引入

我们知道如何构建一个图的数据结构，那么现在，我们看看如何根据一棵图的图形，创建一张图到内存中去。

创建数据结构

#define MAX_VEX_NUM 50  //最大的容量暂定为50
typedef enum {DG, UDG} GraphType;  //选择有向图还是无向图
typedef struct {
    char vexs[MAX_VEX_NUM];  //一维数组存储顶点
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];   //二维数组（邻接矩阵）存储边
    int vexnum, arcnum;  //记录顶点的数量和边的数量，等下用作循环判断条件
    GraphType type;  //记录图得类型
} MGraph;

数据结构中

  • 记录顶点的数量和边的数量，等下用作循环判断条件
  • 记录图得类型，等下用于写入矩阵

获取数据

void create_MG(MGraph *MG)
{
    
    int type;  //存储图得类型
    printf("请输入图的类型，有向图（输入0）无向图（输入1） :");
    scanf("%d", &type);
    //如果是0，那就是有向图，如果是1那就是无向图
    if (type == 0)
        MG->type = DG;
    else if (type == 1)
        MG->type = UDG;
    else
    {
        printf("请输入正确的图类型，有向图（输入0）无向图（输入1）");
        return;
    }
    
    //获取数值
    printf("请输入顶点个数:");
    scanf("%d", &MG->vexnum);  //数值赋值给 MG 的 vexnum
    printf("请输入边个数：");
    scanf("%d", &MG->arcnum);
    getchar();  //接收最后那个回车
    
    int i;
    int v1, v2;
    //有多少个顶点，就输入多少次
    for (i = 1; i <= MG->vexnum; i++)
    {
        printf("请输入第%d个顶点的值:", i);
        scanf("%c", &MG->vexs[i]);
        getchar();
    }
    //以上就完成了所有信息的获取

我们一部分一部分的讲

  • 先输入1或0判断图类型，然后存到结构体中
  • 然后输入顶点数和边树，方便下面判断循环次数
  • 接着根据顶点数，接收每个顶点得值
  • 所有数据获取完毕

初始化矩阵

//初始化邻接矩阵，双层循环将二维数组都填充为0
   for (i = 1; i <= MG->vexnum; i++)
   {
       for (j = 1; j <= MG->vexnum; j++)
       {
           MG->arcs[i][j] = 0;
       }
   }

这里我们先把矩阵创建出来

  • 判断条件就是顶点的个数，有多少顶点创建多大的矩阵
  • 矩阵中默认的值为0

在矩阵中定位

//定位
// 输入矩阵指针和顶点得值，判断在一维数组中这是第几号，并返回
int getIndexOfVexs(char vex, MGraph *MG)
{
    int i;
    //有多少结点循环多少次
    for (i = 1; i <= MG->vexnum; i++)
    {
    //如果值等于输入的值，那么就把在一维数组中的位置返回
        if (MG->vexs[i] == vex)
        {
            return i;
        }
    }
    return 0;
}

这个定位的函数，主要是

  • 将用户输入的值，在一维数组中找到它的位置
  • 然后将这个位置返回
  • 我们就能通过这个位置在矩阵中定位到它了

处理边的信息

//输入边的信息，建立邻接矩阵，有多少边执行多少次
   char c1, c2;
   int j, k;
   for (k = 1; k <= MG->arcnum; k++) {
       printf("请输入第%d个边: ", k);
       scanf("%c %c", &c1, &c2);
       //利用上面的定位函数，找到输入的顶点在一维数组中的位置
       v1 = getIndexOfVexs(c1, MG);
       v2 = getIndexOfVexs(c2, MG);
       
       if (MG->type == 1)  //如果是y无向图，则对称矩阵，把对称位置上的值同时赋值为1
           MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
       else  //如果是有向图，则只在指定位置赋值。
           MG->arcs[v1][v2] = 1;
       getchar();
   }

有多少个顶点就循环多少次

  • 接收到构成边的两个顶点
  • 然后利用上面的定位函数，返回在一维数组中的位置
  • 接着判断图得类型
  • 无向图，那么矩阵对称，则在对称位置同时赋值 1
  • 有向图，矩阵不对称，所以只在对应位置赋值 1

总代码

#include <stdio.h>
#include <stdlib.h>
#define MAX 50

typedef enum{DG,UDG} GraphType;

typedef struct {
    char vex[MAX];  //定义一维数组存储顶点
    int arcs[MAX][MAX];  //定义二维数组存储边
    int vexnum,arcnum;  //存储顶点和边的数量
    GraphType type;  //存储图的类型
}Graph;

int position(char c , Graph *G){
    int i;
    for(i=1;i<=G->vexnum;i++){
        if(G->vex[i]==c){
            return i;
        }
    }
    return 0;
}

void Create(Graph * G){
    //获取图的类型
    int type;
    printf("请输入图的类型，有向图输入1，无向图输入0:");
    scanf("%d",&type);
    if(type==1){
        G->type=DG;
    }else if(type==0){
        G->type=UDG;
    }else{
        printf("输入的类型不正确！\n");
        return;
    }
    //获取图得顶点数和边数
    printf("图有几个顶点:");
    scanf("%d",&G->vexnum);
    printf("图有几条边:");
    scanf("%d",&G->arcnum);
    getchar();
    //获得每个顶点得值
    
    for(int k=1;k<=G->vexnum;k++){
        printf("请输入第%d个结点的值：",k);
        scanf("%s",&G->vex[k]);
        getchar();
    }
    //值全部获得完毕
    
    //矩阵初始化
    int i,j;
    for (i = 1; i <= G->vexnum; i++)
    {
        for (j = 1; j <= G->vexnum; j++)
        {
            G->arcs[i][j] = 0;
        }
    }
    //有多少个结点循环多少次
    char V1,V2;
    int V1p,V2p;
    for(int l=1;l<=G->arcnum;l++){
        printf("请输第%d个边的信息：",l);
        scanf("%c %c",&V1,&V2);
        V1p=position(V1,G);
        V2p=position(V2,G);
        
        if(G->type==UDG){
            G->arcs[V1p][V2p]=G->arcs[V2p][V1p]=1;
        }else{
            G->arcs[V1p][V2p]=1;
        }
        getchar();
    }
}

void print_MG(Graph MG){
    printf("-------------------------------\n");
    int i, j;
    if(MG.type == DG)
    {
        printf("图类型 : 有向图\n");
    }
    else
    {
        printf("图类型：无向图\n");
    }
    printf("图中的顶点有: %d 个\n",MG.vexnum);
    printf("图中的边/弧有: %d 个\n",MG.arcnum);
    
    printf("顶点的集合:");
    for (i = 1; i <= MG.vexnum; i++){
        printf("%c ", MG.vex[i]);
    }
    printf("\n");
    printf("邻接矩阵:\n");
    
    for (i = 1; i <= MG.vexnum; i++)
    {
        printf("%c ", MG.vex[i]);
        j = 1;
        for (; j < MG.vexnum; j++)
        {
            printf("%d ", MG.arcs[i][j]);
        }
        printf("%d ", MG.arcs[i][j]);
        printf("\n");
    }
}
int main()
{
    Graph MG;
    Create(&MG);
    print_MG(MG);
    return 0;
}

V0 V1 v2 v3
V0 0 1 1 1
V1 1 0 1 0
V2 1 1 0 1
V3 1 0 1 0

我们将上面的图输入程序，我们用 a、b、c、d 代替v1、v2、v3、v4

运行结果
请输入图的类型，有向图输入1，无向图输入0:0
图有几个顶点:4
图有几条边:5
请输入第1个结点的值：a
请输入第2个结点的值：b
请输入第3个结点的值：c
请输入第4个结点的值：d
请输第1个边的信息：a b
请输第2个边的信息：b c
请输第3个边的信息：c d
请输第4个边的信息：d a

请输第5个边的信息：a c

图类型：无向图
图中的顶点有: 4 个
图中的边/弧有: 5 个
顶点的集合:a b c d
邻接矩阵:
a 0 1 1 1
b 1 0 1 0
c 1 1 0 1
d 1 0 1 0

运行结果同矩阵相同，成功！

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。