JAVA数据结构----实现图广度优先遍历与深度优先遍历
程序员文章站
2022-05-24 09:49:35
...
数据结构系列是我学习做的笔记,会持续更新,源码分享在github:数据结构,当然你也可以从下面的代码片中获取
注:github代码更新会有延迟,关注不迷路????
本篇博文简单介绍图广度优先搜索算法与深度优先搜索算法,并用java实现
1. 广度优先搜索
教科书上解释:广度优先搜索类似于类似于树的层次遍历,是数的层次遍历的推广
算法描述:
从图中某个顶点v开始,先访问该顶点,再依此访问该顶点的每一个未被访问的邻接点w1,w2,w3,w4……,然后按照顺序访问顶点w1,w2……未被访问的邻接点,重复直到图中顶点全被访问。
简要概述:选择图的一个顶点,自上而下,自左而右,由远及近,一行行搜索
2. 深度优先搜索
教科书上解释: 深度优先搜索类似于树的先根遍历,是树先根遍历的推广
算法描述:
从图中某个顶点v开始访问,然后访问他的任意一个邻接点w1,再从w1出发,访问与w1相邻且还未被访问的顶点w2……,如此直到所有的邻接点都被访问过,接着,回退一步,遇到前一次刚访问的顶点,查看其是否还有未被访问的邻接点,若有,访问此顶点,否则继续回退,直到所有顶点全被访问。
简要概述:先从一个顶点出发,一根筋靠着左边走,直到走不通后往后倒退,若有路,接着靠左走,如此往复,直到所有顶点全部被访问。
3. Java实现: GraphSearch.java
其中,涉及到 IGraph 接口,详见链接:
图的存储结构之邻接表或者图的存储结构之邻接矩阵
当然也可以访问我的github,获取完整项目代码(注:更新有延迟),地址见博文开头
package code.Graph;
import code.Queue.LinkQueue;
/**
* 图的搜索算法,包括广度优先搜索算法和深度优先搜索算法
* */
public class GraphSearch {
private static boolean [] visited;//访问标志数组
/**
* 广度优先遍历----(Breadth First Search)
* */
public static void BFSTraverse(IGraph G)throws Exception{
visited = new boolean[G.getVexNum()];//实例化访问标志数组
for (int v = 0;v < G.getVexNum();v++){//循环 顶点次数 次
//将访问标志数组初始化
visited[v] = false;
}
for (int v = 0;v < G.getVexNum();v++){
if (!visited[v]){ //顶点尚未被访问
BFS(G,v);
}
}
}
private static void BFS(IGraph G,int v)throws Exception{
visited[v] = true;
System.out.print(G.getVex(v).toString()+", ");
LinkQueue Q = new LinkQueue();//辅助队列Q
Q.offer(v);
while (!Q.isEmpty()){
int u = (Integer)Q.poll();//队首元素出队列并赋值给u
for (int w = G.firstAdjVex(u);w >= 0;w = G.nextAdjVex(u,w)){
if (!visited[w]){ //w为u的尚未访问的邻接顶点
visited[w] = true;
System.out.print(G.getVex(w).toString()+", ");
Q.offer(w);
}
}
}
}
/**
* 深度优先遍历----(Depth First Search)
* */
public static void DFSTraverse(IGraph G) throws Exception{
visited = new boolean[G.getVexNum()];//实例化访问标志数组
for (int v = 0;v < G.getVexNum();v++){//循环 顶点次数 次
//将访问标志数组初始化
visited[v] = false;
}
for (int v = 0;v < G.getVexNum();v++){
if (!visited[v]){ //顶点尚未被访问
DFS(G,v);
}
}
}
public static void DFS(IGraph G,int v)throws Exception{
//从第v个顶点出发递归地深度优先遍历图G
visited[v] = true;
System.out.print(G.getVex(v).toString()+", ");//访问第v个顶点
for (int w = G.firstAdjVex(v);w >= 0;w = G.nextAdjVex(v,w)){
if (!visited[w]){
DFS(G,w); //对v的尚未访问的邻接顶点w递归调用DFS
}
}
}
}