使用 Java 的 DSA - Graph

概述

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

重要术语

顶点 − 图的每个节点都表示为一个顶点。在下面给出的示例中，带标签的圆圈表示顶点。因此 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 的路径。

基本操作

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

添加顶点 − 向图形添加顶点。
添加边 − 在图的两个顶点之间添加边。
显示顶点 −显示图形的顶点。

添加顶点操作

//将顶点添加到顶点数组
public void addVertex(char label){
    lstVertices[vertexCount++] = new Vertex(label);
}

添加边操作

//将边添加到边数组
public void addEdge(int start,int end){
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}

显示边操作

//显示顶点
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(){
    //将第一个节点标记为已访问
    lstVertices[0].visited = true;
    //显示顶点
    displayVertex(0);
    //将顶点索引推送到堆栈中
    stack.push(0);
    
    while(!stack.isEmpty()){
    //获取位于堆栈顶部的顶点的未访问顶点
    int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
    //未找到相邻顶点
    if(unvisitedVertex == -1){
        stack.pop();
        }else{
            lstVertices[unvisitedVertex].visited = true;
            displayVertex(unvisitedVertex);
            stack.push(unvisitedVertex);
        }
    }
    
    //堆栈为空，搜索完成，重置访问标志
    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(){
    //将第一个节点标记为已访问
    lstVertices[0].visited = true;
    //显示顶点
    displayVertex(0);
    //将顶点索引插入队列
    queue.insert(0);
    
    int unvisitedVertex;
    while(!queue.isEmpty()){
        //获取位于队列最前面的顶点的未访问顶点
        int tempVertex =queue.remove();
        //未找到相邻顶点
        while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){
            lstVertices[unvisitedVertex].visited = true;
            displayVertex(unvisitedVertex);
            queue.insert(unvisitedVertex);
        }
    }
    
    //队列为空，搜索完成，重置访问标志
    for(int i=0;i<vertexCount;i++){
        lstVertices[i].visited = false;
    } 
}

图形实现

Stack.java

package com.tutorialspoint.datastructure;

public class Stack {
    private int size; // 堆栈的大小
    private int[] intArray; // 堆栈存储
    private int top; // 堆栈顶部
    
    // 构造函数
    public Stack(int size){
        this.size = size;
        intArray = new int[size]; //初始化数组
        top = -1; //堆栈最初为空
    }
    
    // 操作:推送
    // 将项目推送到堆栈顶部
    public void push(int data) {
    
        if(!isFull()){
            // 将顶部增加 1 并插入数据
            intArray[++top] = data;
        }else{
            System.out.println("无法添加数据。堆栈已满。");
        }
    }
    
    // 操作:弹出
    // 从堆栈顶部弹出项目
    public int pop() {
        //检索数据并将顶部减少 1
        return intArray[top--];
    }
    
    // 操作:Peek
    // 查看堆栈顶部的数据
    public int peek() {
        // 从顶部检索数据
        return intArray[top];
    }
    
    // 操作:isFull
    // 如果堆栈已满，则返回 true
    public boolean isFull(){
        return (top == size-1);
    }
    
    // 操作:isEmpty
    // 如果堆栈为空，则返回 true
    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;
    //顶点数组
    private Vertex lstVertices[];
    //邻接矩阵
    private int adjMatrix[][];
    //顶点数
    private int vertexCount;
    
    private Stack stack;
    private Queue query;
    
    public Graph(){
        lstVertices = new Vertex[MAX];
        adjMatrix = new int[MAX][MAX];
        vertexCount = 0;
        stack = new Stack(MAX);
        query = new Queue(MAX);
        for(int j=0; j<MAX; j++) // 设置邻接
        for(int k=0; k<MAX; k++) // 将矩阵设置为 0
        adjMatrix[j][k] = 0;
    }
    
    //将顶点添加到顶点列表
    public void addVertex(char label){
        lstVertices[vertexCount++] = new Vertex(label);
    }

    //将边添加到边数组
    public void addEdge(int start,int end){
        adjMatrix[start][end] = 1;
        adjMatrix[end][start] = 1;
    }
    
    //显示顶点
    public void displayVertex(int vertexIndex){
        System.out.print(lstVertices[vertexIndex].label+" ");
    }
    
    //获取相邻的未访问顶点
    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 voiddepthFirstSearch(){
        //将第一个节点标记为已访问
        lstVertices[0].visited = true;
        //显示顶点
        displayVertex(0);
        //将顶点索引推送到堆栈中
        stack.push(0);
        
        while(!stack.isEmpty()){
            //获取位于堆栈顶部的顶点的未访问顶点
            int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
            //未找到相邻顶点
            if(unvisitedVertex == -1){
                stack.pop();
            }else{
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                stack.push(unvisitedVertex);
            }
        }
        
        //堆栈为空，搜索完成，重置访问标志
        for(int i=0;i<vertexCount;i++){
            lstVertices[i].visited = false;
        }
    }

    public void breadthFirstSearch(){
        //将第一个节点标记为已访问
        lstVertices[0].visited = true;
        //显示顶点
        displayVertex(0);
        //将顶点索引插入队列
        queue.insert(0);
        int unvisitedVertex;
        while(!queue.isEmpty()){
            //获取位于队列最前面的顶点的未访问顶点
            int tempVertex =queue.remove();
            //未找到相邻顶点
            while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                queue.insert(unvisitedVertex);
            }
        }
        
        //队列为空，搜索完成，重置已访问标志
        for(int i=0;i<vertexCount;i++){
            lstVertices[i].visited = false;
        }
    }
}

演示程序

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

使用 Java 的 DSA 教程

有用资源

使用 Java 的 DSA - Graph

概述

基本操作

添加顶点操作

添加边操作

显示边操作

遍历算法

深度优先搜索算法

广度优先搜索算法

图形实现

演示程序

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！