Java如何實(shí)現(xiàn)拓?fù)渑判?/h1>

發(fā)布時(shí)間：2022-05-16 13:55:06 來源：億速云 閱讀：186 作者：iii 欄目：開發(fā)技術(shù)

今天小編給大家分享一下Java如何實(shí)現(xiàn)拓?fù)渑判虻南嚓P(guān)知識(shí)點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識(shí)，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

鋪墊

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

public static class Graph{        /**         * 節(jié)點(diǎn)個(gè)數(shù)         */        private Integer nodeSize;        /**         * 節(jié)點(diǎn)         */        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();           }       }        /**         * 在節(jié)點(diǎn)之間加邊，前驅(qū)節(jié)點(diǎn)指向后繼節(jié)點(diǎn)         * @param front 前驅(qū)節(jié)點(diǎn)所在下標(biāo)         * @param end 后繼節(jié)點(diǎn)所在下標(biāo)         */        public void addEdge(int front, int end) {            adj[front].add(end);       }   }

拓?fù)渑判?/h4>

拓?fù)渑判蚴紫瘸跏蓟藘蓚€(gè)臨時(shí)數(shù)組，一個(gè)隊(duì)列，一個(gè)inDegree數(shù)組存儲(chǔ)對(duì)應(yīng)下標(biāo)節(jié)點(diǎn)的入度，因?yàn)槊看卧L問的節(jié)點(diǎn)需要前驅(qū)節(jié)點(diǎn)已經(jīng)完成，即入度為0，有了這個(gè)數(shù)組我們就可以比較快速的找到這些節(jié)點(diǎn)；另一個(gè)是visited數(shù)組，標(biāo)志當(dāng)前節(jié)點(diǎn)是否已經(jīng)訪問過，防止多次訪問；一個(gè)nodes隊(duì)列則保存在目前情況下所有入度為0的節(jié)點(diǎn)。（注意，為了存取方便，我們都是存儲(chǔ)的節(jié)點(diǎn)下標(biāo) step1:初始化inDegree數(shù)組，visited數(shù)組； step2:遍歷inDegree數(shù)組，將所有入度為0的節(jié)點(diǎn)入nodes隊(duì)列； step3:依次將節(jié)點(diǎn)node出隊(duì)； 根據(jù)visited判斷當(dāng)前node是否已經(jīng)被訪問，是，返回step3，否，進(jìn)行下一步； 將當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)入度-1，判斷鄰接節(jié)點(diǎn)入度是否為0，為0直接放入nodes隊(duì)列，不為0返回step3；

/**
    * @param graph 有向無環(huán)圖
    * @return 拓?fù)渑判蚪Y(jié)果
    */
   public List<Character> toPoLogicalSort(Graph graph) {
       //用一個(gè)數(shù)組標(biāo)志所有節(jié)點(diǎn)入度
       int[] inDegree = new int[graph.nodeSize];
       for (LinkedList list : graph.adj) {
           for (Object index : list) {
               ++ inDegree[(int)index];
          }
      }
       //用一個(gè)數(shù)組標(biāo)志所有節(jié)點(diǎn)是否已經(jīng)被訪問
       boolean[] visited = new boolean[graph.nodeSize];
       //開始進(jìn)行遍歷
       Deque<Integer> nodes = new LinkedList<>();
       //將入度為0節(jié)點(diǎn)入隊(duì)
       for (int i = 0 ; i < graph.nodeSize; i++) {
           if (inDegree[i] == 0) {
               nodes.offer(i);
          }
      }
       List<Character> result = new ArrayList<>();
       //將入度為0節(jié)點(diǎn)一次出隊(duì)處理
       while (!nodes.isEmpty()) {
           int node = nodes.poll();
           if (visited[node]) {
               continue;
          }
           visited[node] = true;
           result.add(graph.node[node]);
           //將當(dāng)前node的鄰接節(jié)點(diǎn)入度-1；
           for (Object list : graph.adj[node]) {
               -- inDegree[(int)list];
               if (inDegree[(int)list] == 0) {
                   //前驅(qū)節(jié)點(diǎn)全部訪問完畢，入度為0
                   nodes.offer((int) list);
              }
          }
      }
       return result;
  }

測(cè)試樣例1

public static void main(String[] args) {
       ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();
       //初始化一個(gè)圖
       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);
  }

執(zhí)行結(jié)果

public static void main(String[] args) {        ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();        //初始化一個(gè)圖        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);   }

執(zhí)行結(jié)果

以上就是“Java如何實(shí)現(xiàn)拓?fù)渑判颉边@篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。