/***************************************************************************** * Solution for Lab Test 1 * * Author: Abhijit Das * * Date: October 06, 2009 * *****************************************************************************/ #include #include #define MAXCITY 100 /* Part 1: Use adjacency matrix representation */ void readGraph ( int A[MAXCITY][MAXCITY], int *n, int *e ) { int i, j, u, v; /* Read number of vertices and number of edges */ scanf("%d%d", n, e); /* Initialize adjacency matrix */ for (i=0; i<*n; ++i) for (j=0; j<*n; ++j) A[i][j] = 0; /* Read edges one by one */ for (i=0; i<*e; ++i) { scanf("%d%d", &u, &v); /* Read vertices */ A[u][v] = A[v][u] = 1; /* Create links */ } } /* Part 2: Find the busiest airport */ int busiest ( int A[MAXCITY][MAXCITY], int n ) { int i, j, max, u, deg; /* Find the node with highest degree */ /* Initialize max and index of max */ max = u = -1; for (i=0; i max) { max = deg; u = i; } } return u; } /* Part 3: Find route between u and v by DFS */ int existsRoute ( int A[MAXCITY][MAXCITY], int n, int u, int v ) { int S[MAXCITY], TOS, visited[MAXCITY], i, j; /* initially no vertices are visited */ for (i=0; i= 0) { /* v reached from u */ if (S[TOS] == v) return 1; /* read top of stack and pop */ i = S[TOS--]; /* push all unvisited neighbors of i */ for (j=0; j= 0) { /* read top of stack and pop */ i = S[TOS--]; /* push all unvisited neighbors of i */ /* also keep track of the count of visited vertices */ for (j=0; j