6.3 图的基本操作

  • 「深度优先搜索 depth first search」 深度优先搜索首先访问起始顶点 vv,从顶点 vv 的邻接表中选取一个未被访问过的顶点 ww 进行访问,并从 ww 开始继续进行深度优先搜索。将 vv 的邻接表中的当前位置保存在一个栈中。当最终搜索到一个顶点 uu,且 uu 的邻接表中的顶点全部被访问过时,就从栈中取出一个顶点,并按照上述方法处理该顶点的邻接表。在搜索过程中,已经访问的过的顶点不再被访问,而未被访问过的顶点被访问且存入栈。当栈为空时,搜索结束。深度优先搜索可以更方便地用递归实现,如下函数 dfs 为深度优先搜索的递归实现。
short int visited[MAX_VERTICES]; // 全局变量,需要初始化为 false
void dfs(int v)
{
    node *w;
    visited[v] = true;
    printf("%5d", v);
    for (w = graph[v]; w; w = w->link)
        if (!visited[w->vertex])
            dfs(w->vertex);
}

6-12

如图是图 GG 及其邻接表,如果从顶点 00 开始进行深度优先搜索,则依次访问顶点的顺序如下:0,1,3,7,4,5,2,60, 1, 3, 7, 4, 5, 2, 6

对于有 nn 个顶点,ee 条边的图 GG,如果用 邻接表 来存储图 GG,由于 dfs 对邻接表中的每个顶点至多扫描一次,所以完成搜索时间复杂度为 O(e)O(e)。如果采用 邻接矩阵 来存储图 GG,那么访问顶点 vv 的所有邻接顶点所需的时间开销为 O(n)O(n)。而整个搜索过程至多访问 nn 个顶点,所以搜索的时间复杂度为 O(n2)O(n^2)

  • 「广度优先搜索 breadth first search」 广度优先搜索从顶点 vv 开始,并把 vv 标记为“已访问”。然后访问 vv 的邻接表中的每一个顶点,并将它们保存在一个队列中。在当前顶点的邻接表中的所有顶点被访问过以后,从队列中取出一个顶点,然后访问该顶点的邻接表中的所有顶点。在搜索过程中,未被访问过的顶点被访问,且存入队列;已经访问过的顶点不再被访问。当队列为空时,搜索结束。函数 bfs 给出了广度优先搜索的实现。代码中使用的函数 addq 和函数 deleteq 分别为元素入队和元素出队。
short int visited[MAX_VERTICES];
void addq(Queue *front, Queue *rear, int v);
int deleteq(Queue *front);
void bfs(int v)
{
    node *w;
    Queue *front, *rear;
    front = rear = NULL;
    printf("%5d", v);
    visited[v] = true;
    addq(&front, &rear, v);
    while (front)
    {
        v = deleteq(&front);
        for (w = graph[v]; w; w->link)
            if (!visited[w->vertex]) {
                printf("%5d", w->vertex);
                addq(&front, &rear, w->vertex);
                visited[w->vertex] = true;
            }
    }
}

dfs 一样,对于有 nn 个顶点,ee 条边的图 GG,如果用 邻接表 来存储图 GGbfs 完成搜索时间复杂度为 O(e)O(e)。如果采用 邻接矩阵 来存储图 GG,那么访问顶点 vv 的所有邻接顶点所需的时间开销为 O(n)O(n)。而整个搜索过程至多访问 nn 个顶点,所以搜索的时间复杂度为 O(n2)O(n^2)

「深度优先搜索」与「广度优先搜索」访问到的顶点以及与这些顶点相关联的边形成图 GG 的一个连通分支。

  • 『判断某个无向图是否是连通图』 调用 dfs(0)bfs(0),然后检查是否存在未被访问过的顶点,如无则是连通图,反之不是。如果图采用邻接表来存储表示,那么这个算法的时间复杂度为 O(n+e)O(n+e)
  • 『列举图中所有连通分支』 重复调用 dfs(v) 或者 bfs(v) 即可解决,其中 v 是图中未被访问的顶点。实现此算法的函数 connected 如下,如果图 GG 采用邻接表存储表示,该算法的时间复杂度为 O(n+e)O(n+e);如果图 GG 采用邻接矩阵存储表示,该算法的时间复杂度为 O(n2)O(n^2)
void connected()
{
    int i;
    for (i = 0; i < n; i++) // O(n)
        if(!visited) {
            dfs(i); // O(e) or O(n^2)
            printf("\n");
        }
}
  • 「生成树 spanning tree」 是由图中的边和图中所有顶点构成的一棵树。如下图为一个完全图及其三棵生成树。

