graph-algorithm

0熱度

1回答

我剛剛看到一個問題的解決方案，修改Dijkstra以獲得具有最大K顏色邊的最短路徑。我想知道如果我們想要用顏色節點而不是邊緣找到最短路徑，我們將如何修改Dijkstra來實現這個訣竅？我想到的是，在Dijkstra之上，我添加了一個整數變量，讓我說我。然後製作一張地圖來記錄需要多少顏色的節點才能到達那裏，並且如果有通過較少顏色節點的方式，請更新它。我們將採用最小顏色節點的路徑。但是這似乎有什麼錯

0熱度

2回答

A *啓發式法求解N-puzzle的比較

我想用三種不同的啓發式函數來解決使用A *算法的N-puzzle問題。我想知道如何比較每種啓發式的時間複雜性。我使用的啓發式是：曼哈頓距離，曼哈頓距離+線性衝突，N-max交換。特別是對於8個難題和15個難題。

0熱度

1回答

圖中的禁止路徑

我們提供了有向圖（數據流圖）。我們希望禁止數據到達圖的某些節點，這意味着我們將禁止刪除路徑，但必須保持圖形連接。我提出了一個簡單的例子來使問題清晰：讓我們如下圖：一個------>乙--------> C- -------> D 我想禁止數據到達節點C，所以邊緣BC將被刪除。同時，我希望數據達到D.因此，將創建一個來自B-D的新邊緣。上面的任務是否有一個有效的算法？謝謝。

0熱度

1回答

使用BFS和DFS查找圖表中兩個節點之間的路徑

我正在關注以下鏈接。 DFS：http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DepthFirstPaths.java.html 其中pathTo方法是這樣的 public Iterable<Integer> pathTo(int v) { validateVertex(v); if (!hasPathTo(v

3熱度

1回答

最長最短路徑（不完全）

對於我的學士論文，我遇到了以下問題（解決這個問題可能對論文的實際問題有用）。我有一個加權有向圖G頂點V和V兩個頂點，開始s和目的地t。我可以刪除至多k頂點。我需要找到頂點，刪除頂點將使調整圖中從s到t的最短路徑的成本（長度）最大化。我想，這個問題本來應該在文獻中討論過，但是，我沒有設法找到相關的文章。我會很感激有關文獻的任何鏈接。

-1熱度

1回答

如何檢查無向圖中循環的存在性？

#include <bits/stdc++.h> using namespace std; int n,m; vector<int> adj[51]; int visited[51]; bool flag; void dfs(int i,int parent){ vector<int>::iterator it;

0熱度

1回答

Python從邊緣流連接的組件

我想從一個邊緣流找到連接組件在輸入我有一個這樣的流： edges_in : [(e1,e2),(e2,e3),(e3,e1),(e5,e6)] edges_out: : [(e1,e2)] 我正在尋找一種算法有輸出： connected_edges : [[(e2,e3),(e3,e1)],[(e5,e6)]] 而從這個名單connected_edges有： connected_nod

1熱度

1回答

遞歸函數不返回到直接調用者

我已經寫了一個遞歸實現，以找到某些特定的路徑給出了一些n * n矩陣，使用我在stackoverflow上找到的這個psuedocode。我已經構建兩個數組：路徑權重陣列保持該邊緣值在我們的圖形從一個頂點到另一個（細胞基質對相鄰小區中的矩陣）鄰接陣列，用於在我們路徑中的每個索引重量陣列因爲某些原因，但是當我的遞歸函數返回它不會返回到直接調用者？我的實現： // find paths of

2熱度

1回答

蟒蛇圖形工具訪問頂點屬性

對於我當前的項目，我想使用圖形工具庫，因爲他們聲稱是最快的：https://graph-tool.skewed.de/performance。我有一些算法（最短路徑等）在真正的大型網絡上運行，所以越快越好！第一個問題：這個說法'最快'是真的嗎？ ;）雖然試圖構建符合我需求的圖形工具圖，但我發現無法以高效的方式訪問頂點屬性。也許我錯過了什麼？我的問題是現在，函數「getVertexFromGr

2熱度

1回答

拆分圖算法

圖有n個頂點和m個邊。圖形開始連接，然後按照它們出現在列表中的順序刪除邊線。在這個過程結束時，圖形被斷開。因此，在邊緣列表中存在特定的邊緣，使得在去除邊緣之前，有一個連接的分量超過n/4個頂點的頂點。刪除該邊後，圖中沒有超過n/4個頂點的連通分量。我該如何去設計最佳算法來找到這個邊緣。我是否剛剛開始刪除邊，然後每次遍歷圖來檢查最大連接組件是否滿足要求？這在O（nm）時間運行，但我覺得必須有一些