Нахождение количества вершин на меньшем или равном расстоянии d от вершины x

Question

Я должен использовать обход графа (я думал о BST), чтобы определить, сколько вершин в g находится на расстоянии v в меньшем или равном N, то есть в путешествии, расстояние которого 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];

У меня трудное время, чтобы сделать эффективное решение в с. Единственный способ, которым я сейчас вижу, это сделать рекурсивный вызов в функции AUX с BST

Answer 1

Если ваши веса неотрицательны, вы можете использовать алгоритм Дейкстры. Вот простой псевдокод. Оно имеет 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 (как вы указали в комментариях), то поиска в ширину будет достаточно.