java 有向無環圖樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）

條件：

1.每個頂點出現且隻出現一次。

2.若存在一條從頂點 A 到頂點 B 的路徑，那麼在序列中頂點 A 出現在頂點 B 的前面。

有向無環圖(DAG)才有拓撲排序，非DAG圖沒有拓撲排序一說。

一般用有向邊訓示順序關系，運用于順序關系。

例如，下面這個圖：

java 有向無環圖樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）

顯然是一個DAG圖，1→4表示4的入度+1，4是1的鄰接點,

代碼表示：前者deg[4]++;後者用vector[1].push(4)

如何寫出拓撲排序代碼？

1.首先将邊與邊的關系确定，建立好入度表和鄰接表。

2.從入度為0的點開始删除，如上圖顯然是1的入度為0，先删除。

java 有向無環圖樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）

3.于是，得到拓撲排序後的結果是 { 1, 2, 4, 3, 5 }。通常，一個有向無環圖可以有一個或多個拓撲排序序列。因為同一入度級别的點可以有不同的排序方式。

4.拓撲排序可以判斷圖中有無環，如下圖

java 有向無環圖樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）

顯然4，5，6入度都是1，不存在入度為0的點，無法進行删除操作。判斷有無環的方法，對入度數組周遊，如果有的點入度不為0，則表明有環。

例題+代碼

拓撲排序(一)-Hiho-Coder1174

描述

由于今天上課的老師講的特别無聊，小Hi和小Ho偷偷地聊了起來。

小Ho：小Hi，你這學期有選什麼課麼？

小Hi：挺多的，比如XXX1,XXX2還有XXX3。本來想選YYY2的，但是好像沒有先選過YYY1，不能選YYY2。

小Ho：先修課程真是個麻煩的東西呢。

小Hi：沒錯呢。好多課程都有先修課程，每次選課之前都得先查查有沒有先修。教務公布的先修課程記錄都是好多年前的，不但有重複的資訊，好像很多都不正确了。

小Ho：課程太多了，教務也沒法整理吧。他們也沒法一個一個确認有沒有寫錯。

小Hi：這不正是輪到小Ho你出馬的時候了麼！

小Ho：哎？？

我們都知道大學的課程是可以自己選擇的，每一個學期可以自由選擇打算學習的課程。唯一限制我們選課是一些課程之間的順序關系：有的難度很大的課程可能會有一些前置課程的要求。比如課程A是課程B的前置課程，則要求先學習完A課程，才可以選擇B課程。大學的教務收集了所有課程的順序關系，但由于系統故障，可能有一些資訊出現了錯誤。現在小Ho把資訊都告訴你，請你幫小Ho判斷一下這些資訊是否有誤。錯誤的資訊主要是指出現了"課程A是課程B的前置課程，同時課程B也是課程A的前置課程"這樣的情況。當然"課程A是課程B的前置課程，課程B是課程C的前置課程，課程C是課程A的前置課程"這類也是錯誤的。

輸入

第1行：1個整數T，表示資料的組數T(1 <= T <= 5)

接下來T組資料按照以下格式：

第1行：2個整數，N,M。N表示課程總數量，課程編号為1..N。M表示順序關系的數量。1 <= N <= 100,000. 1 <= M <= 500,000

第2..M+1行：每行2個整數，A,B。表示課程A是課程B的前置課程。

輸出

第1..T行：每行1個字元串，若該組資訊無誤，輸出"Correct"，若該組資訊有誤，輸出"Wrong"。

Sample Input

2 2

1 2

2 1

3 2

1 2

1 3

Sample Output

Wrong

Correct

#include

using namespace std;

const int maxa=;

vectorvec[maxa];

queueq;

int rudu[maxa];

int t,n,m,x,y,now;

