C语言实现图的相关算法

傷城~ 2022-03-10 00:35 255阅读 0赞

**简介：**  
该程序主要是用C语言来实现与图相关的算法，目的在于加深对于图这种数据结构的理解以及探索其应用场景。  
程序中涉及的有向图如下：  
![在这里插入图片描述][20190308204721711.png]

/*--------------------------------------------
    功能：关于图的存储及操作算法：
    1.根据有向图的邻接矩阵创建该图的邻接表;
    2.打印有向图的邻接表;
    3.销毁一个图的邻接表;
    4.有向图的邻接表的深度优先遍历和广度优先遍历;
    5.关于环形队列的操作。
    ----------------------------------------------
    运行结果：
    该图的邻接表为：
    0 1[6] -> 3[2] -> NULL
    1 2[10] -> 4[3] -> NULL
    2 4[8] -> NULL
    3 2[1] -> NULL
    4 3[12] -> NULL
    该图的一个深度优先遍历序列为：
    0 1 2 4 3
    该图的一个广度优先遍历序列为：
    0 1 3 2 4
    ----------------------------------------------
    Author: Zhang Kaizhou
    Date: 2019-3-8 20:19:37
    ----------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #define INF 32767
    #define MAXSIZE 1000
    #define N 5
    
    int adjacency_array[N][N] = {
       {0, 6, INF, 2, INF},
                                 {INF, 0, 10, INF, 3},
                                 {INF, INF, 0, INF, 8},
                                 {INF, INF, 1, 0, INF},
                                 {INF, INF, INF, 12, 0}}; // 用一个全局二维数组存储一个有向图的邻接矩阵，数字表示连通边权值， INF表示非连通
    
    int visited_deep[N * N] = { 0 }; // 定义一个全局访问记录数组，用于图的深度优先遍历
    
    typedef struct node{ // 定义一个邻接表结点数据类型
        int id; // 结点编号
        struct node * pnext; // 指向下一个结点的指针
        int weight; // 通向下一个结点的边的权值
    } Node;
    
    typedef struct{ // 定义一个图的邻接表数据类型
        Node * headnode[MAXSIZE]; // 头结点指针数组
        int vertex; // 图中的顶点数
        int edge; // 图中的边数
    } Graph;
    
    typedef struct{ // 定义一个队列数据类型
        int data[MAXSIZE];
        int head;
        int tail;
    } Queue;
    
    void creat_graph_adjacency_list(Graph * pgraph, int vertex, int edge);
    void print_graph(Graph * pgraph);
    void distory_graphy(Graph ** ppgraph);
    void deep_first_search(Graph * pgraph, int start);
    void breadth_first_search(Graph * pgraph, int start);
    void in_queue(Queue * q, int id);
    void out_queue(Queue * q, int * temp);
    
    int main(){
        Graph * pgraph = (Graph *)calloc(1, sizeof(Graph));
        creat_graph_adjacency_list(pgraph, N, 7);
        printf("该图的邻接表为：\n");
        print_graph(pgraph);
        printf("该图的一个深度优先遍历序列为：\n");
        deep_first_search(pgraph, 0);
        printf("\n该图的一个广度优先遍历序列为：\n");
        breadth_first_search(pgraph, 0);
        distory_graphy(&pgraph);
        return 0;
    }
    
    void creat_graph_adjacency_list(Graph * pgraph, int vertex, int edge){ // 根据有向图的邻接矩阵创建图的邻接表
        int i, j;
        for(i = 0; i < vertex; i++){
            pgraph->headnode[i] = NULL; // 邻接表所有头结点初始化为空
        }
        for(i = 0; i < vertex; i++){
            for(j = vertex - 1; j >= 0; j--){ // 用头插法倒序插入
                if(adjacency_array[i][j] != 0 && adjacency_array[i][j] != INF){ // 当结点连通且权值为有限值时
                    Node * pnew = (Node *)calloc(1, sizeof(Node));
                    pnew->id = j;
                    pnew->weight = adjacency_array[i][j];
                    pnew->pnext = pgraph->headnode[i]; // 头插法创建单链表
                    pgraph->headnode[i] = pnew;
                }
            }
        }
        pgraph->vertex = vertex;
        pgraph->edge = edge;
        return;
    }
    
    void print_graph(Graph * pgraph){ // 打印有向图的邻接表
        int i;
        Node * phead;
        if(pgraph == NULL){
            printf("The graph is empty!\n");
        }else{
            for(i = 0; i < pgraph->vertex; i++){
                phead = pgraph->headnode[i];
                printf("%d ", i);
                while(phead != NULL){
                    printf("%d[%d] -> ", phead->id, phead->weight);
                    phead = phead->pnext;
                }
                printf("NULL\n");
            }
        }
        free(phead);
        phead = NULL;
        return;
    }
    
    void distory_graphy(Graph ** ppgraph){ // 销毁一个图的邻接表
        int i;
        Node * ppre, * pcur;
        for(i = 0; i < (* ppgraph)->vertex; i++){
            ppre = (* ppgraph)->headnode[i];
            if(ppre != NULL){
                pcur = ppre->pnext;
                while(pcur != NULL){
                    free(ppre);
                    ppre = pcur;
                    pcur = pcur->pnext;
                }
                free(ppre);
            }else{
                free(ppre);
                ppre = NULL;
            }
        }
        free(* ppgraph);
        * ppgraph = NULL; // 释放后的指针变量置空，防止再次引用该变量时指向出错
        return;
    }
    
    void deep_first_search(Graph * pgraph, int start){ // 有向图的邻接表的深度优先遍历
        Node * p;
        visited_deep[start] = 1; // 起始结点被标为已访问
        printf("%d ", start);
        p = pgraph->headnode[start];
        while(p != NULL){
            if(visited_deep[p->id] == 0){ // 若当前结点未被遍历过
                deep_first_search(pgraph, p->id); // 递归遍历
            }
            p = p->pnext;
        }
        return;
    }
    
    void breadth_first_search(Graph * pgraph, int start){ // 有向图的邻接表的广度优先遍历
        Queue * q = (Queue *)calloc(1, sizeof(Queue)); // 申请一个队列并初始化
        q->head = 0;
        q->tail = 0;
        int visited[N * N] = { 0 };
        int temp;
        Node * pcur;
    
        printf("%d ", start);
        visited[start] = 1;
        in_queue(q, start);
        while(q->tail != q->head){ // 环形队列非空时
            out_queue(q, &temp);
            pcur = pgraph->headnode[temp];
            while(pcur != NULL){ // 遍历pcur的所有邻接点
                if(visited[pcur->id] == 0){
                    printf("%d ", pcur->id);
                    visited[pcur->id] = 1;
                    in_queue(q, pcur->id);
                }
                pcur = pcur->pnext;
            }
        }
        return;
    }
    
    void in_queue(Queue * q, int id){ // 入栈环形队列
        if((q->tail + 1) % MAXSIZE == q->head){
            printf("The queue is full!\n");
        }else{
            q->tail = (q->tail + 1) % MAXSIZE;
            q->data[q->tail] = id;
        }
        return;
    }
    
    void out_queue(Queue * q, int * temp){
        if(q->tail == q->head){
            printf("The queue is empty!\n");
        }else{
            q->head = (q->head + 1) % MAXSIZE;
            * temp = q->data[q->head];
        }
        return;
    }

[20190308204721711.png]: /images/20220310/cd1b77d706344f8fab8b361e69b2c069.png