Java邻接矩阵实现图数据结构

﹏ヽ暗。殇╰゛Y 2023-10-04 08:55 71阅读 0赞

## 概述 ##

图是对数学图进行建模的数据结构。它由一组称为顶点和边的连接对组成。我们可以使用顶点数组和边的二维数组来表示图。

重要概念

*  **顶点**\-图形的每个节点都表示为一个顶点。在下面给出的示例中，标记的圆圈表示顶点。所以A到G是顶点。我们可以使用下图所示的数组来表示它们。此处A可以通过索引0标识。B可以使用索引1标识，依此类推。
 *  **边**\-边表示两个顶点之间的路径或两个顶点之间的线。在下面给出的示例中，A到B，B到C等的线表示边。我们可以使用一个二维数组来表示边，如下图所示。在这里AB可以在第0行第1列表示为1，BC在第1行第2列表示为1，依此类推，将其他组合保持为0。
 *  **邻接**\-通过一个边彼此连接的两个节点或顶点是相邻的。在下面给出的示例中，B与A相邻，C与B相邻，依此类推。
 *  **路径**\-路径表示两个顶点之间的一系列边。在下面给出的示例中，ABCD表示从A到D的路径。

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70][] ###

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1][] ###

### 基本操作 ###

以下是图的基本基本操作。

*  **添加顶点**\-将顶点添加到图形。
 *  **添加边**\-在图形的两个顶点之间添加边。
 *  **显示顶点**\-显示图形的顶点。

### 添加顶点操作 ###

//add vertex to the array of vertex
    public void addVertex(char label){
       lstVertices[vertexCount++] = new Vertex(label);
    }

### 添加边操作 ###

//add edge to edge array
    public void addEdge(int start,int end){
       adjMatrix[start][end] = 1;
       adjMatrix[end][start] = 1;
    }

### 显示边操作 ###

//display the vertex
    public void displayVertex(int vertexIndex){
       System.out.print(lstVertices[vertexIndex].label+" ");
    }

### 遍历算法 ###

以下是图上的重要遍历算法。

*  **深度优先搜索**\-沿**深度**运动遍历图形。
 *  **广度优先搜索**\-以**广度**运动遍历图形。

### 深度优先搜索算法 ###

深度优先搜索算法（DFS）在深度运动中遍历图形，并使用堆栈记住在任何迭代中出现死角时获取下一个顶点以开始搜索。

如上面给出的示例，DFS算法首先从A到B到C到D再到E，然后到F，最后到G。

*  **规则1-**访问相邻的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。
 *  **规则2-**如果未找到相邻的顶点，则从堆栈中弹出一个顶点。（它将弹出堆栈中没有相邻顶点的所有顶点。）
 *  **规则3-**重复规则1和规则2，直到堆栈为空。

public void depthFirstSearch(){
       //mark first node as visited
       lstVertices[0].visited = true;
       //display the vertex
       displayVertex(0);   
       //push vertex index in stack
       stack.push(0);
    
       while(!stack.isEmpty()){
          //get the unvisited vertex of vertex which is at top of the stack
          int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
          //no adjacent vertex found
          if(unvisitedVertex == -1){
             stack.pop();
          }else{
             lstVertices[unvisitedVertex].visited = true;
             displayVertex(unvisitedVertex);
             stack.push(unvisitedVertex);
          }
       }
    
       //stack is empty, search is complete, reset the visited flag        
       for(int i=0;i<vertexCount;i++){
          lstVertices[i].visited = false;
       }        
    }

### 广度优先搜索算法 ###

广度优先搜索算法（BFS）沿广度运动遍历图形，并使用队列记住在任何迭代中出现死角时获取下一个顶点以开始搜索。

如以上示例所示，BFS算法首先从A到B遍历到E到F，然后遍历C和G，最后遍历到D。它采用以下规则。

