主要写一下图的几种表示方法。
今天写的几种图存储结构包括邻接矩阵，邻接表，十字链表，邻接多重表，边集数组。
主要是邻接表，十字链表和邻接多重表。邻接矩阵和边集数组比较好理解和实现
我在网上查了一些资料和看了课本上的十字链表和邻接多重表的例子，个人觉得讲的不那么通俗，尤其是课本…
目录：
0.预备知识
1.邻接矩阵
2.邻接表
3.十字链表
4.邻接多重表
5.边集数组
0.预备知识
<1.图表示方法
数据结构中的一个图是用G = (V, E)集合来表示的， V（vertex）是顶点集合， E(edge)是边集合
看下图
顶点直接表示：顶点集合(v1, v2, v3)
我们只能间接的用两个点来表示一条边：E((v1, v2), (v1, v3), (v3, v2))
<2.有向和无向图
下图的v1-v2是双通还是只能有一个方向通过
<3.出度和入度
出度：一个点可以选择多少条路径到达其他地方。
入度：有多少条路径可以到达这个点。
第一张图v1出度是2，入度是0。
<4.权重：标记一条路径长短的值。
1.邻接矩阵
简单理解就是用一个二维矩阵（二维数组）来存储。按照标记来查看此边是否存在。邻接矩阵为每一种情况都做好了空间预存。
该图是一个有向图，右图为邻接矩阵，我们可以看出，v1通往v2,那么G[v1][v2]标记为1，v2不能通往v1，G[v2][v1]为0，不存在v1到v1路径，我们初始化为 “-”。
标记为1为了简单起见，有权图我们则标记为权重
适用场景：使用于稠密的图，可以快速定位到指定的边，但是如果是稀疏的图，会比较浪费空间。
代码：
#include <stdio.h>#include <malloc.h>#include <assert.h>//const int Maxvex = 100;enum{ Maxvex = 100 };const int infinity = 10000;typedef struct graph{int vexs[Maxvex+1];//顶点数int arc[Maxvex+1][Maxvex+1];//邻接矩阵int EdgeNum, VexsNum;//边数，顶点数}Mgraph;void create_graph(Mgraph *G){int i,j,k,w;printf("请输入顶点数,边数:");scanf("%d,%d", &G->VexsNum, &G->EdgeNum);//输入顶点for(i = 1; i <= G->VexsNum; i++)scanf("%d", &G->vexs[i]);//初始化邻接矩阵for(i = 1; i <= G->VexsNum; i++){for(j = 1; j <= G->VexsNum; j++){G->arc[i][j] = infinity;}}//录入边printf("EdgeNum:%d\n", G->EdgeNum);for(k = 1; k <= G->EdgeNum; k++){printf("输入边的i, j, 权值:");scanf("%d,%d,%d", &i, &j, &w);G->arc[i][j] = w;G->arc[j][i] = G->arc[i][j];//无向图arc[i][j]和 arc[j][i]是同一条边，有向图则只赋值一边即可}}int main(){Mgraph *G;G = (Mgraph*)malloc(sizeof(Mgraph));assert(G != NULL);//if G != NULL false errorcreate_graph(G);}
2.邻接表
上面所说邻接矩阵它包含了每一种可能出现情况，不适合稀疏图存储，所以出现了邻接表。
右图为邻接表，节省空间，存储方式决定了它只能表示某个顶点的入度或者出度，不能快速定位到某一条边。
比如v1，有两条路径v1 — v2
v1 — v3，那么v1的出度是2，但是我们不能表示它的入度。
右图的邻接表可以看出v1指向了v2，v1也指向了v3 (v2,v3之间的箭头只是为了链表连接)，表示从v1可以通往v2和v3。
如果我们想表示入度可以建立一个逆邻接表，来表示入度。比如v2 — v1，因为v2的入度是1，只有v1通往它。
适用场景：稀疏图的存储，节省空间。
代码：（要理解顶点集和边集的结构）
#include <stdio.h>#include <assert.h>#include <malloc.h>enum { verMax = 10 };typedef int VertexType;typedef int EdgeType;typedef struct EdgeNode//边表节点{int adjvex;//节点EdgeType weight;//权struct EdgeNode* next;}EdgeNode;typedef struct VertexNode//顶点表节点{VertexType data;EdgeNode *firstEdge;//边表头指针}Adjlist[verMax], VertexNode; //Adglist 是 struct Vertex [verMax]类型的typedef struct AdjGraph{int EdgeNum, VertexNum;Adjlist adjlist;}AdjGraph;void Create_graph(AdjGraph *G){int i, j, k, w;EdgeNode *e;printf("请输入顶点，边数:");scanf("%d,%d", &G->VertexNum, &G->EdgeNum);printf("请输入顶点:");for(i = 1; i <= G->VertexNum; i++){scanf("%d", &G->adjlist[i].data);G->adjlist[i].firstEdge = NULL;}for(k = 1; k <= G->EdgeNum; k++){printf("请输入边的两端节点和权v1, v2, w:");scanf("%d,%d,%d", &i, &j, &w);e = (EdgeNode*)malloc(sizeof(EdgeNode));assert(e != NULL);e->adjvex = j;e->next = G->adjlist[i].firstEdge;G->adjlist[i].firstEdge = e;/* e = (EdgeNode*)malloc(sizeof(EdgeNode)); //注释为逆邻接表的建立方式assert(e != NULL);e->adjvex = i;e->next = G->adjlist[j].firstEdge;G->adjlist[j].firstEdge = e;*/}}int main(){AdjGraph *G;int i = 0, j = 0;EdgeNode *e;G = (AdjGraph *)malloc(sizeof(AdjGraph));assert(G != NULL);Create_graph(G);printf("\n");for(i = 1; i <= G->VertexNum; i++){printf("|%d|->", G->adjlist[i].data);e = G->adjlist[i].firstEdge;while(e != NULL){printf("%d->", e->adjvex);e = e->next;}printf("NULL\n");}return 0;}
3.十字链表
邻接表在某种程度上是有缺陷的，它表示了出度就表示不了入度。
所以出现了十字链表，它既能表示入度也能表示出度。
说通俗点，十字链表也就是邻接表的改进，顶点集包含两个指针，firstIn和firstOut,
firstIn指向入边表（逆邻接表）， firstOut表示出边表（也就是邻接表）。（需要先理解上面代码中顶点集和边节点的结构）。
图画的不太好，见谅…
现在睡觉的话，会做梦;而现在学习的话，会让梦实现。
