广度优先搜索 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 applications
provided 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 at
https://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;