Finding the number of vertices within less or equal distance d of vertex x

Question

I have to use a graph traversal ( i was thinking of BST) to determine how many vertex in g are in a distance of v in less or equal to N , this is , a travel wich the distance is N ou less edges.

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

I have this struct to work with :

#define MAX 100

typedef int WEIGHT;

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

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

I'm having a difficult time to make a efficient solution in c. The only way i'm seeing right now its to make a recursive call in an aux function with the BST

Answer 1

If your weights are nonnegative, you can use Dijkstra algorithm Here is a simple pseudo-code. It has a O(n^2) time complexity (n = number of nodes).

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

If all your weights are equal to 1 (as you are pointing out in comments), then a breadth-first search will be enough.