Fork me on GitHub

图的遍历

发表于 | 分类于
字数统计: 1,088 | 阅读时长 ≈ 5

图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程称为图的遍历。

深度优先遍历(DFS)

从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。

对于非连通图，只需对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到所有顶点都被访问到为止。

mark

上图中，从顶点A开始一直向右走，遇到访问过的顶点时退回，走右手第二条边，直至返回顶点A。

DFS其实就是一个递归过程，类似于一棵树的前序遍历。

邻接矩阵方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef int Boolean;
Boolean visit[MAX];//访问标志数组,FALSE表示该顶点未被访问

void DFSTraverse (MGraph G)
{
    int i;
    for (i = 0;i < G.numVertexes;i++)
        visit[i] = FALSE;//初始化
    for (i = 0;i < G.numVertexes;i++)
        if (!visit[i])//如果这个顶点没有被访问过
            DFS(G,i);
}

void DFS (MGraph G,int i)
{
    visit[i] = TRUE;
    printf("%c",G.vex[i]);//也可以是其他操作
    for (int j = 0;j < G.numVertexes;j++)
        if (G.arc[i][j] == 1 && !visit[i])
            DFS(G,j);//对被访问的顶点的邻接点递归调用
}

邻接表方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFSTraverse (GraphAdjList GL)
{
    int i;
    for (i = 0;i < GL.numVertexes;i++)
        visit[i] = FALSE;
    for (i = 0;i < GL.numVertexes;i++)
        if (!visit[i])//如果这个顶点没有被访问过
            DFS(GL,i);
}

void DFS (GraphAdjList GL,int i)
{
    EdgeNode *p;
    visit[i] = TRUE;
    printf("%c",GL.adjList[i].data);//也可以是其他操作
    p = GL.adjList[i].firstedge;
    while (P)
    {
        if (!visit[p->adjvex])
            DFS(GL,p->adjvex);
        p = p->next;
    }
}

每个顶点都经过且仅经过一次DFS函数，因为只有该函数能设置visit数组值为TRUE

对于n个顶点e条边的图来说，邻接矩阵方式时间为O(n²),邻接表方式时间为O(n+e),故对于点多边少的稀疏图来说更适合用邻接表。

广度优先遍历(BFS)

原理：每当一个元素出队列，将与该顶点相邻接的所有顶点中未被访问的顶点加入队列，加入前进行打印等处理，类似于图的层序遍历。

mark

邻接矩阵方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void BFSTraverse (MGraph G)
{
    Queue Q;
    InitQueue(&Q);//初始化一个辅助用队列
    for (int i = 0;i < G.numVertexes;i++)
        visit[i] = FALSE;
    for (int i = 0;i < G.numVertexes;i++)
    {
        if (!visit[i])
        {
            visit[i] = TRUE;
            printf("%c",G.vex[i]);
            EnQueue(&Q,i);//将此顶点入队列
            while(!QueueEmpty(Q))//当前队列不为空
            {
                DeQueue(&Q,&i);//将队中元素出队列并赋值给i
                for (int j = 0;j < G.numVertexes;j++)
                {
                    if (G.arc[i][j] == 1 && !visit[j])
                    {
                        visit[j] = TRUE;
                        printf("%c",G.vex[j]);
                        EnQueue(&Q,j);
                    }
                }
            }
        }
    }
}

只有一个DeQuene函数可以出队列，因此所有顶点均经历过该函数下方的for循环，故时间复杂度为O(n²)。

邻接表方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void BFSTraverse (GraphAdjList GL)
{
    EdgeNode *p;
    Queue Q;
    InitQueue(&Q);//初始化一个辅助用队列
    for (int i = 0;i < GL.numVertexes;i++)
        visit[i] = FALSE;
    for (int i = 0;i < GL.numVertexes;i++)
    {
        if (!visit[i])
        {
            visit[i] = TRUE;
            printf("%c",GL.adjList[i].data);
            EnQueue(&Q,i);//将此顶点入队列
            while(!QueueEmpty(Q))//当前队列不为空
            {
                DeQueue(&Q,&i);//将队中元素出队列并赋值给i
                p = GL.adjList[i].firstedge;
                while (p)
                {
                    if (!visit[p->adjvex])
                    {
                        visit[p->adjvex] = TRUE;
                        printf("%c",GL.adjList[p->adjvex].data);
                        EnQueue(&Q,p->adjvex);
                        p = p->next;
                    }
                }
            }
        }
    }
}

时间复杂度为O(n+e)。

DFS与BFS相同方式的时间复杂度相同。

深度优化遍历更适合目标比较明确，以找到目标为主要目的的情况，广度优先遍历更适合在不断扩大遍历范围时找到相对最优解的情况。

-------------本文结束感谢您的阅读-------------
undefined