图

图.png

图(Graph) 是由顶点的有穷⾮空集合和顶点之间边的集合组成。通常表示为: G(V,E). 其中，G表示一个图, V 是图G中的顶点集合，E 是图G中边的集合。在图形结构中，结点之间的关系可以是任一的，图中任意两个数据元素之间都可能相关。图有各种形状和大小。边可以有权重（weight），即每一条边会被分配一个正数或者负数值。

图的存储

理论上，图就是一堆顶点和边对象而已，但是怎么在代码中来描述呢？有两种主要的方法：邻接表和邻接矩阵。

邻接矩阵

在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。

实现

思路

1. 确定顶点数/边树
2. 读取顶点信息
3. 初始化邻接矩阵
4. 读入边信息
5. 循环打印

1. 邻接矩阵矩阵存储的数据结构设计

#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct {
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numNodes, numEdges; /* 图中当前的顶点数和边数  */
}MGraph;

2. 核心代码

void CreateMGraph(MGraph *G) {

    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    
    //1. 输入顶点数/边数
    scanf("%d, %d", &G->numNodes, &G->numEdges);
    printf("顶点数:%d, 边数:%d\n", G->numNodes, G->numEdges);

    //2.输入顶点信息/顶点表
    for(i = 0; i<= G->numNodes; I++)
        scanf("%c", &G->vexs[I]);

    //3.初始化邻接矩阵
    for(i = 0; i < G->numNodes; I++)
         for(j = 0; j < G->numNodes; j++)
             G->arc[i][j] = INFINITYC;

    //4.输入边表信息
    for(k = 0; k < G->numEdges; k++){
        printf("输入边(vi, vj)上的下标i, 下标j, 权w\n");
        scanf("%d, %d, %d",&i, &j, &w);

        G->arc[i][j] = w;
        //如果无向图,矩阵对称;
        G->arc[j][i] = G->arc[i][j];

    }
    /*5.打印邻接矩阵*/
    for (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ", G->arc[i][j]);
        }
    }
    printf("\n");
}

3. 使用并打印结果

MGraph G;
CreateMGraph(&G);

邻接矩阵.png

邻接表

在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。

实现

思路

1. 确定顶点数
2. 读取顶点信息
3. 创建一个结点插入到对应的顶点数组中
   1⃣️创建结点p
   2⃣️将结点p的adjvex赋值j
   3⃣️将结点p插入到对应的顶点数组下标I下
   4⃣️将顶点数组[i]的firstedge设置为p
   如果是无向图，则循环1⃣️～4⃣️步骤。

1. 邻接表存储的数据结构设计

#define M 100
#define true 1
#define false 0

typedef char Element;
typedef int BOOL;
//邻接表的节点
typedef struct Node {
    int adj_vex_index;  //弧头的下标，也就是被指向的下标
    Element data;       //权重值
    struct Node * next; //边指针
}EdgeNode;

//顶点节点表
typedef struct vNode {
    Element data;          //顶点的权值
    EdgeNode * firstedge;  //顶点下一个是谁？
}VertexNode, Adjlist[M];

//总图的一些信息
typedef struct Graph {
    Adjlist adjlist;       //顶点表
    int arc_num;           //边的个数
    int node_num;          //节点个数
    BOOL is_directed;      //是不是有向图
}Graph, *GraphLink;

2. 核心代码

void creatGraph(GraphLink *g) {
    int i, j, k;
    EdgeNode *p;
    
    //1. 顶点,边,是否有向
    printf("输入顶点数目,边数和有向？：\n");
    scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);
    
    //2.顶点表
     printf("输入顶点信息：\n");
    for (i = 0; i < (*g)->node_num; i++) {
        getchar();
        scanf("%c", &(*g)->adjlist[i].data);
        (*g)->adjlist[i].firstedge = NULL;
    }
    
    //3.
    printf("输入边信息：\n");
    for (k = 0; k < (*g)->arc_num; k++){
        getchar();
        scanf("%d %d", &i, &j);
        
        //①新建一个节点
        p = (EdgeNode *)malloc(sizeof(EdgeNode));
        //②弧头的下标
        p->adj_vex_index = j;
        //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
        p->next = (*g)->adjlist[i].firstedge;
        //④将顶点数组[i].firstedge 设置为p
        (*g)->adjlist[i].firstedge = p;
        
        //j->I
        if(!(*g)->is_directed) {
            // j -----> I
            //①新建一个节点
            p = (EdgeNode *)malloc(sizeof(EdgeNode));
            //②弧头的下标i
            p->adj_vex_index = I;
            //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
            p->next = (*g)->adjlist[j].firstedge;
            //④将顶点数组[i].firstedge 设置为p
            (*g)->adjlist[j].firstedge = p;
        }
    }
}

void putGraph(GraphLink g) {
    int I;
    printf("邻接表中存储信息:\n");
    //遍历一遍顶点坐标，每个再进去走一次
    for (i = 0; i < g->node_num; i++) {
        EdgeNode * p = g->adjlist[i].firstedge;
        while (p) {
            printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data);
            p = p->next;
        }
        printf("\n");
    }
}

3. 使用并打印结果

GraphLink g = (Graph *)malloc(sizeof(Graph));
creatGraph(&g);
putGraph(g);

邻接表.png