在頂點x的較小或相等距離d內找到頂點數

我必須使用圖遍歷（我在考慮BST）來確定g中有多少頂點在v中的距離小於或等於N ，這是一個至少距離少於邊緣的旅行。在頂點x的較小或相等距離d內找到頂點數

int succN (Grafo g, int v, int N)

我有這樣的結構的工作與：

#define MAX 100 

typedef int WEIGHT; 

struct edge { 
    int dest; 
    WEIGHT weight; 
    struct edge *next; 
}; 

typedef struct edge Edge; 
typedef struct edge *GraphL[MAX];

我有困難的時候，使在C有效的解決方案。我現在看到它的唯一方法是通過BST在輔助功能中進行遞歸調用。

來源

2016-12-25 Ze Pedro Resende

你可以探索Dijkstra的算法。根據循環條件，您可以找到到達目標節點的最短路徑，而不必訪問所有節點;或訪問所有節點（一次），並從一開始就找到每個節點的最短距離。這兩種用法都是一種有效的算法 –

@WeatherVane在這種特殊情況下，權重爲1，因爲它沒有加權圖。我仍然可以使用Dijkstra的algorhim嗎？ –

是的，你可以做。 –

如果您的權重非負，可以使用Dijkstra算法這是一個簡單的僞代碼。它具有O(n^2)時間複雜度（n =節點數量）。

ans = 0 
dist[0 .. n-1, None] = {INF, ..., INF} 
dist[v] = 0 
iterate n times 
    best = None 

    for each node u 
     if not seen[u] and dist[u] < dist[best] 
     best = u 

    if dist[best] > N 
     break 

    seen[best] = true 
    ans++ 
    for each edge from best (going to v, of weight w) 
     if dist[best] + w < dist[v] 
     dist[v] = dist[best] + w 

return ans

如果所有的權重等於1（因爲你是在評論中指出），那麼breadth-first search就足夠了。

來源

2016-12-26 13:41:33 md5

在頂點x的較小或相等距離d內找到頂點數

回答

相關問題