bool visited[V]; 
void BFS(Graph G,v){
    //辅助队列
    InitQueue(Q);
    visited[v] = true;
    viist(v);       //访问
    EnQueue(Q, v);
    while(!QueueEmpty(Q)){
        DeQueue(Q, u);
        for (w = FisrtAdjvex(G, u); w != 0; w=NextAdjvex(G,u,w)){        
            //w为当前出队元u的第一个邻接点
            if(!visited[w]){
                visited[w] = true;
                visit(w);
                EnQueue(Q, w);
            }
        }
    }
}
void BFSTraverse(Graph G){
    for (v = 0; v < G.vexnum; ++v){
        visited[v] = false;        //初始化辅助数组
    }
    for (v = 0; v < G.vexnum; ++v){
        if(!visited[v]){
            BSF(G, v);
        }
    }
}

3.应用

查找连通分量

查找一个连通分量中所有结点

查找两个结点之间最短路径

判断偶图

二.深度优先搜索(DFS)

*该方法类似树的先序遍历方法

1.基本思路

1.从图的某一顶点V0出发，访问此顶点，然后依次从V0未被访问的邻接点出发，深度优先遍历图，直到图中所有与V0相邻的顶点都被访问到为止。

2.若此时图中仍有结点未被访问到，则选择图中未被访问到的结点作为起点，重复上述过程，直到图中所有顶点均被访问到为止。

2.算法描述

类先序遍历思想

初始时，所有顶点均被标记为未被访问；

DFS从图的顶点v开始，考虑从v到其他顶点的边：

如果边关联的另一个顶点已经访问过，则返回当前顶点v；

如果边关联的另一个顶点未被访问过，转到该顶点访问并继续搜索；

持续上述过程直到结尾，开始回溯。当回溯返回到起始顶点时，算法终止。

为便于理解，先给出类C伪代码实现。

bool visited[V];     //标记是否已访问过某结点
void DFS(Graph G,v){
    visited[v] = true;     //置为已访问状态
    visit(v);       //操作
    for (w = FirstAdjvex(G, v); w!=0;w=NextAdjvex(G,v,w)){      //w寻找v下一未被访问的邻接点
        if(!visited[w]){
            DFS(G, w);
        }
    }
}
void DFSTraverse(Graph G){
    for (v = 0; v < G.vexnum;++v){
        visited[v] = false;     //初始化辅助数组
    }
    for (v = 0; v < G.vexnum;++v){
        if(!visited[v]){        //当前节点未被访问 DFS
            DFS(G, v);
        }
    }
}

3.应用

拓补排序

查找连通分量

查找图关节点

查找强连通分量

解决迷宫问题等

以上

2021.10.19

17：30

码农公寓

一.广度优先搜索(BFS)

1.基本思路

2.算法描述

3.应用

二.深度优先搜索(DFS)

1.基本思路

2.算法描述

3.应用

相关文章