Dsa Using Java 简明教程

DSA using Java - Graph

Overview

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

重要术语

Vertex - 图形中的各个节点表示为顶点。在下方的范例中，标记的圆圈代表顶点。A 至 G 即顶点。我们可以使用数组来表达它们，如下图所示。此处可以通过索引 0 识别 A。可以通过 1 等识别 B，依此类推。
Edge - 边表示两个顶点之间的路径或者两个顶点之间的线。在下方的范例中，从 A 到 B、从 B 到 C 等线表示边。我们可以使用二维数组来表示数组，如下图所示。此处 AB 可以表示为 0 行、1 列中的 1，BC 可以表示为 1 行、2 列中的 1，依此类推，其他组合保持为 0。
Adjacency - 两个节点或顶点通过边互相连接，则它们是相邻的。在下方的范例中，B 邻近 A，C 邻近 B，依此类推。
Path - 路径表示两个顶点之间的边序列。在下方的范例中，ABCD 表示从 A 到 D 的路径。

Basic Operations

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

Add Vertex - 向图形添加一个顶点。
Add Edge - 在图形的两个顶点之间添加一条边。
Display Vertex − 显示图的一个顶点。

Add Vertex Operation

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

Add Edge Operation

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

Display Edge Operation

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

Traversal Algorithms

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

Depth First Search − 以深度方向遍历图。
Breadth First Search − 以广度方向遍历图。

Depth First Search Algorithm

深度优先搜索算法 (DFS) 以深度方向遍历图并使用一个堆栈记住在任何迭代中发生死锁时获取下一个顶点以开始搜索。

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

Rule 1 − 访问相邻的未访问过的顶点。将其标记为已访问。显示它。将其压入堆栈。
Rule 2 − 如果找不到相邻顶点，则从堆栈弹出一个顶点。（它会从堆栈中弹出所有没有相邻顶点的顶点。）
Rule 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;
   }
}

Breadth First Search Algorithm

广度优先搜索算法 (BFS) 以广度方向遍历图并使用一个队列记住在任何迭代中发生死锁时获取下一个顶点以开始搜索。

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

Rule 1 − 访问相邻的未访问过的顶点。将其标记为已访问。显示它。将其插入队列。
Rule 2 − 如果找不到相邻顶点，则从队列中移除第一个顶点。
Rule 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;
   }
}

Graph Implementation

Stack.java

package com.tutorialspoint.datastructure;

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

package com.tutorialspoint.datastructure;

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

package com.tutorialspoint.datastructure;

public class Vertex {
   public char label;
   public boolean visited;

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

Graph.java

package com.tutorialspoint.datastructure;

public class Graph {
   private final int MAX = 20;
   //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+" ");
   }

   //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;
      }
   }
}

Demo Program

GraphDemo.java

package com.tutorialspoint.datastructure;

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();
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

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