C语言图的邻接矩阵建立算法

浅浅的花香味﹌ 2022-04-24 11:38 188阅读 0赞

**目录**

1.邻接矩阵（adjacency matrix）

2.无向图的邻接矩阵表示

3.有向图的邻接矩阵表示

4.网的邻接矩阵表示

5.示例源代码

--------------------

### 1.邻接矩阵（adjacency matrix） ###

（1）用一维数组存储顶点信息

（2）用矩阵（二维数组）表示图中顶点邻接关系

### 2.无向图的邻接矩阵表示 ###

规定：若两节点连通，则在矩阵对应位置元素置1，否则置0

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

### 3.有向图的邻接矩阵表示 ###

规定：若两节点连通，则矩阵对应位置元素为边上权值，否则为无穷大

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

### 4.网的邻接矩阵表示 ###

规定：若两节点连通，则矩阵对应位置元素为边上权值，否则为无穷大

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

### 5.示例源代码（以上述无向图为例） ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VERTEX_NUM 100 // 图中最大节点数
    typedef char VertexType;   // 顶点类型设置为字符型
    typedef int EdgeType;      // 边上权值类型设置为整型
    typedef struct             // 边表节点
    {
        VertexType vex[MAX_VERTEX_NUM];                 // 顶点表
        EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
        int vexnum;                                     // 节点的数目
        int edgenum;                                    // 边的数目
    } MGraph;
    
    void CreateMG(MGraph *MG); // 邻接表法创建无向图
    void PrintMG(MGraph MG);   // 邻接矩阵形式输出图MG
    
    int main(void)
    {
        MGraph g;
    
        CreateMG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        PrintMG(g);
    
        return 0;
    }
    void CreateMG(MGraph *MG)
    {
        int i = 0, j, k, w; // w：权值
        char ch;
    
        printf("请依次输入顶点数、边数：");
        scanf("%d %d", &(MG->vexnum), &(MG->edgenum));
    
        printf("请依次输入顶点（以回车结束输入）：");
        getchar();
        while ((ch = getchar()) != '\n') // 输入顶点信息
            MG->vex[i++] = ch;
    
        /*
         * for (i = 0; i < MG->vexnum; i++)
         *     scanf("\n%c", &(MG->vex[i]));
         */
    
        // 初始化邻接矩阵
        for (i = 0; i < MG->vexnum; i++)
            for (j = 0; j < MG->vexnum; j++)
                MG->edges[i][j] = 0;
    
        printf("顶点 | 下标\n");
        // 显示图中顶点及其对应下标
        for (i = 0; i < MG->vexnum; i++) {
            printf("%3c%6d\n", MG->vex[i], i);
        }
    
        printf("请输入每条边对应的两个顶点下标（格式：i,j）：\n");
        // 建立邻接矩阵
        for (k = 0; k < MG->edgenum; k++) {
            scanf("\n%d,%d", &i, &j);
            MG->edges[i][j] = 1;
            MG->edges[j][i] = 1;
        }
    }
    void PrintMG(MGraph MG)
    {
        int i, j;
    
        // 输出邻接矩阵
        for (i = 0; i < MG.vexnum; i++) {
            for (j = 0; j < MG.vexnum; j++)
                printf("%2d", MG.edges[i][j]);
            printf("\n");
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220215/174ce97dc88e42e0867ed6d32a10f0f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220215/79c32e6e89794cbf864c931cba7d15dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220215/2a95efd8933049ee8c60e02a420cfc17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3]: /images/20220215/4a69e319614e48dcabf771a195f4eff1.png