如题 自用笔记 如有错误欢迎及时指正

目录

一.广度优先搜索(BFS)

1.基本思路

2.算法描述

3.应用

二.深度优先搜索(DFS)

1.基本思路

2.算法描述

3.应用

（以下假设图G有V个结点E条边）

        图的遍历等价于寻找每个顶点的邻接点的过程，BFS与DFS在思路上仅仅是遍历策略上的区别，本质都是上述过程。

        一个图无论是有向图还是无向图，都有可能存在回路，这使得遍历操作必须防止重复访问某一结点，设置一个visited[V]数组来标记某个结点是否访问过可以解决此问题。

        下面分别给出BFS与DFS的思想、类C伪码与N-S流程图描述。

一.广度优先搜索(BFS)

*该方法类似树的层序遍历方法，要借助一个辅助队列实现

1.基本思路

         1.从图的某个顶点V0出发，访问此结点之后，依次访问V0的所有未被访问过的邻接点，然后再分别从这些邻接点出发，广度优先遍历图，直到图中所有已被访问结点的邻接点都被访问到。

        2.若此时图中还有顶点未被访问到，则另选一个图中未被访问到的顶点作为新起点，重复上述过程，直到图中所有结点都被访问到。

2.算法描述

        类似层序遍历思路，树的层序遍历算法就是由BFS启发得来。

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

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