/* bfs-dfs.c Generic implementation of graph traversal: breadth-first/depth-first search */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include #include "bfs-dfs.h" #include "queue.h" /* [[[ graph_arrays_cut */ bool processed[MAXV+1]; /* which vertices have been processed */ bool discovered[MAXV+1]; /* which vertices have been found */ int parent[MAXV+1]; /* discovery relation */ /* ]]] */ int entry_time[MAXV+1]; /* time of vertex entry */ int exit_time[MAXV+1]; /* time of vertex exit */ int time; /* current event time */ bool finished = false; /* if true, cut off search immediately */ /* [[[ init_search_cut */ void initialize_search(graph *g) { int i; /* counter */ time = 0; for (i = 0; i <= g->nvertices; i++) { processed[i] = false; discovered[i] = false; parent[i] = -1; } } /* ]]] */ /* [[[ bfs_cut */ void bfs(graph *g, int start) { queue q; /* queue of vertices to visit */ int v; /* current vertex */ int y; /* successor vertex */ edgenode *p; /* temporary pointer */ init_queue(&q); enqueue(&q, start); discovered[start] = true; while (!empty_queue(&q)) { v = dequeue(&q); process_vertex_early(v); processed[v] = true; p = g->edges[v]; while (p != NULL) { y = p->y; if ((!processed[y]) || g->directed) { process_edge(v, y); } if (!discovered[y]) { enqueue(&q,y); discovered[y] = true; parent[y] = v; } p = p->next; } process_vertex_late(v); } } /* ]]] */ /* [[[ eclass_cut */ int edge_classification(int x, int y) { if (parent[y] == x) { return(TREE); } if (discovered[y] && !processed[y]) { return(BACK); } if (processed[y] && (entry_time[y]>entry_time[x])) { return(FORWARD); } if (processed[y] && (entry_time[y]edges[v]; while (p != NULL) { y = p->y; if (!discovered[y]) { parent[y] = v; process_edge(v, y); dfs(g, y); } else if (((!processed[y]) && (parent[v] != y)) || (g->directed)) { process_edge(v, y); } if (finished) { return; } p = p->next; } process_vertex_late(v); time = time + 1; exit_time[v] = time; processed[v] = true; } /* ]]] */ /* [[[ find_path_cut */ 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); } } /* ]]] */