SHARE
TWEET

Untitled

a guest Dec 7th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "Graph.h"
  5. #include "Queue.h"
  6.  
  7. int furthestReachable(Graph g, int src) {
  8.     if (g == NULL) {
  9.         return -1;
  10.     }
  11.  
  12.     int nV = GraphNumVertices(g);
  13.     int dist[nV];
  14.  
  15.     // Init dist array setting src to be 0
  16.     for (int i = 0; i < nV; i++) {
  17.         if (i == src) {
  18.             dist[i] = 0;
  19.         }
  20.         else {
  21.             dist[i] = -1;
  22.         }
  23.     }
  24.  
  25.     Queue q = QueueNew();
  26.     QueueEnqueue(q, src);
  27.     int max = src;
  28.     while (QueueIsEmpty(q) == false) {
  29.         int v = QueueDequeue(q);
  30.         for(int i = 0; i < nV; i++) {
  31.             if (GraphIsAdjacent(g, i, v) == true && dist[i] == -1) {
  32.                 dist[i] = dist[v] + 1;
  33.                 if (dist[i] >= dist[max]) {
  34.                     max = i;
  35.                 }
  36.                 QueueEnqueue(q, i);
  37.             }
  38.         }
  39.     }
  40.  
  41.     QueueFree(q);
  42.     return max;
  43. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top