SHARE
TWEET

numWithin

a guest Dec 7th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "Graph.h"
  6. #include "Queue.h"
  7.  
  8. /*BFS, but uses a dist array to keep track of the distances of vertices
  9. when they are found. You could use the visited array as the dist array, like
  10. what I did in furthestReachable. */
  11. int numWithin(Graph g, int src, int dist) {
  12.     int n = GraphNumVertices(g);
  13.     int visited[n];
  14.     memset(visited, -1, sizeof(int) * n);
  15.     visited[src] = src;
  16.     int distA[n];
  17.     distA[src] = 0;
  18.     int ret = 0;
  19.     Queue q = QueueNew();
  20.     QueueEnqueue(q, src);
  21.     while (!QueueIsEmpty(q)) {
  22.         int v = QueueDequeue(q);
  23.         if (distA[v] <= dist) {
  24.             ret++;
  25.         }
  26.        
  27.         for (int i = 0; i < n; i++) {
  28.             if (visited[i] == -1 && GraphIsAdjacent(g, i, v)) {
  29.                 QueueEnqueue(q, i);
  30.                 visited[i] = v;
  31.                 distA[i] = distA[v] + 1;
  32.                
  33.             }
  34.         }
  35.     }
  36.     QueueFree(q);
  37.     return ret;
  38. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top