深度优先搜索 C 代码

2016-08-01 11:46:14 暂无评论阳光倾城算法与数据结构 738

深度优先搜索 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 */

                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);

        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;