❤️

ARCHAI

Undergraduate / Rookie

Back
Featured image of post 图的遍历

图的遍历

广度优先遍历(BFS)

BFS(Breadth-First-Search),参考对树的层序遍历

对上面的图从①出发进行BFS得到序列:

①②⑤ ⑥ ③⑦ ④⑧

若采用不同的储存结构,可能会得到不同的遍历结果(这个差异主要来自寻找邻接点的过程),对于邻接矩阵存储的图,由于邻接矩阵是唯一的,所以BFS序列也是唯一的;同理,邻接表存储的图BFS序列不唯一

BFS算法

与树的层序遍历不同的是,由于图中存在回路,遍历过程中会出现重复访问的问题,故可构造visited数组,用来标记已访问过的数组。

此外,还应针对非连通图做额外的判断,遍历完一个连通分量(极大连通子图)后,遍历查找visited数组中是否还存在未遍历的,如果有即为另一连通分量,继续调用BFS即可。

void BFS(Graph G,int v);

bool visited[MAX_VERTEX_NUM];

SqQueue Q;//辅助队列
void BFSTraverse(Graph G){
    //初始化visited数组
    for (int i = 0; i < G.vexnum; ++i) {//使下标从1开始
        visited[i]=false;
    }
    //对非连通图的处理
    for (int v = 0; v < G.vexnum; ++v) {
        if (!visited[v])
            BFS(G,v);
    }
}

//从顶点v出发广度优先遍历图G
void BFS(Graph G,int v){
    visit(v);
    visited[v]=true;
    EnQueue(Q,v);//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);//顶点v出队列Q
        for (w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//处理v的所有邻接点
            if (!visited[w]) {
                visit(w);
                visited[w]=true;
                EnQueue(Q,w);
            }//if
    }//while
}

需要借助辅助队列存储v的所有邻接结点

复杂度

(一)空间

空间复杂度主要来自辅助队列,在访问v的邻接结点时会入队,因此最坏的情况下

复杂度为:$O(|V|)$

(二)时间

对时间复杂度的分析,不必纠结于算法中的具体循环,只需宏观地分析:

①访问|V|个结点需要的时间复杂度?

②访问各个结点的邻接结点需要的时间?

邻接矩阵型 邻接表型
$O(V)$ $O(V)$
$O(V^2)$ $O(2E)=O(E)$
时间复杂度 $O(V^2)$ $O(V+E)$

时间复杂度=访问各结点所需时间+探索各条边所需时间

广度优先生成树

简而言之,就是 $\text{连通图}\overset{BFS}{\rightarrow}\text{树}$

仅保留每个节点第一次被访问的那条通路

此外还有广度优先生产森林,即 $\text{非连通图}\overset{BFS}{\rightarrow}\text{森林}$

深度优先遍历(DFS)

BFS(Depth-First-Search),参考对树的先序遍历

对上面的图从②出发进行DFS得到序列:

② ① ⑤ ⑥ ③ ④⑦ ⑧

同样的,邻接矩阵存储得到序列唯一,邻接表则不唯一。

DFS算法

void DFS(Graph G,int v);

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){
    //初始化visited数组
    for (int i = 0; i < G.vexnum; ++i)
        visited[i]=false;
    //对非连通图的处理
    for (int v = 0; v < G.vexnum; ++v) 
        if (!visited[v])
            DFS(G,v);
}

//从顶点v出发广度优先遍历图G
void DFS(Graph G,int v){
    visit(v);
    visited[v]=true;
    for (w=FirstNeighbor(G,v);w>=0;w=FirstNeighbor(G,v))//始终遍历v的第一个邻接点,往“深”处走
        if (!visited[w]) {
            DFS(G,w);
        }//if
}

复杂度

(一)空间

主要来自函数调用栈,因此最坏的情况与最好的情况分别是

因此,空间复杂度为$O(|V|)$

(二)时间

邻接矩阵型 邻接表型
$O( V
$O( V
时间复杂度 $O( V

深度优先生成树

同BFS

思考:图的遍历与图的连通性

根据上述算法可知,对于无向图,调用BFS/DFS的次数与连通分量的数量有关,即 $\text{BFS|DFS调用次数}\propto \text{连通分量数}$

对于有向图:

1.若从①出发,需要调用几次DFS?

答:4次。

2.若从⑦出发,需要调用几次DFS?

答:1次。

因此,有

图的分类 调用BFS|DFS次数
无向图 连通:1次
非连通:连通分量数
有向图 普通有向图:具体分析(与出发点的选择有关)
强连通图:1次

🖋

Archai
Built with Hugo
Theme Stack designed by Jimmy