图的遍历:深度优先遍历/搜索(DFS)与广度优先遍历/搜索(BFS)
程序员文章站
2022-05-22 10:06:21
...
深度优先遍历/搜索(DFS)
基本思想
- 对于连通图:从初始访问顶点开始,先访问第一个邻接顶点,再以这个邻接顶点为新的初始顶点,访问它的第一个邻接顶点
- 对于非连通图:对图的连通分量分别进行深度优先遍历
- 这种方式是优先纵向深入
- 这是一个递归的过程
算法实现
邻接矩阵的实现
boolean[] isVisited ;
void dfs(Graph<?> G)
{
//开始时所有顶点均未访问
isVisited = new boolean[G.getNumOfVertexes()];
for(int i = 0;i < G.getNumOfVertexes(); i++)
isVisited[i] = false;
//遍历所有顶点,进行DFS
for(int i = 0; i < G.getNumOfVertexes(); i++)
if( !isVisited[i])
dfs(G, i);
}
//DFS递归算法部分
void dfs(Graph<?> G, int i)
{
//访问该顶点
System.out.println(G.getValueByIndex(i).toString());
//标记为已访问
isVisited[i] = true;
//访问下个邻接顶点
int j = 0;
for(j = 0; j < G.getNumOfVertexes(); j++)
if(G.edges[i][j] != 0 && !isVisited[j]) //有边且未被访问
dfs(G, j);
}
算法分析
- 邻接矩阵结构:邻接矩阵是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,所以算法时间复杂度为O(n2)
广度优先遍历/搜索(BFS)
基本思想
- 类似于树的层序遍历
- 使用一个辅助队列
- 首先,将初始顶点入队列,当队列不为空的时候使队列中第一个顶点出队,将出队顶点的所有未访问过的邻接顶点入队,循环上述过程,就遍历了整个图
- 实质上是先遍历初始顶点的所有邻接顶点,再遍历邻接顶点的邻接顶点,一层层遍历
算法实现
邻接矩阵的实现
boolean[] isVisited ;
void bfs(Graph<?> G)
{
//使用辅助队列(链表)
LinkedList<Integer> queue = new LinkedList<>();
//开始时所有节点均未被访问
isVisited = new boolean[G.getNumOfVertexes()];
for(int i = 0; i < G.getNumOfVertexes(); i++)
isVisited[i] = false;
//遍历所有顶点,进行BFS
for(int i = 0; i < G.getNumOfVertexes(); i++)
{
//对未被访问的顶点搜索
if(!isVisited[i])
{
//访问该顶点
System.out.println(G.getValueByIndex(i).toString()); //一个访问动作
isVisited[i] = true; //将该顶点标记为已访问
queue.addLast(i); //将此顶点入队列
while(!queue.isEmpty())
{
i = queue.removeFirst(); //移除现队列中第一个顶点,赋给i
for(int j = 0; j < G.getNumOfVertexes(); j++)
{
//访问下个邻接顶点
if(G.edges[i][j] != Graph.INFINITY && G.edges[i][j] != 0 && !isVisited[j]) //有边且未被访问
{
//访问该顶点
System.out.println(G.getValueByIndex(j).toString()); //一个访问动作
isVisited[j] = true; //将该顶点标记为已访问
queue.addLast(j); //将此顶点入队列
}
}
}
}
}
算法分析
-
邻接矩阵结构:邻接矩阵是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,所以算法时间复杂度为O(n2)
-
两种算法时间复杂度是一样的,区别在于对顶点的访问顺序不同
-
当遍历图的时间很长,目的是为了寻找合适的顶点时
深度优先遍历适合目标比较明确,以找到目标为主要目的的情况
广度优先遍历适合在不断扩大遍历范围时找到相对最优解的情况
推荐阅读
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
图的遍历——广度优先搜索算法
-
图 - DFS深度优先搜索和BFS广度优先搜索