鋪墊

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

鄰接表：鄰接表是存儲圖結(jié)構(gòu)的一種有效方式，如下圖所示，左邊節(jié)點(diǎn)數(shù)組存儲圖中所有節(jié)點(diǎn)，右側(cè)鄰接表存儲節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。

簡介

這篇文章我們要講的是拓?fù)渑判?，這是一個針對有向無環(huán)圖的算法，主要是為了解決前驅(qū)后繼的關(guān)系，即我們在完成當(dāng)前事項(xiàng)的時候需要先完成什么事項(xiàng)，其實(shí)這在我們流程控制里面用的挺多的。看下面這個圖，我們需要先完成A事項(xiàng)，然后才能去完成B，C事項(xiàng)，B，C事項(xiàng)的屬于并列的，沒有先后順序，但是對于D事項(xiàng)需要在B，C事項(xiàng)完成之后才能進(jìn)行。而拓?fù)渑判蚰軌驇椭覀冋业竭@個完成事項(xiàng)的合理順序，同時我們看上面這個例子，A事項(xiàng)完成之后，B，C事項(xiàng)是沒有先后順序的，不管是先完成B還是C都符合條件，所以拓?fù)渑判虻捻樞蛐蛄胁皇峭耆欢ǖ摹?/p>

工作過程

首先拓?fù)渑判驅(qū)?yīng)操作的是一個有向無環(huán)圖。無環(huán)圖，則肯定存在至少一個結(jié)點(diǎn)入度為0。在當(dāng)前情況下，我們需要查找入度為0的節(jié)點(diǎn)進(jìn)行操作，入度為0，表示當(dāng)前節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)，或者前驅(qū)節(jié)點(diǎn)已經(jīng)處理，可以直接操作。操作完畢之后，將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)入度全部減1，再次查找入度節(jié)點(diǎn)為0的節(jié)點(diǎn)進(jìn)行操作，此后就是一個遞歸過程，不斷處理當(dāng)前情況下入度為0的節(jié)點(diǎn)，直至所有節(jié)點(diǎn)處理完畢。

數(shù)據(jù)結(jié)構(gòu)

有向圖結(jié)構(gòu)如下，其中node存儲當(dāng)前圖中包含的所有節(jié)點(diǎn)，adj存儲對應(yīng)下標(biāo)節(jié)點(diǎn)的鄰接點(diǎn)。初始化圖時候，我們需要初始化圖中節(jié)點(diǎn)個數(shù)，存儲節(jié)點(diǎn)的數(shù)組以及節(jié)點(diǎn)對應(yīng)鄰接數(shù)組。同時提供一個addEdge方法，用于在兩個節(jié)點(diǎn)直接加邊，其實(shí)就是將后繼節(jié)點(diǎn)放入前驅(qū)節(jié)點(diǎn)的鄰接表中。

public?static?class?Graph{
? ? ? ?/**
? ? ? ??* 節(jié)點(diǎn)個數(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ù)渑判?/h3>

拓?fù)渑判蚴紫瘸跏蓟藘蓚€臨時數(shù)組，一個隊(duì)列，一個inDegree數(shù)組存儲對應(yīng)下標(biāo)節(jié)點(diǎn)的入度，因?yàn)槊看卧L問的節(jié)點(diǎn)需要前驅(qū)節(jié)點(diǎn)已經(jīng)完成，即入度為0，有了這個數(shù)組我們就可以比較快速的找到這些節(jié)點(diǎn)；另一個是visited數(shù)組，標(biāo)志當(dāng)前節(jié)點(diǎn)是否已經(jīng)訪問過，防止多次訪問；一個nodes隊(duì)列則保存在目前情況下所有入度為0的節(jié)點(diǎn)。（注意，為了存取方便，我們都是存儲的節(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) {
? ? ? ?//用一個數(shù)組標(biāo)志所有節(jié)點(diǎn)入度
? ? ? ?int[]?inDegree?=?new?int[graph.nodeSize];
? ? ? ?for?(LinkedList?list?:?graph.adj) {
? ? ? ? ? ?for?(Object?index?:?list) {
? ? ? ? ? ? ? ?++?inDegree[(int)index];
? ? ? ? ? }
? ? ? }
? ? ? ?//用一個數(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;
? }

測試樣例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);
? }

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

測試樣例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);
? }

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

總結(jié)

我在上面有說到，拓?fù)渑判蚩梢杂脕砼袛鄨D是否存在環(huán)，其實(shí)判斷方式很簡單，實(shí)現(xiàn)步驟與上面一致，只是我們最后判斷一下出隊(duì)的元素個數(shù)是否等于圖的節(jié)點(diǎn)個數(shù)，如果等于，證明圖無環(huán)，如果不等于則證明存在環(huán)。

到此這篇關(guān)于Java實(shí)現(xiàn)拓?fù)渑判虻氖纠a的文章就介紹到這了,更多相關(guān)Java拓?fù)渑判騼?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論