图的深度搜索和广度搜索

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"  //在BFS搜索算法中会用到队列

//定义图的节点结构体
typedef struct _graph_node_ {
    int data;//存储本结点的值或序号
    struct _graph_node_ *next;//存储下一节点地址
}gnode_t;

//定义图的入口结构体，存储图所有信息
typedef struct _adjlist_graph_ {
    gnode_t *relation;//存储图中结点及其边的关系，头节点
    int vn;//存储结点的数目
    char *visit;//用于存储在搜索算法中需要的标志位
}graph_t;

gnode_t *create_gnode(int value);//创建结点
graph_t *graph_init(int vn);//图的初始化
int graph_destroy(graph_t *graph);//图的销毁
int graph_add_adge(graph_t *graph, int vx, int vy);//在两结点间添加一条边
int graph_show(graph_t *graph);//展示图中结点间的关系
int graph_first_adj(graph_t *graph, int vn);
int graph_next_adj(graph_t *graph, int vx, int vy);
int graph_dfs(graph_t *graph, int start);//深度搜索
int graph_bfs(graph_t *graph, int start);//广度搜索

int main(int argc, char *argv[])
{
    graph_t *graph = NULL;//定义图的入口
    char adges[][2] = {//图中互连结点，即0结点连接1、3结点，1结点连接2、3结点，2结点连接4结点
        {0,1},
        {0,3},
        {1,3},
        {1,2},
        {2,4},
    };
    int i;
    
    graph = graph_init(5);//图初始化，含有5个结点
    
    for (i = 0; i < sizeof(adges) / sizeof(*adges); i++){
        graph_add_adge(graph, adges[i][0], adges[i][1]);//将边的信息添加到图中
    }
    
    graph_show(graph);
    
    puts("DFS:");
    graph_dfs(graph, 0);
    puts("\b ");
    
    puts("BFS:");
    graph_bfs(graph, 0);
    puts("\b ");
    
    graph_destroy(graph);
    
    return 0;
}

//图的初始化
graph_t *graph_init(int vn)
{
    graph_t *graph = NULL;//定义图的入口地址
    
    graph = malloc(sizeof(*graph));//申请图的入口结构体所需要的堆内存空间
    
    graph->relation = malloc(sizeof(gnode_t) * vn);//申请vn个结点所需要的堆内存空间
    memset(graph->relation, 0, sizeof(gnode_t) * vn);//清空申请到的堆内存空间
    
    graph->visit = malloc(sizeof(char) * vn);//申请标志位所需内存
    memset(graph->visit, 0, sizeof(char) *vn);
    
    graph->vn = vn;//图中结点个数目
    
    return graph;//返回图的入口地址
}

//图的销毁，一定要注意销毁顺序，否则会产生内存泄露
int graph_destroy(graph_t *graph)
{
    gnode_t *p = NULL;
    gnode_t *tmp = NULL;
    int i;
    
    for (i = 0; i < graph->vn; i++) {
        p = graph->relation[i].next;//从图的第一个结点开始，逐个释放内存
        while (NULL != p) {
            tmp = p;
            p = p->next;
            free(tmp);
        }
    }
    free(graph->relation);//
    free(graph->visit);
    free(graph);//逐个释放，最后释放图的入口结构体内存
    
    return 0;
}

//给图中的结点添加边的关系
int _graph_add_adge1_(graph_t *graph, int vx, int vy)
{
    gnode_t *new = NULL;
    gnode_t *p = graph->relation + vx;
    
    /* locate */
    while (NULL != p->next && p->next->data < vy)
        p = p->next;
    
    if (NULL == p->next || p->next->data > vy) {
        new = create_gnode(vy);
        new->next = p->next;
        p->next = new;
    }
    
    return 0;
}

int graph_add_adge(graph_t *graph, int vx, int vy)
{
    if (vx < 0 || vx >= graph->vn || vy < 0 || vy >= graph->vn)
        return -1;
    
    _graph_add_adge1_(graph, vx, vy);
    _graph_add_adge1_(graph, vy, vx);
    
    return 0;
}

int graph_show(graph_t *graph)
{
    gnode_t *p = NULL;
    int i;
    
    for (i = 0; i < graph->vn; i++) {
        p = graph->relation[i].next;
        
        printf("V%d: ", i);
        while (NULL != p) {
            printf(" V%d,", p->data);
            p = p->next;
        }
        puts("\b ");
    }
    return 0;
}

//创建结点
gnode_t *create_gnode(int value)
{
    gnode_t *p = NULL;
    
    p = malloc(sizeof(*p));//申请结点所需的内存
    p->data = value;//存储结点的值
    p->next = NULL;
    
    return p;//返回结点的地址
}

int graph_first_adj(graph_t *graph, int vn)
{
    gnode_t *p = graph->relation[vn].next;
    
    if (NULL == p)
        return -1;
    
    return p->data;
}

int graph_next_adj(graph_t *graph, int vx, int vy)
{
    gnode_t *p = graph->relation[vx].next;
    
    while (NULL != p && p->data != vy)
        p = p->next;
    
    if (NULL == p || NULL == p->next)
        return -1;
    
    return p->next->data;
}

//深度搜索
int graph_dfs(graph_t *graph, int start)
{
    int vn;
    
    if (graph->visit[start])
        return 0;
    
    printf(" V%d,", start);
    graph->visit[start] = 1;
    
    vn = graph_first_adj(graph, start);
    
    while (vn != -1) {
        graph_dfs(graph, vn);
        vn = graph_next_adj(graph, start, vn);
    }
    
    return 0;
}

//广度搜索
int graph_bfs(graph_t *graph, int start)
{
    sequeue_t *queue = NULL;
    int vn;
    
    memset(graph->visit, 0, sizeof(*graph->visit) * graph->vn);
    
    queue = sequeue_init(5);
    sequeue_enque(queue, start);
    graph->visit[start] = 1;
    
    while (!sequeue_isempty(queue)) {
        sequeue_deque(queue, &start);
        printf(" V%d,", start);
        
        vn = graph_first_adj(graph, start);
        while (vn != -1) {
            if (!graph->visit[vn]) {
                sequeue_enque(queue, vn);
                graph->visit[vn] = 1;
            }
            vn = graph_next_adj(graph, start, vn);
        }
    }
    
    sequeue_destroy(queue);
    return 0;
}