directed-acyclic-graphs

3熱度

1回答

拓撲排序可以使用DFS（具有相反的邊）和使用隊列來完成。 BFS也可以使用隊列完成。在使用隊列進行拓撲排序時，在使用BFS隊列時，存儲和檢索元素的方式之間是否存在任何關係。澄清會有幫助。謝謝。

0熱度

1回答

我正在使用DFS算法編寫在圖中查找循環的代碼。但是，當我打印循環的路徑時，會發生一些非常奇怪的事情。在評論中閱讀我的關注。 #include <iostream> #include "graph.h" #include <stdio.h> using namespace std; int discovered[MAXV+1]; int parent[MAXV+1]; //Prin

0熱度

3回答

如何將struct屬性轉換爲C++中的指針引用？

我有一個JSON格式的DAG，其中每個節點都是一個條目：它有一個名稱和兩個數組。一個陣列用於其他箭頭進入的節點，另一個陣列用於該節點指向的節點（外出箭頭）。因此，舉例來說： { 'id': 'A', 'connected_from' : ['B','C'], 'connects_to' : ['D','E'] } 我有這些節點的集合，所有一起形成DAG。我想

0熱度

1回答

在有向圖中尋找邊緣不相交路徑的最大數量

如何在有向圖中找到最大數量的邊緣不相交路徑。該圖未加權。假設圖就像是跟隨... 1 - 2 , 1 - 3 , 4 - 1 , 5 - 1 所以沒有在圖中，兩個邊分離路徑，4->1->2和5->1->3 我如何解決使用匹配算法的問題？我的問題是...假設我有一個有向圖（可能包含循環）。如果我在一個節點上放置一個'警衛'，它就可以開始它的旅程。即使是其他警衛已經去過的城市，警衛也可以多次訪問

0熱度

1回答

有約束的有向無環加權圖的遍歷

我有一個有向無環加權圖，我想遍歷。一個有效的解決途徑的約束條件是：所有邊的權重之和的路線走過必須是最高可能在圖中，以考慮第二個約束。在所選擇的路線（包括開始和結束頂點）中必須訪問完全N個頂點。通常情況下，圖形將具有大量的頂點和邊，所以嘗試所有可能性不是一種選擇，並且需要相當高效的算法。尋找一些指針或適合這個問題的算法。我知道使用Dijkstra算法很容易實現第一個條件，但我不確定如何合併

1熱度

2回答

從DAG創建強連接組件

我正嘗試從有向無環圖創建強連通組件。輸入是邊緣的形式 1 2 3 5 etc 我需要創建一組邊的最小的外點被添加到給定的圖形使強連接組件的圖形列表... 。任何想法？這裏是什麼，我正在尋找一個例子：給定輸入： 1 3 1 4 2 3 2 4 5 7 5 8 6 8 6 9 輸出將是必要的除了創建強連接的部件邊緣的最小數量。輸出： 3 1 4 5 7 6 8

1熱度

1回答

拓撲排序的有向圖頂點的子集

我正在用C＃4.0編寫一個程序，我已經抽象出以下內容（我提及語言，以便您知道我必須使用哪些庫;沒有第三方庫）：讓S = { s1, s2, s3, ..., sn }。對於所有si，sj在S，i != j，功能f(si, sj)是{ true, false }的元件。調用這個函數f是相當昂貴的，但是應該儘可能少地完成。組給定的T = { t1, t2, t3, ..., tm }S一個非空

2熱度

1回答

找到最有利的貨幣兌換順序

我正在從我的書中進行以下練習：最短路徑算法可應用於貨幣交易。讓c1，c2，...。。。，cn是各種各樣的rencies;例如，c1可能是美元，c2磅和c3里拉。對於任何兩種貨幣ci和 cj，都存在匯率ri，j;這意味着你可以在之間兌換一單位的貨幣單位，購買ri，j貨幣單位cj。這些匯率滿足條件裏，J·RJ，我< 1，因此，如果你與貨幣詞的單位開始，它變成貨幣CJ，然後再轉換回貨幣詞，

4熱度

4回答

等級順序樹遍歷一棵普通的樹，按級別顯示樹級別

我想逐級顯示樹型結構。我當前的代碼執行BFS或級別順序遍歷，但我無法獲得輸出以顯示樹狀結構，如樹狀圖查看當前輸出和預期輸出。我的想法是使用某種類型的計數遍歷從隊列中的同一級別的元素。我怎麼可以這樣做。沒有此功能的原始代碼可以在下面的情況下，有人需要整個實施其他只是看看下面的displayBFS功能的鏈接中找到。 Level Order traversal of a generic tree

0熱度

1回答

向無環圖的Word構建適應和支持

假設我有我的DAWG 3個字：做，點，BOT我都會有這樣的： http://imageshack.us/photo/my-images/703/dawgp.png/ 這個圖告訴「博」也是一個字。其實並非如此。節點'o'是EOW，如果只有路徑來自'd'，而不是'b' 我明顯錯過了smth，但我現在知道是什麼。