Java 程序员Java

图的遍历1.广度优先遍历(BFS)2.深度优先遍历(DFS)

2021-08-24  本文已影响0人  程序花生

1.广度优先遍历(BFS)

基本思想:首先从图的某个顶点0出发,访问0之后,依次访问与0相邻接的未被访问的顶点,然后从这些顶点出发继续访问与之相邻接的未被访问的顶点,以此类推,直到所有顶点都被访问完。

广度优先遍历(BFS)代码

bool visited[Max_Vex];             //访问标记数组 
void BFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
    visited[i]=false;        //初始化标记数组
    InitQueue(Q); 
    for(v=0;v<G.vexnum;++v)
    if(!visited[v])             //如果v未被访问,那么从v起,开始做广度优先遍历
    BFS(G,v);
}
void BFS(Graph G,int v){
    visit(v); visited[v]=true; Enqueue(Q,v); //访问结点并将结点入队
    while(!isEmpty(Q)){ 
        DeQueue(Q,v); for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]){
            visit(w); visited[w]=true; EnQueue(Q,w)
        }
    }
}

性能分析

广度优先生成树

在广度优先遍历过程中,我们可以得到一颗遍历树,称为广度优先生成树

注意:

2.深度优先遍历(DFS)

基本思想:首先从图的某个顶点0出发,访问0之后,访问与0相邻接 的未被访问的顶点1,然后从1顶点出发继续访问与之相邻接的未被访问 的顶点2,以此类推,若不能再继续向下访问时,依次回退最近一次访问 的顶点,每次回退查看当前顶点还有没有未被访问的邻接顶点,若有就访 问,直到所有顶点都被访问完。

bool visited[Max_Vex];             //访问标记数组 
void DFSTraverse(Graph G){
    for(i=0;i<G.vexnum;++i)
    visited[i]=false;        //初始化标记数组
    for(v=0;v<G.vexnum;++v)
    if(!visited[v])             //如果v未被访问,那么从v起,开始做深度优先遍历
    DFS(G,v);
}
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);
    }
}

性能分析

深度优先生成树

在深度优先遍历过程中,我们可以得到一颗遍历树,称为深度优先生成树

注意:

作者:有出路
链接:https://juejin.cn/post/6999560010879483917
来源:掘金

上一篇下一篇

猜你喜欢

热点阅读