Java实现图的广度优先遍历和深度优先遍历

深碍√TFBOYSˉ_ 2023-07-18 12:49 6阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

首先构造一个图的基本功能：

package binarySortTree;
    
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Stack;
    
    public class Graph {
        
    
    	ArrayList<String> vertex;
    	int[][] edges;
    	public Graph(String[] arr) {
        
    		int n = arr.length;
    		vertex = new ArrayList<String>(n);
    		for(int i=0; i<n; i++) {
        
    			vertex.add(arr[i]);
    		}
    		edges = new int[n][n];
    	}
    	//修改边缘
    	public void insertEdge(int v1, int v2, int weight) {
        
    		edges[v1][v2] = weight;
    		edges[v2][v1] = weight;
    	}
    	//获取值
    	public String getValue(int n) {
        
    		return vertex.get(n);
    	}
    	//用邻接矩阵展示图
    	public void show() {
        
    //		Arrays.deepToString(edges);
    		for(int[] link : edges) {
        
    			System.out.println(Arrays.toString(link));
    		}
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		String[] arr = {
        "1","2","3","4","5","6","7","8"};
    		Graph g = new Graph(arr);
    		g.insertEdge(0, 1, 1);
    		g.insertEdge(0, 2, 1);
    		g.insertEdge(1, 3, 1);
    		g.insertEdge(1, 4, 1);
    		g.insertEdge(3, 7, 1);
    		g.insertEdge(4, 7, 1);
    		g.insertEdge(2, 5, 1);
    		g.insertEdge(2, 6, 1);
    		g.insertEdge(5, 6, 1);
    		g.show();
    		g.dfsR();
    		g.dfs();
    		g.bfs();
    	}
    }

## 1. 广度优先遍历 ##

广度优先遍历用队列实现，利用队列先入先出的特性。实现思路和树的层次遍历基本相同，不同的是：

1，树不存在孤立节点，图可能存在孤立顶点，需要从每个顶点都遍历一次，这样孤立节点也会被输出。  
2，树只有一个父节点，且是有向的，所以只能从一个方向经过，不用担心重复输出。图可能有多个来源，所以在图的广度优先遍历时需要一个标记来判断是否输出过此顶点。

//广度优先遍历，和二叉树的层次遍历思路一样，深度用栈，广度用队列
    public void bfs() {
        
    	int len = vertex.size();
    	//存储定点是否被访问过
    	boolean[] flag = new boolean[len];
    	for(int i=0; i<len; i++) {
        
    		flag[i] = false;
    	}
    	//遍历每一个顶点，防止有孤立顶点
    	for(int i=0; i<len; i++) {
        
    		ArrayDeque<Integer> quene = new ArrayDeque<Integer>();
    		int temp = i;
    		//在该顶点没有被访问过时才入队，换句话数，i>0时只有是孤立节点才能进入while循环
    		if(!flag[temp]) {
        
    			quene.add(temp);
    			flag[temp] = true;
    		}
    		while(!quene.isEmpty()) {
        
    			//出列并输出，此时并不把flag[temp]置为true，否则一个顶点可能在出队前再次入队。
    			temp = quene.poll();
    			System.out.print(vertex.get(temp) + " ");
    			for(int j=temp+1; j<len; j++) {
        
    				if(edges[temp][j] != 0 && !flag[j]) {
        
    					//j入队并把flag[j]置为true，这样保证每个顶点只入队一次，输出一次
    					quene.add(j);
    					flag[j] = true;
    				}
    			}
    		}
    	}
    	System.out.println();
    }

## 2.1 深度优先遍历的递归实现 ##

实现思路类似于二叉树的递归前序遍历

//深度优先遍历递归写法
    public void dfsR() {
        
    	int len = vertex.size();
    	//存储定点是否被访问过
    	boolean[] flag = new boolean[len];
    	for(int i=0; i<len; i++) {
        
    		flag[i] = false;
    	}
    	for(int i=0; i<len; i++) {
        
    		dfsR(flag, i);
    	}
    	System.out.println();
    }
    public void dfsR(boolean[] flag, int n) {
        
    	if(!flag[n]) {
        
    		System.out.print(vertex.get(n) + " ");
    	}
    	flag[n] = true;
    	for(int i=n+1; i<vertex.size(); i++){
        
    		if(edges[n][i] != 0 && !flag[i]) {
        
    			dfsR(flag, i);
    		}
    	}
    }

## 2.2 深度优先遍历的非递归实现 ##

//深度优先遍历非递归写法，把广度写法的队列换成栈就是深度
    public void dfs() {
        
    	int len = vertex.size();
    	//存储定点是否被访问过
    	boolean[] flag = new boolean[len];
    	for(int i=0; i<len; i++) {
        
    		flag[i] = false;
    	}
    	
    	//防止孤立顶点
    	for(int i=0; i<len; i++) {
        
    		Stack<Integer> stack = new Stack<Integer>();
    		int temp = i;
    		if(!flag[temp]) {
        
    			stack.push(temp);
    		}
    		while(!stack.isEmpty()) {
        
    			temp = stack.pop();
    			System.out.print(vertex.get(temp) + " ");
    			for(int j=len-1; j>temp; j--) {
        
    				if(edges[temp][j] != 0 && !flag[j]) {
        
    					stack.push(j);
    					flag[j] = true;
    				}
    			}
    		}
    	}
    	System.out.println();
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982