本文所有代码全部基于Java实现图的存储和创建一文所实现的带权无向图。
广度优先遍历
广度优先搜索(Breadth-First-Search,BFS) 类似于二叉树的层序遍历。基本思想是:首先访问起始顶点v,接着由v出发,依次访问未访问过的邻接顶点w1,w2,…wi,然后依次访问w1,w2,…wi的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,访问他们所有未被访问过的邻接顶点,直至图中所有顶点都被访问过为止。若此时仍有顶点未被访问,则另选图中一个未被访问的顶点作为起始点,重复上述过程,直至所有顶点都被访问过。
很明显每一次BFS只能遍历到一个连通分量的所有顶点,如果图不是连通图的话,一次BFS就无法遍历所有顶点了,于是为了遍历非连通图,我们引入一个辅助数组private static boolean[] visited;
,visited[i]
表示下标未i的顶点是否已被访问过,这样每执行完一次BFS后,检查该数组中是否还有值未false
的值,如果有就从该下标开始继续BFS,如果没有则说明图已经遍历完成。
BFS代码
public ArrayList<String> BFSTraverse(){
//对图进行广度优先遍历
//访问标记数组初始化
graph_t.visited = new boolean[this.vexNum];
for (int i = 0; i < this.vexNum; i++) {
visited[i] = false;
}
ArrayList<String> res = new ArrayList<>();
for (int i = 0; i < this.vexNum; i++) {
if(!graph_t.visited[i]){
res = this.BFS(i,res);
}
}
return res;
}
private ArrayList<String> BFS(int vnodeIndex,ArrayList<String> tmpRes){
//tmpRes保存临时结果,该方法执行一次只能遍历一个连通分量,需要上一个方法才能遍历整个非连通图
//初始化辅助队列
LinkedList<VNode> queue = new LinkedList<>();
//讲遍历起点放入
queue.offer(this.vertices.get(vnodeIndex));
while (!queue.isEmpty()){
//从队列中弹出一个顶点并访问
VNode node = queue.remove();
//获取该顶点的下标
int curIndex = this.containVnode(node.getName());
if (!graph_t.visited[curIndex]){
//如果该店还未被访问则访问它
graph_t.visited[curIndex] = true;
tmpRes.add(node.getName());
//利用临时变量遍历node的所有邻接点,并加入队列
ArcNode tmpArcNode = new ArcNode(node.first);
while (tmpArcNode != null){
//小的设计缺陷,无法通过边点快速找到与node相连的顶点
if (node.getName().equals(tmpArcNode.getNode1().getName())){
//此时node2试邻接点
queue.offer(tmpArcNode.getNode2());
}else{
//否则node1为邻接点
queue.offer(tmpArcNode.getNode1());
}
tmpArcNode = tmpArcNode.next;
}
}
}
return tmpRes;
}
深度优先遍历
与广度优先搜索不同,深度优先搜索(Depth-First-Search,DFS) 类似于树的先序遍历。如其名称中所暗含的意思一样,这中搜索算法搜索策略是尽可能“深”地搜索一个图。
他的基本思想如下:首先访问图中某一起始点v,然后由v出发,访问与v邻接且未被访问任一顶点w1,再访问与w1邻接且未被访问地任一顶点w2…重复上述过程,依次退回到最近被访问的顶点,若它还有邻接点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。
一次DFS和一次BFS一样都具有不能完全遍历非连通图的问题,所有采取了和BFS相同的处理方法。
DFS代码
public ArrayList<String> DFSTraverse(){
//对图进行深度优先遍历
//访问标记数组初始化
graph_t.visited = new boolean[this.vexNum];
for (int i = 0; i < this.vexNum; i++) {
visited[i] = false;
}
ArrayList<String> res = new ArrayList<>();
for (int i = 0; i < this.vexNum; i++) {
if(!graph_t.visited[i]){
res = this.DFS(i,res);
}
}
return res;
}
private ArrayList<String> DFS(int vnodeIndex,ArrayList<String> tmpRes){
//该方法与BFS思路一样只是将队列改为栈
Stack<VNode> stack = new Stack<>();
stack.push(this.vertices.get(vnodeIndex));
while (!stack.isEmpty()){
VNode node = stack.pop();
int curIndex = this.containVnode(node.getName());
if (!graph_t.visited[curIndex]){
tmpRes.add(node.getName());
graph_t.visited[curIndex] = true;
ArcNode tmpArcNode = node.first == null ? null : new ArcNode(node.first);
while (tmpArcNode != null){
if (node.getName().equals(tmpArcNode.getNode1().getName())){
//此时node2试邻接点,精确获取当前图中的顶点对象
stack.push(this.getVNodeByName(tmpArcNode.getNode2().getName()));
}else{
//否则node1为邻接点
stack.push(this.getVNodeByName(tmpArcNode.getNode1().getName()));
}
tmpArcNode = tmpArcNode.next;
}
}
}
return tmpRes;
}
运行结果
测试运行的代码如下:
public static void main(String[] args) {
graph_t g = new graph_t();
g.create();
g.showGraph();
System.out.println("---------------BFS-----------------------");
ArrayList<String> bfsRes = g.BFSTraverse();
for (int i = 0; i < g.getVexNum(); i++) {
System.out.print(bfsRes.get(i) + " ");
}
System.out.println();
System.out.println("---------------DFS-----------------------");
ArrayList<String> dfsRes = g.DFSTraverse();
for (int i = 0; i < g.getVexNum(); i++) {
System.out.print(dfsRes.get(i) + " ");
}
}
输入
输入是这样一张图:
输出
输出结果如下:
如有错误恳请指正