Java如何實現拓撲排序

今天小編給大家分享一下Java如何實現拓撲排序的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

鋪墊

有向圖：我們這節要講的算法涉及到有向圖，所以我先把有向圖的一些概念說一下，文章后面就不做解釋啦。首先有向圖節點與節點之間是用帶箭頭的線連接起來的。節點有出度和入度的概念，連線尾部指向的節點出度加1，連線頭部，也就是箭頭指向的節點入度加1。看下面這個例子，A的入度為0，出度為2，B的入度為1，出度為1，C的入度為1，出度為1，D的入度為2，出度為0。

鄰接表：鄰接表是存儲圖結構的一種有效方式，如下圖所示，左邊節點數組存儲圖中所有節點，右側鄰接表存儲節點的相鄰節點。

簡介

這篇文章我們要講的是拓撲排序，這是一個針對有向無環圖的算法，主要是為了解決前驅后繼的關系，即我們在完成當前事項的時候需要先完成什么事項，其實這在我們流程控制里面用的挺多的。看下面這個圖，我們需要先完成A事項，然后才能去完成B，C事項，B，C事項的屬于并列的，沒有先后順序，但是對于D事項需要在B，C事項完成之后才能進行。而拓撲排序能夠幫助我們找到這個完成事項的合理順序，同時我們看上面這個例子，A事項完成之后，B，C事項是沒有先后順序的，不管是先完成B還是C都符合條件，所以拓撲排序的順序序列不是完全一定的。

工作過程

首先拓撲排序對應操作的是一個有向無環圖。無環圖，則肯定存在至少一個結點入度為0。在當前情況下，我們需要查找入度為0的節點進行操作，入度為0，表示當前節點沒有前驅節點，或者前驅節點已經處理，可以直接操作。操作完畢之后，將當前節點的后繼節點入度全部減1，再次查找入度節點為0的節點進行操作，此后就是一個遞歸過程，不斷處理當前情況下入度為0的節點，直至所有節點處理完畢。

數據結構

有向圖結構如下，其中node存儲當前圖中包含的所有節點，adj存儲對應下標節點的鄰接點。初始化圖時候，我們需要初始化圖中節點個數，存儲節點的數組以及節點對應鄰接數組。同時提供一個addEdge方法，用于在兩個節點直接加邊，其實就是將后繼節點放入前驅節點的鄰接表中。

public static class Graph{
       /**
        * 節點個數
        */
       private Integer nodeSize;
       /**
        * 節點
        */
       private char[] node;
       /**
        * 鄰接表
        */
       private LinkedList[] adj;

       public Graph(char[] node) {
           this.nodeSize = node.length;
           this.node = node;
           this.adj = new LinkedList[nodeSize];
           for (int i = 0 ; i < adj.length ; i++) {
               adj[i] = new LinkedList();
          }
      }
       /**
        * 在節點之間加邊，前驅節點指向后繼節點
        * @param front 前驅節點所在下標
        * @param end 后繼節點所在下標
        */
       public void addEdge(int front, int end) {
           adj[front].add(end);
      }
  }

拓撲排序

拓撲排序首先初始化了兩個臨時數組，一個隊列，一個inDegree數組存儲對應下標節點的入度，因為每次訪問的節點需要前驅節點已經完成，即入度為0，有了這個數組我們就可以比較快速的找到這些節點；另一個是visited數組，標志當前節點是否已經訪問過，防止多次訪問；一個nodes隊列則保存在目前情況下所有入度為0的節點。（注意，為了存取方便，我們都是存儲的節點下標 step1:初始化inDegree數組，visited數組； step2:遍歷inDegree數組，將所有入度為0的節點入nodes隊列； step3:依次將節點node出隊； 根據visited判斷當前node是否已經被訪問，是，返回step3，否，進行下一步； 將當前節點的鄰接節點入度-1，判斷鄰接節點入度是否為0，為0直接放入nodes隊列，不為0返回step3；

/**
    * @param graph 有向無環圖
    * @return 拓撲排序結果
    */
   public List<Character> toPoLogicalSort(Graph graph) {
       //用一個數組標志所有節點入度
       int[] inDegree = new int[graph.nodeSize];
       for (LinkedList list : graph.adj) {
           for (Object index : list) {
               ++ inDegree[(int)index];
          }
      }
       //用一個數組標志所有節點是否已經被訪問
       boolean[] visited = new boolean[graph.nodeSize];
       //開始進行遍歷
       Deque<Integer> nodes = new LinkedList<>();
       //將入度為0節點入隊
       for (int i = 0 ; i < graph.nodeSize; i++) {
           if (inDegree[i] == 0) {
               nodes.offer(i);
          }
      }
       List<Character> result = new ArrayList<>();
       //將入度為0節點一次出隊處理
       while (!nodes.isEmpty()) {
           int node = nodes.poll();
           if (visited[node]) {
               continue;
          }
           visited[node] = true;
           result.add(graph.node[node]);
           //將當前node的鄰接節點入度-1；
           for (Object list : graph.adj[node]) {
               -- inDegree[(int)list];
               if (inDegree[(int)list] == 0) {
                   //前驅節點全部訪問完畢，入度為0
                   nodes.offer((int) list);
              }
          }
      }
       return result;
  }

測試樣例1

public static void main(String[] args) {
       ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();
       //初始化一個圖
       Graph graph = new Graph(new char[]{'A', 'B', 'C', 'D'});
       graph.addEdge(0, 1);
       graph.addEdge(0,2);
       graph.addEdge(1,3);
       graph.addEdge(2,3);
       List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);
  }

執行結果

測試樣例2

public static void main(String[] args) {
       ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();
       //初始化一個圖
       Graph graph = new Graph(new char[]{'A', 'B', 'C', 'D','E','F','G','H'});
       graph.addEdge(0, 1);
       graph.addEdge(0,2);
       graph.addEdge(0,3);
       graph.addEdge(1,4);
       graph.addEdge(2,4);
       graph.addEdge(3,4);
       graph.addEdge(4,7);
       graph.addEdge(4,6);
       graph.addEdge(7,5);
       graph.addEdge(6,7);
       List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);
  }

執行結果

以上就是“Java如何實現拓撲排序”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。