数据结构中的图：概念、存储与遍历

图的基本概念

图在数据结构中扮演着重要的角色，其复杂性和多样性使得它在计算机科学中占据着独特的地位。图是一种由顶点和连接顶点的边构成的结构，用于表示对象之间的关系。

什么是图

图（Graph）由顶点集合和边集合组成，通常表示为 G = (V, E)。其中，V 是顶点的集合，E 是边的集合。顶点是图中元素的基本单位，边则表示顶点之间的连接关系。

图可以分为有向图和无向图。在有向图中，边是有方向的，表示从一个顶点指向另一个顶点；而在无向图中，边则没有方向。

图的术语与分类

图的分类包括简单图、多重图、完全图和子图等。简单图是指没有重边和自环的图，多重图则允许重边。完全图是指任意两个不同顶点之间都有边相连的图。而子图是原图的一个部分，包括一些顶点和边。

有向图与无向图

• 有向图：边是有序对，记为 (v, w)，表示从顶点 v 到顶点 w 的连接。
• 无向图：边是无序对，记为 (v, w)，表示顶点 v 和顶点 w 之间的双向连接。

顶点的度、入度和出度

在图中，每个顶点的度是与其相连的边的数目。对于有向图，度分为入度和出度，分别表示以该顶点为终点和起点的有向边的数目。

图的存储结构

图的存储结构有多种选择，常见的有邻接矩阵、邻接表、十字链表、邻接多重表和边集数组。

邻接矩阵

邻接矩阵是一种简单易理解的图存储方式。它使用一个二维数组来表示顶点之间的连接关系。对于一个有 n 个顶点的图，邻接矩阵是一个 n × n 的二维数组。若顶点 vi 和 vj 之间有边，则 A[i][j] = 1，否则为 0。

这种方法适合稠密图，但对于稀疏图则会浪费大量空间。

邻接表

邻接表是一种更为高效的存储方式，尤其适用于稀疏图。它为每个顶点维护一个链表，用于存储其所有相邻顶点。

这种方式存储空间小，但查找两个顶点之间是否有边连接的时间复杂度较高。

十字链表

十字链表是有向图的一种存储方式，将邻接表和逆邻接表结合起来，使得在查找入度和出度时都很方便。

邻接多重表

邻接多重表是无向图的存储方式，适用于需要频繁修改边的图。它在邻接表的基础上，每条边只存一次，从而简化了对边的操作。

边集数组

边集数组关注边的集合，适用于需要频繁遍历边的操作。它由两个数组构成，一个存储顶点信息，另一个存储边的信息。

图的遍历

图的遍历是访问图中所有顶点的过程，主要有深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历（DFS）

DFS 类似于树的先序遍历，通过递归的方式尽可能深入到图的每个分支。其实现需要辅助递归栈。

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w]) {
            DFS(G, w);
        }
    }
}

广度优先遍历（BFS）

BFS 类似于树的层序遍历，通过队列实现，逐层访问顶点。

void BFSTraverse(MGraph G) {
    Queue Q;
    InitQueue(&Q);
    for (i = 0; i = 0; j = NextNeighbor(G, i, j)) {
                    if (!visited[j]) {
                        visited[j] = TRUE;
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}

FAQ

1. 什么是图的连通性？

图的连通性是指图中任意两个顶点是否可达。对于无向图，若从任一顶点出发能到达所有其他顶点，则为连通图；对于有向图，若任意两个顶点之间都有路径，则为强连通图。

2. 图的存储结构如何选择？

选择图的存储结构取决于图的密度和操作需求。稠密图适合邻接矩阵，稀疏图适合邻接表。十字链表适用于需要频繁查询入度和出度的有向图。

3. 如何判断两个顶点之间是否有边？

在邻接矩阵中，直接检查对应位置的值。在邻接表中，需要遍历顶点对应的边表。

4. DFS 和 BFS 的区别是什么？

DFS 是沿着一个分支尽可能深地走，适用于路径查找；BFS 是逐层遍历，适用于查找最短路径。

5. 什么是生成树？

生成树是一个包含图中所有顶点的最小连通子图，对于无回路的连通图，生成树的边数为 n-1（n为顶点数）。