6-13

  • 在函数 dfsbfsif 语句中,再加入一条语句,把边 (v, w) 插入到一个链表中,就可以得到树边集合 TTTT 中的边构成一棵树,且包含图中的所有顶点。当采用函数 dfs 来构造生成树时,则该生成树称为 「深度优先生成树 depth first spanning tree」;当采用函数 bfs 来构造生成树时,则该生成树称为 「广度优先生成树 breadth first spanning tree」。如果把任意一条非树边 (v, w) 加入到生成树 TT 中,就必定会产生环路。如下图为图 GG 及其从顶点 00 开始,分别进行深度优先搜索和广度优先搜索得到的生成树。

6-14

  • 「极小子图 minimal subgraph」 是指边数最少的子图。图 GG 的生成树是图 GG 上的一个极小子图 GG'。使得 V(G)=V(G)V(G') = V(G),且 GG' 是连通的。由于任意一个具有 nn 个顶点的连通图至少含有 n1n - 1 条边,且具有 n1n - 1 条边的连通图必是一棵树。则 nn 个顶点的生成树包含 n1n - 1 条边
  • 「关节点 articulation point」 是图 GG 中的一个顶点 vv,如果删除 vv 以及关联在 vv 上的所有边后,得到的新图 GG' 至少包含两个连通分支。如下图连通图有四个关节点:顶点 1,3,5,71, 3, 5, 7
  • 「双连通图 biconnected graph」 是没有关节点的连通图。上图 GG 就是一个双连通图。
  • 「双连通分支 biconnected component」 是图 GG 中的一个最大双连通子图 HH。「最大双连通子图」是指,在图 GG 中不再有其他子图既是双连通的,同时又包含 HH。如下图连通图包含 6 个双连通分支。而上图双连通图 GG 仅包含一个双连通分支,即自身。图中的同一条边不可能同时出现在两个或两个以上双连通分支中。因此,图 GG 的双连通分支是对图 GG 中边的一种划分。

6-15

  • 「深度优先编号 depth first number, dfn」 是某个顶点在深度优先搜索过程中被访问的顺序编号,如下图 a) 为上图连通图调用 dfs(3) 函数得到的一棵生成树,下图 b) 为 a) 树的重画版本。每个顶点外面的数字表示其对应的「深度优先编号」。一般地,在深度优先生成树中,如果顶点 uu 是顶点 vv 的祖先顶点,则有 dfn(u) << dfn(v)
  • 「回退边 back edge」 是非树边,当且仅当 uuvv 的祖先顶点,或是 vvuu 的祖先顶点。下图 b) 中的虚线表示非树边,也均表示回退边。

6-16

  • lowlow(u) 等于从 uu 出发,经过一条由其后代顶点形成的路径和一条回退边,所能到达的具有最小深度优先编号顶点的饿编号。即,

    low(u) = min{dfn(u), min{low(w) | w 是 u 的儿子}, min{dfn(w) | (u, w) 是一条回退边}}
    

    判断顶点 uu 是否关节点的方法:如果顶点 uu 是生成树的根顶点,且 uu 至少有两个儿子,则 uu 是关节点;如果 uu 不是根顶点,那么当且仅当 uu 有一个儿子 ww,使得 low(w) \geq dfn(n),则 uu 是关节点。各顶点的 dfnlow 值如下表,可以得出:

    1. 顶点 11 是一个关节点,因为它有一个儿子顶点 00,使得 low(0) =4= 4 \geq dfn(1) =3= 3
    2. 顶点 77 是一个关节点,因为它有一个儿子顶点 88,使得 low(8) =9= 9 \geq dfn(7) =7= 7
    3. 顶点 55 是一个关节点,因为它有一个儿子顶点 66,使得 low(6) =5= 5 \geq dfn(5) =5= 5
    4. 根顶点 33 是关节点,因为它的儿子个数多于 1。
顶点 00 11 22 33 44 55 66 77 88 99
dfn 4 3 2 0 1 5 6 7 9 8
low 4 3 0 0 0 5 5 7 9 8
  • bicon 函数是求解图的双连通分支,bicon 函数的调用方法是 bicon(x, -1),其中 x 是生成树的根。
#define MIN2(x, y) ((x) < (y) ? (x) : (y))
short int dfn[MAX_VERTICES];
short int low[MAX_VERTICES];
int num;

void bicon(int u, int v)
{
    node *ptr;
    int w, x, y;
    dfn[u] = low[u] = num++;
    for (ptr = graph[u]; ptr; ptr->link) {
        w = ptr->vertex;
        if (v != w && dfn[w] < dfn[u]) {
            add(&top, u, w); // add edge to stack
            if (dfn[w] < 0) { // w has not been visited
                bicon(w, u);
                low[u] = MIN2(low[u], low[w]);
                if (low[w] >= dfn[u]) {
                    printf("New biconnected component: ");
                    do {
                        delete(&top, &x, &y); // delete edge from stack
                        printf("<%d, %d>", x, y);
                    } while (!((x == u) && (y == w)));
                    printf("\n");
                }
            }
        }
        else if (w != v) low[u] = MIN2(low[u], dfn[w]);
    }
}

results matching ""

    No results matching ""