数据结构-图的储存方式
主要写一下图的几种表示方法。
今天写的几种图存储结构包括邻接矩阵，邻接表，十字链表，邻接多重表，边集数组。
主要是邻接表，十字链表和邻接多重表。邻接矩阵和边集数组比较好理解和实现
我在网上查了一些资料和看了课本上的十字链表和邻接多重表的例子，个人觉得讲的不那么通俗，尤其是课本...
目录：
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 error
create_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表示出边表（也就是邻接表）。（需要先理解上面代码中顶点集和边节点的结构）。
图画的不太好，见谅...
注意右图的箭头是指向整个结构。
看右图的结构：每个节点都有firstIn和firstOut是用来表示入度的边（fristIn）和出度的边(firstOut)，可以这样表示是因为
每个边的存储结构是右上角包括（起点， next，指向顶点， 反next，和 w），比如左图的路径v1 --> v3， 那么对于v1来说
v3是v1的出度路径，对于v3来说v1是v3的入度路径，那么当我们读入这条边的时候，我们就要同时更新决定这条边的两个顶点
所以在右图的十字链表其实我们只录入了 v1 --> v3这一条边，但是顶点集合v1的firOut和v3的firIn就更新了（右图的两个箭头），
遍历十字链表时，firsIn后面连接的就是该点的入度，firsOut后面连接的就是该点的出度。
这样每次录入边我们能更新入度和出度，录入完成后就可以同时访问入度和出度了～
代码：（还是需理解顶点集和边节点的声明定义）
/*
* 十字链表， 结合邻接表和逆邻接表的一种数据结构
* 时间复杂度和邻接表相同
* 因此在有向图中， 它是很好的数据结构
*/
#include <stdio.h>
#include <assert.h>
#include <malloc.h>
enum { verMax = 10 };
typedef int VertexType;
typedef int EdgeType;//权
//边表节点结构
typedef struct EdgeNode
{
int adjvex;
int again_adjvex;
struct EdgeNode* again_next;
struct EdgeNode* next;
EdgeType weight;
}EdgeNode;
//顶点表
typedef struct VertexNode
{
VertexType data;
EdgeNode* firstin; //逆邻接表边表的下一个节点
EdgeNode* firstout; //邻接表边表的下一个节点
}CrossList[verMax+1], VertexNode;
typedef struct CrossGraph
{
int EdgeNum, VertexNum;
CrossList crosslist;
}CrossGraph;
void Create_graph(CrossGraph *G)
{
int i, j, k, w;
EdgeNode *e;
EdgeNode *q;
printf("请输入顶点，边数:");
scanf("%d,%d", &G->VertexNum, &G->EdgeNum);
printf("请输入顶点:");
for(k = 1; k <= G->VertexNum; ++k)//初始化顶点表
{
scanf("%d", &G->crosslist[k].data);
G->crosslist[k].firstin = NULL;
G->crosslist[k].firstout = 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->next = NULL;
e->again_next = NULL;
e->again_adjvex = i;//逆邻接表边表节点
e->adjvex = j; //邻接表
e->next = G->crosslist[i].firstout;
G->crosslist[i].firstout = e;
//比邻接表多了一个入度的表示
e->again_next = G->crosslist[j].firstin;
G->crosslist[j].firstin = e;
}
}
int main()
{
CrossGraph *G;
int i = 0, j = 0;
EdgeNode *e;
G = (CrossGraph *)malloc(sizeof(CrossGraph));
assert(G != NULL);
Create_graph(G);
printf("邻接表\n");
for(i = 1; i <= G->VertexNum; ++i)
{
printf("|%d|->", G->crosslist[i].data);
e = G->crosslist[i].firstout;
while(e != NULL)
{
printf("%d->", e->adjvex);
e = e->next;
}
printf("NULL\n");
}
printf("逆邻接表\n");
for(i = 1; i <= G->VertexNum; ++i)
{
printf("|%d|<-", G->crosslist[i].data);
e = G->crosslist[i].firstin;
while(e != NULL)
{
printf("%d<-", e->again_adjvex);
//标记 , 注意逆邻接表的标量， 分清next 和 again_next!
e = e->again_next;
}
printf("NULL\n");
}
return 0;
}
4.邻接多重表
如果我们更加关注边的操作，且存在删除边的操作，那么邻接多重表是个不错的选择。
上面的结构删除一个边要执行多个操作
看下邻接多重表的表示，重点注意下边结构的5个组成部分（ivex, ilink, jvex, jlink, weight），稍候解释
右图是执行插入边E1(v1,v3)和边E2(v3,v4)后邻接多重表的样子
先说下插入的过程，然后在解释为什么这样，比较好理解。
1.插入边E1（v1, v3），此时顶点集合（竖着的表格）指针域都为NULL，因为边E1是v1和v3点组成， 顶点集v1和v3都要更新，也就是箭头1和2，都指向了边E1（v1,v3）。
2.接下来插入边E2（v3,v4），判断边E2（v3,v4）的第一个节点是v3，那么在顶点集合（v1,v2,v3,v4）中找寻v3，找到了后看v3的指向，如果为NULL则让
顶点集合的v3的指针域指向（和上面1一样），不为NULL（此时不为NULL）则一直向后寻找，更新发现jlink为NULL，让这个NULL指针指向新插入的边。如右图的箭头指
针3，接下来判断E2边的第二个组成节点是v4，那么先看顶点集合v4的指针为NULL，和步骤1一样直接更新指向E2即可，不用向后寻找。
明白了这个操作之后，说说为什么。不明白再看下，不是很好理解 ^ _ ^
邻接多重表是以边来添加到图结构中的，所有表示的边无非依靠的就是图中的全部顶点而已，那么顶点集合（上图竖着的表）其实就是起了一个开头的作用，
后面所有出现v1节点的边都会通过顶点集合的v1指针（只有1个，开头），加上后面的包含v1节点的边结构中的ilink或者是jlink来连接起来（ilink还是jlink根据
v1是边的ivex还是jvex）。
还没理解的话看看顶点集的v3和箭头2，3，串起来了所有的包含v3的边。
这样顶点集加上边集合我们就能访问这个图结构，顶点v1串起来所有包含v1的边，顶点v2串起来的所有包含v2的边。
删除边的时候我们只需要改变指针ilink和jlink即可，很方便。
代码：
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
enum { verMax = 10 };
typedef int VertexType;
typedef int EdgeType;
//边节点信息
typedef struct EdgeNode
{
int mark; //标记是否访问过
int ivex;
int jvex;
struct EdgeNode* ilink;
struct EdgeNode* jlink;
int weight;
}EdgeNode;
//顶点信息
typedef struct VertexNode
{
VertexType vertex;
EdgeNode* firstEdge;
}Adjmulist[verMax+1], VertexNode;
//图结构
typedef struct
{
int VertexNum, EdgeNum;
Adjmulist adjmulist;
}adjmulistGraph;
void Print_Graph(adjmulistGraph *G)
{
int i;
EdgeNode* p;
for(i = 1; i <= G->VertexNum; ++i)
{
p = G->adjmulist[i].firstEdge;
while(p != NULL)
{
if(p->ivex == i) //判断相等才能知道连接上的是ivex还是jvex;
{
printf("%d--%d\n", G->adjmulist[p->ivex].vertex, G->adjmulist[p->jvex].vertex);
p = p->ilink;
}
else//jvex
{
printf("%d--%d\n", G->adjmulist[p->jvex].vertex, G->adjmulist[p->ivex].vertex);
p = p->jlink;
}
}
}
}
void Create_Graph(adjmulistGraph *G)
{
int criculate;
int vertex[2]; //需要测试一条边的两个点
EdgeNode *p, *newedge;
int i;
int w;
printf("请输入顶点，边数:");
scanf("%d,%d", &G->VertexNum, &G->EdgeNum);
printf("请输入顶点:");
for(i = 1; i <= G->VertexNum; ++i)
{
scanf("%d", &G->adjmulist[i].vertex);
}
criculate = G->EdgeNum;
while(criculate--)
{
printf("请输入v1,v2");
scanf("%d,%d,%d", &vertex[0], &vertex[1], &w);
newedge = (EdgeNode*)malloc(sizeof(EdgeNode));
assert(newedge != NULL);
newedge->ivex = vertex[0];
newedge->jvex = vertex[1];
newedge->weight = w;
//组成一条边的两个点都要处理
for(i = 0; i < 2; i++)
{
p = G->adjmulist[vertex[i]].firstEdge;
if(p == NULL)
{
G->adjmulist[vertex[i]].firstEdge = newedge;
}
else
{ <pre name="code" class="cpp"> //找到末尾 while((p->ilink != NULL && p->ivex == vertex[i]) || (p->jlink != NULL && p->jvex == vertex[i])) { if(vertex[i] == p->ivex) p = p->ilink; else// ==jvex p = p->jlink; } if(p->ivex == vertex[i]) p->ilink = newedge; else p->jlink
= newedge; } } }}int main(){ adjmulistGraph *G; G = (adjmulistGraph*)malloc(sizeof(adjmulistGraph)); assert(G != NULL); Create_Graph(G); printf("\n\n"); Print_Graph(G); return 0;}
5.边集数组
更加关注的是边的集合且依次对边处理的操作，但是如果要查找一个顶点的度，需要扫描整个集合，效率并不高，使用一个二维数组表示即可。
这个没什么好说的，每个边表示起点终点权重等。
最后放下这几个图存储结构的比较
参考书籍：《大话数据结构》
《数据结构与算法分析 -- c语言描述》
有问题一起讨论哈