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

图的基本概念

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

什么是图

图（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);
        }
    }
}

DFS示例

广度优先遍历（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);
                    }
                }
            }
        }
    }
}

BFS示例