*  **规则1-**访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。
 *  **规则2-**如果未找到相邻的顶点，请从队列中删除第一个顶点。
 *  **规则3-**重复规则1和规则2，直到队列为空。

public void breadthFirstSearch(){
       //mark first node as visited
       lstVertices[0].visited = true;
       //display the vertex
       displayVertex(0);   
       //insert vertex index in queue
       queue.insert(0);
    
       int unvisitedVertex;
       while(!queue.isEmpty()){
          //get the unvisited vertex of vertex which is at front of the queue
          int tempVertex = queue.remove();            
          //no adjacent vertex found
          while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
             lstVertices[unvisitedVertex].visited = true;
             displayVertex(unvisitedVertex);
             queue.insert(unvisitedVertex);               
          }
       }   
    
       //queue is empty, search is complete, reset the visited flag        
       for(int i=0;i<vertexCount;i++){
          lstVertices[i].visited = false;
       }    
    }

### 图的实现 ###

***Stack.java***

public class Stack {
       private int size;           // size of the stack
       private int[] intArray;     // stack storage
       private int top;            // top of the stack
    
       // Constructor 
       public Stack(int size){
          this.size = size;           
          intArray = new int[size];   //initialize array
          top = -1;                   //stack is initially empty
       }
    
       // Operation : Push
       // push item on the top of the stack 
       public void push(int data) {
    
          if(!isFull()){
             // increment top by 1 and insert data 
             intArray[++top] = data;
          }else{
             System.out.println("Cannot add data. Stack is full.");
          }      
       }
    
       // Operation : Pop
       // pop item from the top of the stack 
       public int pop() {
          //retrieve data and decrement the top by 1
          return intArray[top--];        
       }
    
       // Operation : Peek
       // view the data at top of the stack    
       public int peek() {       
          //retrieve data from the top
          return intArray[top];
       }
    
       // Operation : isFull
       // return true if stack is full 
       public boolean isFull(){
          return (top == size-1);
       }
       
       // Operation : isEmpty
       // return true if stack is empty 
       public boolean isEmpty(){
          return (top == -1);
       }
    }

***Queue.java***

public class Queue {
        
       private final int MAX;
       private int[] intArray;
       private int front;
       private int rear;
       private int itemCount;
    
       public Queue(int size){
          MAX = size;
          intArray = new int[MAX];
          front = 0;
          rear = -1;
          itemCount = 0;
       }
    
       public void insert(int data){
          if(!isFull()){
             if(rear == MAX-1){
                rear = -1;            
             }       
    
             intArray[++rear] = data;
             itemCount++;
          }
       }
    
       public int remove(){
          int data = intArray[front++];
          if(front == MAX){
             front = 0;
          }
          itemCount--;
          return data;  
       }
    
       public int peek(){
          return intArray[front];
       }
    
       public boolean isEmpty(){
          return itemCount == 0;
       }
    
       public boolean isFull(){
          return itemCount == MAX;
       }
    
       public int size(){
          return itemCount;
       }    
    }

***Vertex.java***

public class Vertex {
       public char label;
       public boolean visited;
    
       public Vertex(char label){
          this.label = label;
          visited = false;
       }   
    }

***Graph.java***

public class Graph {
       private final int MAX = 7;
       //array of vertices
       private Vertex lstVertices[];
       //adjacency matrix
       private int adjMatrix[][];
       //vertex count
       private int vertexCount;
    
       private Stack stack;
       private Queue queue;
    
       public Graph(){
          lstVertices = new Vertex[MAX];
          adjMatrix = new int[MAX][MAX];
          vertexCount = 0;
          stack = new Stack(MAX);
          queue = new Queue(MAX);
          for(int j=0; j<MAX; j++) // set adjacency
             for(int k=0; k<MAX; k++) // matrix to 0
                adjMatrix[j][k] = 0;
       } 
    
       //add vertex to the vertex list
       public void addVertex(char label){
          lstVertices[vertexCount++] = new Vertex(label);
       }
    
