 深度优先搜索 C 代码 ` `

``` 深度优先搜索 C 代码 /*  bfs-dfs.c    A generic implementation of graph traversal: breadth-first    and depth-first search    begun: March 27, 2002    by: Steven Skiena*//*Copyright 2003 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applicationsprovided this copyright notice remains intact and unchanged.This program appears in my book:"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.This book can be ordered from Amazon.com athttp://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/*/#include "bool.h"#include "graph.h"#include "queue.h"bool processed[MAXV];   /* which vertices have been processed */bool discovered[MAXV];  /* which vertices have been found */int parent[MAXV];   /* discovery relation */bool finished = FALSE;  /* if true, cut off search immediately */initialize_search(graph *g){        int i;                          /* counter */        for (i=1; i<=g->nvertices; i++) {                processed[i] = discovered[i] = FALSE;                parent[i] = -1;        }}/*bool valid_edge(edge e){    if (e.residual > 0) return (TRUE);    else return(FALSE);}*/dfs(graph *g, int v){    int i;              /* counter */    int y;              /* successor vertex */    if (finished) return;       /* allow for search termination */    discovered[v] = TRUE;    process_vertex(v);    for (i=0; i<g->degree[v]; i++) {        y = g->edges[v][i];        if (valid_edge(g->edges[v][i]) == TRUE) {            if (discovered[y] == FALSE) {                parent[y] = v;                dfs(g,y);            } else                if (processed[y] == FALSE)                    process_edge(v,y);        }        if (finished) return;    }    processed[v] = TRUE;}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);    }}//graph.h#define MAXV        100     /* maximum number of vertices */#define MAXDEGREE   50      /* maximum outdegree of a vertex */typedef struct {    int edges[MAXV+1][MAXDEGREE];   /* adjacency info */    int degree[MAXV+1];     /* outdegree of each vertex */    int nvertices;          /* number of vertices in the graph */    int nedges;         /* number of edges in the graph */} graph; ```