CODEWITHSUNDEEP
calgorithmgraphgraph-traversal
user6540722
user6540722

Reputation:

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

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 which the distance is N or 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

Upvotes: 0

Views: 355

Answers (2)

djawadmain
djawadmain

Reputation: 93

You can use BFS with O(n + m) and then find vertexes in distance of n-1 or less than n-1 And all edges connected to this vertexes have distance <= n And if you have a tree we can do another things

Upvotes: 0

md5
md5

Reputation: 23727

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.

Upvotes: 1

Related Questions