图杂谈

1. 关于图的基本操作

本章中的很多程序对采用邻接表或邻接矩阵的存储结构都适用，主要原因是在图的基本操作函数中保持了相同的参数和返回值，而封闭了内部实现细节。例如，取顶点 $ x $ 的邻接顶点 $ y $ 的下一个邻接顶点的函数为 NextNeighbor(G, x, y)。

1.1 用邻接矩阵作为存储结构

1
2
3
4
5
6
7
8
9
int NextNeighbor(MGraph& G, int x, int y) {
    if (x != -1 && y != -1) {
        for (int col = y + 1; col < G.vexnum; col++) {
            if (G.Edge[x][col] > 0 && G.Edge[x][col] < maxWeight) // maxWeight 代表 ∞
                return col;
        }
    }
    return -1; // 返回 -1 表示没有下一个邻接顶点
}

1.2 用邻接表作为存储结构

1
2
3
4
5
6
7
8
9
10
11
12
int NextNeighbor(ALGraph& G, int x, int y) {
    if (x != -1) { // 顶点 x 存在
        ArcNode *p = G.vertices[x].first; // 对应边链表第一个边节点
        // 寻找邻接顶点 y
        while (p != NULL && p->data != y) {
            p = p->next;
        }
        if (p != NULL && p->next != NULL)
            return p->next->data; // 返回下一个邻接顶点
    }
    return -1; // 返回 -1 表示没有下一个邻接顶点
}

2. 关于图的遍历、连通性、生成树、关键路径的几个要点

  1. 图的遍历：在执行图的遍历时，由于图中可能存在回路，且图的任一顶点都可能与其他顶点相连，所以在访问完某个顶点后可能会沿某些边又回到曾经访问过的顶点。因此，需要设置一个辅助数组 visited[] 标记顶点是否已被访问过，避免重复访问。

  2. 深度优先搜索（DFS）：深度优先搜索时利用回溯法对图进行遍历，通常采用递归方法实现。在向前递归查找某一邻接节点之前，必须判断该节点是否已被访问过。此外，递归算法均可借助栈来实现非递归算法，深度优先搜索也不例外。

  3. 广度优先搜索（BFS）：广度优先搜索是一种分层的遍历过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程。

  4. 邻接矩阵与邻接表：一个给定的图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入先后次序不同，则生成的邻接表表示也会不同。

  5. 最小生成树（MST）：图的最小生成树首先必须是带权连通图，其次要在 $ n $ 个顶点的图中选择 $ n-1 $ 条边将其连通，使得其权值总和达到最小，且不出现回路。

  6. 关键活动与关键路径：加速某一关键活动不一定能缩短整个工程的工期，因为 AOE 网中可能存在多条关键路径。还可能存在称为“桥”的一种特殊关键活动，它位于所有的关键路径上，只有加速它才能缩短整个工期。