bool processed[MAXV + 1]; bool discovered[MAXV + 1]; int parent[MAXV + 1]; void initialize_search(graph *g) { int i; for (i = 1; i < g->nvertices; i++) { processed[i] = discovered[i] = false; parent[i] = -1; } } void process_vertex_late(int v) { } void process_vertex_early(int v) { printf("processed vertex %d\n", v); } void process_edge(int x, int y) { printf("processed edge (%d %d)\n", x, y); } void bfs(graph *g, int start) { std::queue <int> q;
int v; int y; edgenode *p;
q.push(start); discovered[start] = true;
while(!q.empty()) { v = q.front(); q.pop(); process_vertex_early(v); processed[v] = true; p = g->edges[v]; while (p != NULL) { y = p->y; if ((processed[y] == false) || g->directed) process_edge(v, y); if (discovered[y] == false) { q.push(y); discovered[y] = true; parent[y] = v; } p = p->next; } process_vertex_late(v); } } void find_path(int start, int end, int parents[]) { if ((start == end) || (end == -1)) printf("\n%d", start); else { find_path(start, parents[end], parents); printf(" %d", end); }
} void connected_components(graph *g) { int c, i;
initialize_search(g);
c = 0; for (i = 1; i <= g->nvertices; i++) if (discovered[i] == false) { c = c + 1; printf("Component %d:", c); bfs(g, i); printf("\n"); }
} int main(int argc, const char * argv[]) { graph *myGraph = (graph *)malloc(sizeof(graph)); //read_graph(myGraph, false); // Or load_graphA(myGraph, false);
print_graph(myGraph);
initialize_search(myGraph);
bfs(myGraph, 1); find_path(1, 4, parent); } |
Algorithms > Graph >