bool tuopu(){

int cnt=;

while(!q.empty()) q.pop();

for(int i=;i<=n;i++)

if(rudu[i]==) q.push(i);

while(!q.empty()){

now=q.front();

cnt++;

q.pop();

for(size_t i=;i

if(--rudu[vec[now][i]]==)

q.push(vec[now][i]);

}

if(cnt==n) return true;

else return false;

}

int main(){

cin>>t;

while(t--)

{

cin>>n>>m;

memset(rudu,,sizeof(rudu));

for(int i=;i<=n;i++) vec[i].clear();

while(m--)

{

cin>>x>>y;

vec[x].push_back(y);

rudu[y]++;//入度+1

}

if(tuopu()) cout<

else cout<

}

return ;

}

C&num;實作有向無環圖(DAG)拓撲排序

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序,是将G中所有頂點排成一個線性序列,使得圖中任意一對頂點u和v,若邊(u,v)∈E(G),則u線上性序列中出現在 ...

判斷有向無環圖(DAG)

1.拓撲排序 bfs 所有入度為0的先入選. 2.tarjan 1個點1個集合 3.暴力一個點不能重新到達自己

【模闆整合計劃】圖論—有向無環圖 (DAG) 與樹

[模闆整合計劃]圖論-有向無環圖 (DAG) 與樹一:[拓撲排序] 最大食物鍊計數 \(\text{[P4017]}\) #include #include

【拓撲】【寬搜】CSU 1084 有向無環圖 (2016湖南省第十二屆大學生計算機程式設計競賽)

題目連結: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1804 題目大意: 一個有向無環圖(DAG),有N個點M條有向邊(N,M<=105 ...

javascript實作有向無環圖中任意兩點最短路徑的dijistra算法

有向無環圖一個無環的有向圖稱做有向無環圖(directed acycline praph).簡稱DAG 圖.DAG 圖是一類較有向樹更一般的特殊有向圖, dijistra算法摘自 http://w ...

有向無環圖的應用—AOV網和拓撲排序

有向無環圖:無環的有向圖,簡稱 DAG (Directed Acycline Graph) 圖. 一個有向圖的生成樹是一個有向樹,一個非連通有向圖的若幹強連通分量生成若幹有向樹,這些有向數形成生成森林 ...

圖-&gt&semi;有向無環圖-&gt&semi;拓撲排序

文字描述關于有向無環圖的基礎定義: 一個無環的有向圖稱為有向無環圖,簡稱DAG圖(directed acycline graph).DAG圖是一類較有向樹更一般的特殊有向圖. 舉個例子說明有向無環圖 ...

CSU 1804&colon; 有向無環圖拓撲排序圖論

1804: 有向無環圖 Submit Page Summary Time Limit: 5 Sec Memory Limit: 128 Mb Submitted: 716 ...

第十二屆湖南省賽 (B - 有向無環圖 )(拓撲排序+思維)好題

Bobo 有一個 n 個點,m 條邊的有向無環圖(即對于任意點 v,不存在從點 v 開始.點 v 結束的路徑). 為了友善,點用 1,2,…,n 編号. 設 count(x,y) 表示點 x 到點 y ...

随機推薦

Jsp 錯題分析

ArrayList删除元素通過RemoveAt(int index)來删除指定索引值的元素運作時異常都是RuntimeException類及其子類異常,如NullPointerException.I ...

python架構(flask/django/tornado)比較

一.對外資料接口三者作為web架構,都是通過url映射對外的接口 flask:以decorator的形式,映射到函數中 django:以字典形式,映射到函數 tornado: 以字典形式,映射到類中 ...

WPF 基礎到企業應用系列索引

轉自:http://www.cnblogs.com/zenghongliang/archive/2010/07/09/1774141.html WPF 基礎到企業應用系列索引 WPF 基礎到企業應用系 ...

(medium)LeetCode 207&period;Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prer ...

配置Nginx服務

一,安裝之前準備1.nginx依賴: gcc openssl-devel pcre-devel zlib-devel 安裝依賴:yum install gcc openssl-devel pcr ...

javascript語言學習筆記。

js類建立方法 var DogKing = function(dogName){ this.dogName = dogName; }; var myDogKing = new DogKing(&quo ...

bzoj 2212&colon; [Poi2011]Tree Rotations

Description Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some in ...

《深入了解Java虛拟機》-----第8章虛拟機位元組碼執行引擎——Java進階開發必須懂的

概述執行引擎是Java虛拟機最核心的組成部分之一.“虛拟機”是一個相對于“實體機”的概念 ,這兩種機器都有代碼執行能力,其差別是實體機的執行引擎是直接建立在處理器.硬體.指令集和作業系統層面上的,而 ...

APICloud Studio2建立應用報錯和檢出錯誤

今天心血來潮,閑暇時間想做個移動應用app,聽一哥們說APICloud開發app很友善,就查詢了一下,看了之後簡直就是熱血沸騰,我感覺正是我一直要找的工具信心滿滿的開始着手使用,看了一下介紹我選擇了 ...

java 有向無環圖 樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）

java 有向無環圖樹_拓撲排序-有向無環圖（DAG, Directed Acyclic Graph）