图的简单实现以及深度和广度优先搜索算法（Java实现）

不念不忘少年蓝@ 2024-04-19 07:35 18阅读 0赞

前面通过Java实现图的数据结构，自定义了顶点，还自定义了栈和队列来实现搜索算法，相对麻烦，其实除了邻接矩阵，我们可以通过一个数组来表示顶点集合，另外深度优先搜索可以通过递归调用来实现，而广度优先搜索必须要通过队列来实现，我们可以直接使用java.util工具包下的队列来代替，这样图的实现就相对简单很多了。

图的基本组成是少不了的，一个是顶点集合vertexs，一个是邻接矩阵matrix，另外我们需要定义边的数量，和用来做广度优先搜索的队列。如下图所示，是图的构成和搜索所需的必要属性，在构造函数中，我们初始化这些属性。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

接着添加两个方法，分别是在图中添加顶点和边的信息。

![2019091512581816.png][]

图的结构有了，这里就可以构建一个简单的图，无向图。如下图所示，7个顶点，6条边。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1][]

深度优先搜索的思路是，从一个顶点开始遍历，依次遍历该顶点所能到达的最远的边，每次都是深入到无边可达的顶点为止。其实可以通过递归来操作，以上图为例，若从A顶点开始遍历，那么依次遍历BC  DE FG，遍历B的时候，会接着深入遍历到C，遍历D的时候会接着遍历E，同理，遍历F的时候会深入遍历到G。

广度优先搜索虽然也很直观，就是先遍历近的节点，然后遍历远的节点，刚开始是遍历BCD，后面一轮再遍历CEG。这里面就不能递归了，必须通过一个队列来保存先前遍历的顶点信息，然后当当前节点已经没有邻接边了，再以队列中的头部元素为起点开始做同样的遍历，直到队列中所有元素弹出，即队列为空遍历结束。

下面给出完整代码：

package com.xxx.algorithm.wh.graph2;
    import java.util.LinkedList;
    import java.util.Queue;
    public class Graph {
    	private final int MAX_VERTS=20;
    	private char[] vertexs;
    	private int[][] matrix;
    	private int nVerts;
    	private Queue<Integer> q;
    	
    	public Graph(){
    		vertexs = new char[MAX_VERTS];
    		matrix = new int[MAX_VERTS][MAX_VERTS];
    		for(int i=0;i<MAX_VERTS;i++)
    			for(int j=0;j<MAX_VERTS;j++)
    				matrix[i][j] = 0;
    		nVerts = 0;
    		q = new LinkedList<Integer>();
    	}
    	
    	public void addEdge(int start,int end){
    		matrix[start][end] = 1;
    		matrix[end][start] = 1;
    	}
    	
    	public void addVertex(char label){
    		vertexs[nVerts++] = label;
    	}
    	
    	public void deepFirstSearch(int v){
    		System.out.print("dfs : ");
    		boolean visited[] = new boolean[MAX_VERTS];
    		for(int i=0;i<MAX_VERTS;i++){
    			visited[i] = false;
    		}
    		dfs(v,visited);
    		System.out.println();
    	}
    	
    	public void dfs(int v,boolean[] visited){
    		System.out.print(vertexs[v]+" ");
    		visited[v] = true;
    		for(int i=0;i<MAX_VERTS;i++){
    			if(matrix[v][i]==1 && visited[i]==false){
    				dfs(i, visited);
    			}
    		}	
    	}
    	
    	public void breadthFirstSearch(int v){
    		System.out.print("bfs : ");
    		boolean visited[] = new boolean[MAX_VERTS]; 
    		for(int i=0;i<MAX_VERTS;i++){
    			visited[i] = false;
    		}
    		bfs(v, visited);
    	}
    	
    	public void bfs(int v,boolean[] visited){
    		System.out.print(vertexs[v]+" ");
    		visited[v] = true;
    		q.add(v);
    		int index = getIndex(vertexs[v]);
    		if(index==-1)return;
    		while(!q.isEmpty()){
    			int u = q.remove();
    			for(int i=0;i<MAX_VERTS;i++){
    				if(matrix[u][i]==1 && visited[i]==false){
    					q.add(i);
    					visited[i] = true;
    					System.out.print(vertexs[i]+" ");
    				}
    			}
    		}
    	}
    	
    	public int getIndex(char v){
    		for(int i=0;i<MAX_VERTS;i++){
    			if(v==vertexs[i])
    				return i;
    		}
    		return -1;
    	}
    	
    	public static void main(String[] args) {
    		Graph graph = new Graph();
    		graph.addVertex('A');
    		graph.addVertex('B');
    		graph.addVertex('C');
    		graph.addVertex('D');
    		graph.addVertex('E');
    		graph.addVertex('F');
    		graph.addVertex('G');
    		
    		graph.addEdge(0, 1);
    		graph.addEdge(0, 3);
    		graph.addEdge(0, 5);
    		graph.addEdge(1, 2);
    		graph.addEdge(3, 4);
    		graph.addEdge(5, 6);
    		
    		graph.deepFirstSearch(0);
    		graph.breadthFirstSearch(0);
    	}
    }

运行程序，打印信息如下：

dfs : A B C D E F G 
    bfs : A B D F C E G

到此，只用了一个类就实现了图数据结构的构造和搜索，相对来说很简洁，但是这种方式只适合简单的无向图，稍微复杂的带权图就没有这么简单了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e265a9b964c843a79d5f704a9d545698.png
[2019091512581816.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b952ecedf8cc4667b3745fd00f48cb20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2b8ae170a2684a87be0b2f8f79d0e65f.png