       //add edge to edge array
       public void addEdge(int start,int end){
          adjMatrix[start][end] = 1;
          adjMatrix[end][start] = 1;
       }
    
       //display the vertex
       public void displayVertex(int vertexIndex){
          System.out.print(lstVertices[vertexIndex].label+" ");
       }
    
    	// display the AdjMatrix
    	public void displayAdjMatrix() {
    		System.out.println();
    		for (int i = 0; i < adjMatrix.length; i++) {
    			for (int j = 0; j < adjMatrix[0].length; j++) {
    				System.out.print(adjMatrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}       
    
       //get the adjacent unvisited vertex
       public int getAdjUnvisitedVertex(int vertexIndex){
          for(int i=0; i<vertexCount; i++)
             if(adjMatrix[vertexIndex][i]==1 && lstVertices[i].visited==false)
                return i;
          return -1;
       }
    
       public void depthFirstSearch(){
          //mark first node as visited
          lstVertices[0].visited = true;
          //display the vertex
          displayVertex(0);   
          //push vertex index in stack
          stack.push(0);
    
          while(!stack.isEmpty()){
             //get the unvisited vertex of vertex which is at top of the stack
             int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
             //no adjacent vertex found
             if(unvisitedVertex == -1){
                stack.pop();
             }else{
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                stack.push(unvisitedVertex);
             }
          }
    
          //stack is empty, search is complete, reset the visited flag        
          for(int i=0;i<vertexCount;i++){
             lstVertices[i].visited = false;
          }        
       }
    
       public void breadthFirstSearch(){
          //mark first node as visited
          lstVertices[0].visited = true;
          //display the vertex
          displayVertex(0);   
          //insert vertex index in queue
          queue.insert(0);
          int unvisitedVertex;
          while(!queue.isEmpty()){
             //get the unvisited vertex of vertex which is at front of the queue
             int tempVertex = queue.remove();            
             //no adjacent vertex found
             while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                queue.insert(unvisitedVertex);               
             }
          }   
    
          //queue is empty, search is complete, reset the visited flag        
          for(int i=0;i<vertexCount;i++){
             lstVertices[i].visited = false;
          }    
       }
    }

### 演示程序 ###

***GraphDemo.java***

public class GraphDemo {
       public static void main(String args[]){
          Graph graph = new Graph();
    
          graph.addVertex('A');   //0
          graph.addVertex('B');   //1
          graph.addVertex('C');   //2
          graph.addVertex('D');   //3
          graph.addVertex('E');   //4
          graph.addVertex('F');   //5
          graph.addVertex('G');   //6
    
          /*       1  2  3   
           * 0  |--B--C--D
           * A--|
           * |
           * |     4 
           * |-----E
           * |     5  6
           * |  |--F--G
           * |--| 
           */        
          graph.addEdge(0, 1);   //AB
          graph.addEdge(1, 2);   //BC
          graph.addEdge(2, 3);   //CD
          graph.addEdge(0, 4);   //AC
          graph.addEdge(0, 5);   //AF
          graph.addEdge(5, 6);   //FG
          System.out.print("Depth First Search: ");
          //A B C D E F G
          graph.depthFirstSearch();        
          System.out.println("");
          System.out.print("Breadth First Search: ");
          //A B E F C G D
          graph.breadthFirstSearch();
    	  graph.displayAdjMatrix();
       }
    }

如果我们编译并运行上面的程序，那么它将产生以下结果-

Depth First Search: A B C D E F G 
    Breadth First Search: A B E F C G D
    0 1 0 0 1 1 0 
    1 0 1 0 0 0 0 
    0 1 0 1 0 0 0 
    0 0 1 0 0 0 0 
    1 0 0 0 0 0 0 
    1 0 0 0 0 0 1 
    0 0 0 0 0 1 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210321095414451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021032110250780.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbHdheTI=,size_16,color_FFFFFF,t_70