無環圖演算法
Ⅰ 請教無向無環圖最長路徑演算法
無向無環圖就是樹，
從根出發：
如果是計算最多的路徑，就用廣度優先（層次遍歷）就可以了，最後訪問的頂點一定是最多的路徑的
如果是計算最長的路徑長度，直接將上面的演算法改一下，每個頂點時記下前面的來路的值加上現在的，就可以求出最大值
或者直接用Dijkstra 演算法就可以了
Ⅱ 一個有向無環圖的拓撲排序序列是唯一的么
AOV網路構造的拓撲序列的拓撲排序演算法主要通過以下兩個步驟循環，直到沒有度為0的頂點，選擇度為0的頂點，輸出，從網路中刪除這個頂點和所有向外的邊。
在循環結束時，如果輸出的頂點數小於網路中的頂點數，則會輸出「loop」信息，否則，輸出頂點序列就是拓撲序列。
利用AOV網路構建拓撲序列的實際意義是：如果按照拓撲序列的頂點順序，在啟動每個活動時，可以保證其所有前體活動都已完成，從而使整個項目有序進行，不會產生沖突。
(2)無環圖演算法擴展閱讀：
拓撲排序是一個DAG（有向無環圖）的所有頂點的線性序列。序列必須滿足以下兩個條件：每個頂點只出現一次。如果從頂點A到頂點B有一條路徑，那麼在序列中頂點A出現在頂點B之前。
拓撲排序通常用於確定事物在一組依賴項中發生的順序。例如，在日常工作中，一個項目可能分為A，B，C和D，但取決於B和D和C取決於D計算項目的順序，關系集可以拓撲排序產生一個線性序列，和第一個任務是需要首先完成。
Ⅲ 怎樣求一個有向無環圖的拓撲排序序列總數
(1)
設對有向無環圖G=,求得它的一個拓撲序列為S,
初始化S為空,然後每次從G中選取一個入度為0的點v,將v插入到S的尾部,再在G中刪除點v,並刪除所有以v為弧尾的邊(即由v引出去的邊),如此循環,直到圖G中的V為空集時結束.
2
1 2 3 4 5 6 7 8
1 3 2 4 5 7 6 8
3 1 4 2 5 6 7 8
3 1 2 5 4 7 8 6
Ⅳ 無向圖中查找環的演算法有哪些
比較直觀的辦法是，從初始結點 S 開始，用深度優先的方法遍歷圖的結點，如果在這個過程中，你遇到了一個先前就已經發現過的結點（假定它叫 V），說明存在一個環。
如果你想輸出這個環，那麼就從 V 沿路返回，直到又遇到 V，途中經過的所有結點就組成了這個環。
Ⅳ 有誰知道能解釋一下有向無環圖(DAG)么怎麼用程序做出來，及怎麼應用到經濟學實證上
我們說區塊鏈目前還不成熟，有各種各樣的問題，比如說處理速度慢、手續費高昂、存在安全隱患等等，這些都是用戶最直觀的體驗，體驗不是太好。區塊鏈還有一個問題，那就是高並發問題。
高並發問題是怎麼回事呢，我們簡單說一下。高並發是計算機領域的問題，簡單來講，高並發問題就是系統無法順利同時運行多個任務。
很多任務同時運行，一大堆用戶涌進來，系統承受不住這么多的任務，會出現高並發問題，你的系統就卡住了，就好比春運時候，12306系統總是卡住，有可能就是高並發問題造成的。
傳統互聯網尚且存在高並發問題，區塊鏈網路自然也存在這個問題，畢竟區塊鏈的成熟程度比起傳統互聯網，還有很大的差距。但是，如果沒有安全、可靠和高效的公鏈，整個區塊鏈產業的發展都將受到嚴重製約，應用落地也是空談。
在這種背景下，DAG 技術就被提出來了，DAG 的全稱是「Directed Acyclic Graph」，中文翻譯為「有向無環圖」。
DAG有向無環圖是怎麼回事呢，它到底能起到什麼作用呢？我們下面解釋一下。
一、DAG：一個新型的數據結構
DAG，中文名字叫「有向無環圖」，從字面意思看，「有向"就是說它是有方向的，
「無環」就是說它是沒有環路的、不能形成閉環的。所以，DAG其實是一種新型的數據結構，這個數據結構是有方向的，同時又是不能形成閉環的。
傳統區塊來講，我們總是以「區塊」為單位，一個區塊里往往包含了多筆交易信息。而在DAG中，沒有區塊的概念，而是以「單元」為單位，每個單元記錄的是單個用戶的交易，組成的單元不是區塊，而是一筆筆的交易，這樣一來，可以省去打包出塊的時間。
簡單來說，區塊鏈和DAG有向無環圖最大的區別就是：區塊鏈是一個接一個的區塊來存儲和驗證交易的分布式賬本，而DAG則是把每筆交易都看成一個區塊，每一筆交易都可以鏈接到多個先前的交易來進行驗證。
二、DAG 的工作原理
傳統區塊鏈上，就拿比特幣來講，它是單鏈式的結構，區塊與區塊之間按照時間戳的先後順序排列開來（如圖一），數據記錄在一條主鏈上。用不太恰當的比喻來講，這個
「單鏈式」結構是一條一字排列的鏈。
區塊鏈只有一條單鏈，打包出塊就無法並發執行。新的區塊會加入到原先的最長鏈之上，所有節點都以最長鏈為准，繼續按照時間戳的順序無限蔓延下去。而對於DAG來講，每個新加入的單元，不僅只加入到最長鏈的一個單元，還要加入到之前所有的單元（如圖二）。
舉個例子：假設我發布了一個新的交易，此時DAG結構已經有2個有效的交易單元，那麼我的交易單元會主動同時鏈接到前面的2個之中，去驗證並確認，直到鏈接到創世單元，而且，上一個單元的哈希會包含到自己的單元裡面。
換句話說，你要想進行一筆交易，就必須要驗證前面的交易，具體驗證幾個交易，根據不同的規則來進行。這種驗證手段，使得DAG可以非同步並發的寫入很多交易，並最終構成一種拓撲的樹狀結構，極大地提高擴展性。
依據DAG有向無環圖，每一筆交易都直接參與了維護全網。當交易發起後，直接廣播全網，跳過礦工打包區塊階段，這樣就省去了打包交易出塊的時間，提升了區塊鏈處理交易的效率。
隨著時間遞增，所有交易的區塊鏈相互連接，形成圖狀結構，如果要更改數據，那就不僅僅是幾個區塊的問題了，而是整個區塊圖的數據更改。DAG這個模式相比來說，要進行的復雜度更高，更難以被更改。
總結一下，DAG作為一種新型的去中心化數據結構，它屬於廣義區塊鏈的一種，具備去中心化的屬性，但是二者的不同之處在於：
區塊鏈組成單元是Block（區塊），DAG組成單元是TX（交易）。
區塊鏈是單線程，DAG是多線程。
區塊鏈所有交易記錄記在同一個區塊中，DAG每筆交易單獨記錄在每筆交易中。
區塊鏈需要礦工，DAG不需要礦工。
三、 DAG 的代表：IOTA
DAG當前的代表項目，最知名的無疑就是 IOTA。可以說，正是因為IOTA這個幣種在 2017年下半年沖進市值排行第四位，才使人們真正認識到了它的底層技術：DAG有向無環圖。
IOTA在DAG有向無環圖的基礎上提出了「纏結」概念，在IOTA裡面，沒有區塊的概念，共識的最小單位是交易。每一個交易都會引用過去的兩條交易記錄哈希，這樣前一交易會證明過去兩條交易的合法性，間接證明之前所有交易的合法性。這樣一來， 就不再需要傳統區塊鏈中的礦工這樣少量節點來驗證交易、打包區塊，從而提升效率，節省交易費用。
四、 DAG 的現狀
盡管理論上來講，DAG有向無環圖能夠彌補傳統區塊鏈的一些弊端，但是目前並不成熟，應用到數字貨幣領域的時間也比較短，還比較年輕 。
它沒有像比特幣那般經過長達10年的時間來驗證整個系統的安全性，也沒有像以太坊那般實現了廣泛的應用場景。不過，現在有些聲音提出要採用「傳統區塊鏈+DAG」的數據結構，但是還沒有非常突出的案例，這里就不多說了。
總結一下，本節我們介紹了區塊鏈的衍生技術：DAG有向無環圖，這是一種全新的數據結構，可以對區塊鏈處理交易的效率、並發力達到顯著的提升。
Ⅵ 請教無向無環圖最長路徑演算法
無向無環圖就是樹，
從根出發：
如果是計算最多的路徑，就用廣度優先（層次遍歷）就可以了，最後訪問的頂點一定是最多的路徑的
如果是計算最長的路徑長度，直接將上面的演算法改一下，每個頂點時記下前面的來路的值加上現在的，就可以求出最大值
或者直接用Dijkstra
演算法就可以了
Ⅶ 判斷給定的圖是否是有向無環圖1
判斷無向圖中是否存在迴路（環）的演算法描述 如果存在迴路，則必存在一個子圖，是一個環路。環路中所有頂點的度>=2。 演算法： 第一步：刪除所有度<=1的頂點及相關的邊，並將另外與這些邊相關的其它頂點的度減一。 第二步：將度數變為1的頂點排入隊列，並從該隊列中取出一個頂點重復步驟一。 如果最後還有未刪除頂點，則存在環，否則沒有環。 有向圖是否有環的判定演算法，主要有深度優先和拓撲排序2中方法。 拓撲排序，如果能夠用拓撲排序完成對圖中所有節點的排序的話，就說明這個圖中沒有環，而如果不能完成，則說明有環。
Ⅷ 遍歷的遞歸與非遞歸演算法，判斷是否是有向無環圖，並輸
基本思想：首先從圖中某個頂點v0出發，訪問此頂點，然後依次從v0相鄰的頂點出發深度優先遍歷，直至圖中所有與v0路徑相通的頂點都被訪問了；若此時尚有頂點未被訪問，則從中選一個頂點作為起始點，重復上述過程，直到所有的頂點都被訪問。可以看出深度優先遍歷是一個遞歸的過程。
Ⅸ 建立有向無環圖的存儲結構，設計實現求拓撲排序的演算法
拓撲排序常見的有兩種演算法，一種是反復找入度為0的點，一種是利用DFS時的時間戳來求拓撲序
下面的程序時後一種演算法，圖用臨界表存儲，在遍歷的同時，完成了拓撲排序
#include<cstdio>
#include<cstring>
struct edgetype
{
int to;
edgetype *next;
} edge[1000000];
edgetype *link[10000];
int n , m, DFStime;
int reach[10000], order[10000];
bool DFS(int now)
{
if (reach[now] == 2) return true;
if (reach[now] == 1) return false;
reach[now] = 1;
for (edgetype *e = link[now]; e; e = e -> next)
if (!DFS(e -> to)) return false;
reach[now] = 2;
order[DFStime++] = now;
return true;
}
int main()
{
scanf("%d%d" ,&n, &m);
for (int i = 0; i < m; ++i)
{
int a,b;
scanf("%d%d",&a,&b);
edge[i].to = b;
edge[i].next = link[a];
link[a] = edge + i;
}
memset(reach , -1, sizeof(reach));
DFStime = 0;
for (int i = 0; i < n; ++i)
if (reach[i] == -1)
if (!DFS(i))
{
puts("There is a cycle in the graph!");
return 0;
}
for (int i = n - 1; i >= 0; --i)
printf("%d ", order[i]);
}
Ⅹ 編寫一個演算法，給有向無環圖G中每個頂點賦以一個整數序號，並滿足以下條件
拓撲排序
先統計所有點的入度。
然後把當前剩下的點中入度為0的點編號，把這個點刪去，更新與它相鄰的點的入度。重復直到所有點處理完