从零开始养成算法·篇十四：图与图的存储

一、图

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

•注意的地方：
–线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。
–线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在咱国内大部分的教材中强调顶点集合V要有穷非空。
–线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶(Vi,Vj)来表示
有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也成为弧(Arc)，用有序偶<Vi,Vj>来表示，Vi称为弧尾，Vj称为弧头。

简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。
通常认为边或弧数小于nlogn（n是顶点的个数）的图称为稀疏图，反之称为稠密图。

有些图的边或弧带有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)，带权的图通常称为网(Network)。
对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。

顶点V的度(Degree)是和V相关联的边的数目，记为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。
对于有向图G=(V,E)，如果有<V1,V2>∈E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。
以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。

在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于图中任意两个顶点Vi和Vj都是连通的，则称G是连通图。
无向图中的极大连通子图称为连通分量。

注意以下概念：
–首先要是子图，并且子图是要连通的；
–连通子图含有极大顶点数；
–具有极大顶点数的连通子图包含依附于这些顶点的所有边。

在有向图G中，如果对于每一对Vi到Vj都存在路径，则称G是强连通图。
有向图中的极大强连通子图称为有向图的强连通分量。

一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。

二、邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设置两个数组，顶点数组为vertex[4]={V0,V1,V2,V3}，边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边，1表示顶点间存在边)。

对称矩阵：所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j]i。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。
有了这个二维数组组成的对称矩阵，可以很容易地知道图中的信息：
–要判定任意两顶点是否有边无边非常容易；
–要知道某个顶点的度，其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和；
–求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

——邻接矩阵（有向图）
顶点数组vertex[4]={V0,V1,V2,V3}，弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由V1到V0有弧，得到arc[1][0]=1，而V0到V1没有弧，因此arc[0][1]=0。
另外有向图是有讲究的，要考虑入度和出度，顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V1行的各数之和。

——邻接矩阵（网）
在图的术语中，我们提到了网这个概念，事实上也就是每条边上带有权的图就叫网。
这里“∞”表示一个计算机允许的、大于所有边上权值的值。

邻接矩阵存储代码实现思想：
1、确定顶点数/边数
2、读取顶点信息
3、初始化邻接矩阵
4、读入边信息
5、循环打印

#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;

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

三、邻接表

对于边数相对顶点较少的图，邻接矩阵的这种l结构无疑是存在对存储空间的极大浪费。
把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。

邻接表的处理方法是这样：
–图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。
–图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。
有向图——邻接表结构也是类似的，把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度。
有时为了便于确定顶点的入度或以顶点为弧头的弧，也可以建立一个有向图的逆邻接表，此时很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可。

邻接表存储代码实现思想：
1、确定顶点数/边数
2、读取顶点信息
3、创建一个结点插入到对应的顶点数组中
创建结点p
将结点p的adjvex赋值I
将结点p插入到对应的顶点数组下标i下
将顶点数组[i]的firstedge设置为p
如果是无向图，则循环以上步骤

//邻接表的节点
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;

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