java实现图结构以及深度优先搜索和广度优先搜索

末蓝、 2024-04-18 23:12 4阅读 0赞

图结构是数据结构里面应该是最复杂的一个数据结构，首先是它的物理结构复杂，图是由顶点和边组成的，这样还算是简单的图形，另外还有带权图。以前的数据结构如：链表，树，栈，队列等等，基本都可以通过普通的数组和链表来构建，但是图因为组成的元素不仅有顶点，还有边，所以表示起来会相对复杂一些，一般是通过邻接矩阵或者矩阵表来表示，如下图所示的图，有五个顶点和四个边组成。

![20190913175019472.png][]

通过矩阵来表示就如下图所示：

![20190913175637284.png][]

这个矩阵其实只是通过二维数组表示了顶点与边之间的关系，当矩阵中数字为1表示两个顶点之间有边。另外，我们还需要通过一个数组来表示顶点。

图可以解决很多问题，比如最小生成树，最短路径，top排序等等，另外图的搜索分为两种，一种是深度优先搜索，另外一种是广度优先搜索，现在来说说他们的具体是怎么回事。

先说深度优先搜索，这是一种遍历图中所有顶点的一种方式，它遵照以下三种规则：

*  规则一、如果可能，访问一个相邻的未访问的节点，标记它，并放入栈中。
 *  规则二、当不能执行规则一时，如果栈不为空，那么从栈中弹出一个顶点。
 *  规则三、如果不能执行规则一和规则二，就完成了整个搜索过程。

整个搜索遍历过程如下图所示，顺序在图中已经标出：

![20190913180719471.png][]

广度优先搜索，它与深度优先搜索不同的地方在于它是先遍历最靠近初始遍历节点的节点，然后依次遍历离初始节点越来越远的节点，它也遵照以下三种规则：

*  规则一、访问下一个未访问的相邻节点（如果存在），这个顶点必须是当前顶点的邻接点，标记它，并把它放入队列中。
 *  规则二、如果因为已经没有未访问的顶点而不能执行规则一，那么从队列头中取出一个顶点（如果存在），并使它成为当前顶点。
 *  规则三、如果因为队列为空而不能执行规则二，则搜索结束。

广度优先搜索遍历过程如下图所示，顺序也在图中已经标出：

![2019091319074346.png][]

两种搜索方式通过图形来表示很直观，但是实现方式却是有很大的差别，第一种深度优先搜索，我们需要借助一个栈，将遍历的节点先放入栈中，并标记已经遍历，如果有相邻节点也是会存入栈中并标记，如果没有相邻节点了，那么就取出栈中的节点，依次遍历下去，直到栈中元素为空，那么遍历结束。

而广度优先搜索就不一样，我们需要按照节点从近到远的顺序来依次遍历，所以需要使用一个队列，先将头结点放入队列，依次遍历他的相邻节点，标记并放入队列中，如果节点没有相邻节点了，那么就从队列头部取出一个节点，继续遍历他的相邻节点，标记并存入队列，直到队列为空，遍历结束。

整个图结构的表示和遍历需要用到二维数组表示顶点之间的关系，用一维数组表示顶点，需要使用栈来做深度优先的遍历操作，需要使用队列来做广度优先的遍历操作，因此表示起来比较复杂。

按照上面的思路，我们可以实现图的结构以及遍历，下面给出所有的代码：

Vertex.java

package com.xxx.algorithm.wh.graph;
    /**
     * 顶点实体
     *
     */
    public class Vertex {
    	public char label;
    	public boolean visited;
    	public Vertex(char lab){
    		this.label = lab;
    		this.visited = false;
    	}
    }

StackX.java

package com.xxx.algorithm.wh.graph;
    
    public class StackX {
    	private final int SIZE=20;
    	private int st[];
    	private int top;
    	
    	public StackX(){
    		st = new int[SIZE];
    		top=-1;
    	}
    	
    	public void push(int val){
    		st[++top] = val;
    	}
    	
    	public int pop(){
    		return st[top--];
    	}
    	
    	public int peek(){
    		return st[top];
    	}
    	
    	public boolean isEmpty(){
    		return top==-1;
    	}
    	
    }

Queue.java

package com.xxx.algorithm.wh.graph;
    
    public class Queue {
    	private final int SIZE=20;
    	private int[] queArray;
    	private int front;
    	private int rear;
    	public Queue(){
    		queArray = new int[SIZE];
    		front = 0;
    		rear= -1;
    	}
    	
    	public void insert(int v){
    		if(rear==SIZE-1){
    			rear = -1;
    		}
    		queArray[++rear] = v;
    	}
    	
    	public int remove(){
    		int temp = queArray[front++];
    		if(front==SIZE)
    			front = 0;
    		return temp;
    	}
    	
    	public boolean isEmpty(){
    		return (rear+1==front) || (front+SIZE-1==rear);
    	}
    }

Graph.java

