 广度优先搜索 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;        }}bfs(graph *g, int start){    queue q;            /* queue of vertices to visit */    int v;              /* current vertex */    int i;              /* counter */    init_queue(&q);    enqueue(&q,start);    discovered[start] = TRUE;    while (empty(&q) == FALSE) {        v = dequeue(&q);        process_vertex(v);        processed[v] = TRUE;        for (i=0; i<g->degree[v]; i++)             if (valid_edge(g->edges[v][i]) == TRUE) {            if (discovered[g->edges[v][i]] == FALSE) {                enqueue(&q,g->edges[v][i]);                discovered[g->edges[v][i]] = TRUE;                parent[g->edges[v][i]] = v;            }            if (processed[g->edges[v][i]] == FALSE)                 process_edge(v,g->edges[v][i]);            }    }}/*bool valid_edge(edge e){    if (e.residual > 0) return (TRUE);    else return(FALSE);}*/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; ```