查找顶点 x 小于或等于距离 d 内的顶点数量

Question

我必须使用图遍历（我正在考虑BST）来确定g中有多少个顶点在小于或等于N的距离v中，这就是距离为N或更少边的旅行。

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 在 aux 函数中进行递归调用

Answer 1

如果你的权重是非负的，你可以使用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（正如你在评论中指出的那样），那么广度优先搜索就足够了。