package com.xxx.algorithm.wh.graph;
    
    public class Graph {
    	private final int MAX_VERTS=20;
    	private Vertex vertexList[];
    	private int adjMat[][];
    	private int nVerts;
    	private StackX stack;
    	private Queue queue;
    	
    	public Graph(){
    		vertexList = new Vertex[MAX_VERTS];
    		adjMat = new int[MAX_VERTS][MAX_VERTS];
    		nVerts = 0;
    		for(int i=0;i<MAX_VERTS;i++){
    			for(int j=0;j<MAX_VERTS;j++){
    				adjMat[i][j] = 0;
    			}
    		}
    		stack = new StackX();
    		queue = new Queue();
    	}
    	
    	/**
    	 * 添加顶点
    	 * @param lab
    	 */
    	public void addVertex(char lab){
    		vertexList[nVerts++] = new Vertex(lab);
    	}
    	
    	/**
    	 * 添加边
    	 * @param start
    	 * @param end
    	 */
    	public void addEdge(int start,int end){
    		adjMat[start][end] = 1;
    		adjMat[end][start] = 1;
    	}
    	
    	/**
    	 * 显示顶点
    	 * @param index
    	 */
    	public void displayVertex(int index){
    		System.out.print(vertexList[index].label +" ");
    	}
    	
    	/**
    	 * 获取未访问的相邻节点
    	 * @param index
    	 * @return
    	 */
    	public int getAdjUnvisitedVertex(int index){
    		for(int i=0;i<nVerts;i++){
    			if(adjMat[index][i]==1&&vertexList[i].visited==false){
    				return i;
    			}
    		}
    		return -1;
    	}
    	
    	/**
    	 * deep-first search
    	 * 规则一、如果可能，访问一个相邻的未访问的节点，标记它，并放入栈中。
    	 * 规则二、当不能执行规则一时，如果栈不为空，那么从栈中弹出一个顶点。
    	 * 规则三、如果不能执行规则一和规则二，就完成了整个搜索过程。
    	 */
    	public void dfs(){
    		vertexList[0].visited = true;
    		displayVertex(0);
    		stack.push(0);
    		while(!stack.isEmpty()){
    			int v = getAdjUnvisitedVertex(stack.peek());
    			if(v==-1){
    				stack.pop();
    			}else{
    				vertexList[v].visited = true;
    				displayVertex(v);
    				stack.push(v);
    			}
    		}
    		
    		//stack is empty
    		for(int i=0;i<nVerts;i++){
    			vertexList[i].visited = false;
    		}
    		
    	}
    	
    	/**
    	 * breadth-first search
    	 * 规则一、访问下一个未访问的相邻节点（如果存在），这个顶点必须是当前顶点的邻接点，标记它，并把它放入队列中。
    	 * 规则二、如果因为已经没有未访问的顶点而不能执行规则一，那么从队列头中取出一个顶点（如果存在），并使它成为当前顶点。
    	 * 规则三、如果因为队列为空而不能执行规则二，则搜索结束。
    	 */
    	public void bfs(){
    		vertexList[0].visited = true;
    		displayVertex(0);
    		queue.insert(0);
    		int v2;
    		while(!queue.isEmpty()){
    			int v1 = queue.remove();
    			while((v2=getAdjUnvisitedVertex(v1))!=-1){
    				vertexList[v2].visited = true;
    				displayVertex(v2);
    				queue.insert(v2);
    			}
    		}
    		
    		for(int i=0;i<nVerts;i++){
    			vertexList[i].visited = false;
    		}
    	}
    }

GraphDemo.java

package com.xxx.algorithm.wh.graph;
    
    public class GraphDemo {
    
    	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.addEdge(0, 1);
    		graph.addEdge(1, 2);
    		graph.addEdge(0, 3);
    		graph.addEdge(3, 4);
    		System.out.print("dfs visits: ");
    		graph.dfs();
    		System.out.println();
    		
    		System.out.print("bfs visits: ");
    		graph.bfs();
    		System.out.println();
    	}
    	
    }

运行示例程序，控制台打印信息如下：

dfs visits: A B C D E 
    bfs visits: A B D C E

深度优先搜索和广度优先搜索的结果和我们之前的描述是一直的。

这里总结一下图的数据结构：

1.  需要使用二维数组即邻接矩阵来表示图，还需要使用数组表示顶点。
2.  深度优先搜索需要使用到栈，来保存遍历过的节点，当没有相邻节点时需要从栈中弹出节点，当栈为空的时候，遍历结束。
3.  广度优先搜索需要使用到队列，来保存遍历过的节点，当没有相邻节点的时候从队头取出节点，当队列为空，遍历结束。

[20190913175019472.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/84c62f0d0a314959ada3fc0535dc2231.png
[20190913175637284.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a46dc80e13bf4f1591532ce6af68d60f.png
[20190913180719471.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e9f4ed4742f34bb8b846314b5278d83c.png
[2019091319074346.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d38412ba433345c19a9ce449b7523f65.png