定义

图(Graph) 是由顶点的有穷⾮空集合和顶点之间边的集合组成。通常表示为：G(V，E)。其中，G表示一个图；V是图G中顶点的集合；E是图G中边的集合。

image.png

在线性表中，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；
在树形结构中，数据之间有明显的层次关系，并且每一层上的数据元素可能和下一层中多个数据元素有关，但只能和上一层中的一个元素相关。

图的定义注意点：

• 线性表中我们把数据元素叫元素；树中数据元素叫结点；在图中，数据元素称为顶点。
• 线性表中可以没有数据元素，称为空表；树中可以没有结点，称为空树；但是在图中，不允许没有顶点，且顶点集合V是有穷非空的。
• 线性表中，相邻的数据元素之间具有线性关系；在树中，相邻的两层结点具有层次关系；在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集允许为空。

图的邻阶矩阵存储方式

图的邻阶矩阵存储方式是用两个数组来表示图，一个一维数组存储图中的顶点信息，一个二维数组存储图中边或者弧的信息。

邻阶矩阵的优点

• 我们要判定任意两顶点是否有边无边就非常容易，可以直接遍历矩阵某一行即可。
• 我们要知道某个顶点的度，其实就是这个顶点V_i在邻阶矩阵第i行的元素之和。
• 求顶点V_i的所有邻接点就是将矩阵第i行元素遍历一遍，arc[i][j]为1就是邻接点。

代码实现

typedef struct{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numNodes, numEdges; /* 图中当前的顶点数和边数  */
}MGraph;

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");
}

图的邻接表

邻阶矩阵是不错的一种图的存储结构，但是我们发现，对于边数相对顶点较少的图，这种结构存在极大的浪费。比如： image.png
顶点数组为： image.png
边数组为： image.png
邻阶矩阵中，除了arc[1][0]有值外，没有其它的弧，其实这些存储空间就被浪费掉了。

因此，我们引出链式存储的结构，来避免这种空间浪费的情况。

代码实现

//边表结点
typedef struct EdgeNode{
    int adjvex;     //邻接点域，存储该顶点对应的下标
    EdgeType weight;//用于存储权值
    struct EdgeNode* next;//链域，指向下一个邻接点
}EdgeNode;

//顶点表结点
typedef struct VertexNode{
    Vertextype data;    //顶点域，存储顶点信息
    EdgeNode* firstedge;//边表头指针
}VertexNode, Adjlist[M];

typedef struct GraphLink{
    Adjlist adjlist;       //顶点表
    int numVertexes, numEdges;
}Graph, *GraphLink;

void creatGraph(GraphLink* G){
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    //1. 输入顶点数/边数
    scanf("%d %d",&(*G)->numVertexes,&(*G)->numEdges);
    printf("顶点数:%d,边数:%d\n",(*G)->numVertexes,(*G)->numEdges);
    //2.输入顶点信息/顶点表
    for(i = 0; i<= (*G)->numVertexes;i++){
        scanf("%d",&(*G)->adjlist[i].data);
        (*G)->adjlist[i].firstedge = NULL;
    }
    //3.建立边表
    for(k = 0; k<(*G)->numEdges; k++){
        printf("输入边(vi,vj)上的下标i,下标j,权w\n");
        scanf("%d,%d,%d",&i,&j,&w);
        EdgeNode* ej = (EdgeNode*)malloc(sizeof(EdgeNode));
        ej->adjvex = j;
        ej->weight = w;//无向图，i->j j->i权重是一样的
        ej->next = (*G)->adjlist[i].firstedge;//采用头插法
        (*G)->adjlist[i].firstedge = ej;
        
        //由于是无向图，所以i顶点的邻接点为j，j顶点的邻接点也是i
        EdgeNode* ei = (EdgeNode*)malloc(sizeof(EdgeNode));
        ei->adjvex = i;
        ei->weight = w;////无向图，i->j j->i权重是一样的
        ei->next = (*G)->adjlist[j].firstedge;//采用头插法
        (*G)->adjlist[j].firstedge = ei;
    }
}