graph-algorithm

0熱度

2回答

我在搞清楚圖的工作方式（DFS）方面是全新的。我已經閱讀了很多關於如何使用DFS構建迷宮路徑尋找解算器的教程，並且有一部分我沒有得到。我如何在世界上找出誰是頂點的鄰居？ Forinstens我有這個迷宮： maze 我已經把所有的字符串放到一個名爲'names'的二維數組中。所以，如果我寫forinstens： names[0,0] // it contains the string + 如果

1熱度

2回答

Dijkstra的算法和循環

它在書中說「Dijkstra算法只適用於有向非循環圖」。看來，只要沒有負循環，該算法也適用於循環圖。那是對的嗎？編輯1：書「Grokking Algorithms」-Aditya Bhargava。第7章第122頁。

1熱度

1回答

具有彩色邊緣的圖形中具有最少改變次數的路徑

我有一個帶有彩色邊緣的有向圖（紅色爲&藍色），可能包含循環。問題是寫一個給定兩個頂點（s，t）的算法，找到s和t之間顏色變化最小的路徑（如果存在這樣的路徑）。（我創建了一個新的圖，其中每個頂點對應於前一個圖的邊，並且包含邊的顏色，例如：if（1,2）是（1/2）是新圖中的一個頂點，我連接了「相鄰邊」頂點，新圖中改變顏色的邊的權重爲1，同一顏色變換爲0 ）。我正在尋找線性時間（V和E）的解決方案

1熱度

1回答

for循環之後的if語句是什麼意思？

這是來自Kattis的編程挑戰之一，我已經解決了它，所以我想看看別人如何解決它。所以，我碰到這一塊的代碼，但我無法理解這兩個具體線路： for(i=0;i<N;i++) if(inTree[i]) 和 for(j=0;i<N;j++) if(inTree[j]) 我不明白如何將這些if語句在此算法的工作。是否應該檢查兩個節點之間是否存在鏈接？代碼如下： #include <stdio.h>

0熱度

1回答

爲什麼我的底部複雜度不是O（n^3）

從我所學到的，自下而上的複雜度應該是n^3，但是，我的結果顯示它幾乎就像O（n）。我一直在檢查這些代碼很多次，但仍然不知道爲什麼它不是複雜性。我在這裏想念什麼？ /** * Using the bottom-up approach to fill in the table m and s for matrices P * @param P an array storing the matric

0熱度

1回答

如何將樹節點合併到一個節點中

希望我的問題不會重複。我想知道是否存在將樹中的某些節點合併到新樹中的算法，以便新樹中的節點由舊樹中的一些節點組成？爲了解釋我的想法，我畫了一張圖來解釋這個問題。輸入：原始樹。輸出：一棵新樹。有與新樹必須滿足以下條件：節點的新樹的數量應該是一個固定的數ķ。新樹中的每個節點必須由原始樹中的節點組成。例如，第二個圖中的節點A包含第一個圖的節點1,3和4。 secod圖中的節點D包含第一個圖中

0熱度

2回答

如何使用BFS獲取圖形的最大深度

當我在圖形上使用BFS算法時，我嘗試獲取圖形的最大深度。但我不知道從哪裏把我的遞增在這個算法： FUNCTION BFS(G,s) BEGIN FOR any vertex v of G DO Mark[v] ← False END FOR Mark[s] ← True F ← Empty Queue enqueue(

6熱度

2回答

Dijkstra算法與切比雪夫距離

我一直在使用Dijkstra算法來查找由普林斯頓大學算法第2部分給出的圖形API中的最短路徑，並且我已經找到了如何找到具有切比雪夫距離的路徑。儘管切比雪夫可以移動到節點的任何一側，但成本只有1，但對總成本沒有影響，但根據圖表紅圈，路徑尋找線爲什麼沒有移動曲折而沒有直行？如果我使用A *算法，同樣的事情會重複嗎？

0熱度

1回答

檢測圖中的相互邊緣

我有一個圖的鄰接列表表示，但它不是對稱的，即，。如果節點A的邊緣爲B，則B與A的邊緣不對。我想這將是一個方向圖（二叉圖）。什麼是檢測節點中所有雙向路徑的好方法。我知道我可以使用DFS來檢測從節點到圖的另一個節點的路徑。我想我正在尋找的是雙向DFS，其中只考慮了雙向邊緣。因此，一種方法是查看節點的鄰居並找出這是否是雙向關係。但是，爲此，我需要遍歷此相鄰節點的所有直接連接，並查看第一個節點是否也是

2熱度

1回答

NP完整嗎？

決策問題：對於給定的圖G和數字「a」，「b」，需要回答是否存在具有至少'b'大小的累積鄰域的一組'a'頂點。我們如何證明這個問題是NPC？