几种图的存储结构的比较

顺序存储结构、链式存储结构、索引存储结构、散列存储结构在计算机科学中，数据的存储和组织方式对于数据的访问和处理起着至关重要的作用。

不同的存储结构在不同的场景下有着各自的优势和不足。

在本文中，我们将介绍四种常见的存储结构：顺序存储结构、链式存储结构、索引存储结构和散列存储结构，并讨论它们的特点和应用。

首先，我们来介绍一下顺序存储结构。

顺序存储结构是一种连续存储数据的方式，数据元素依次存储在内存中的连续位置上。

顺序存储结构具有存取速度快的优点，可以通过下标直接访问指定位置的数据元素。

对于需要频繁访问数据的场景，顺序存储结构是一个不错的选择。

然而，顺序存储结构的缺点是插入和删除操作比较低效，因为需要移动其他数据元素的位置。

接下来，我们介绍链式存储结构。

链式存储结构使用指针将数据元素连接起来，每个数据元素包含一个指向下一个元素的指针。

链式存储结构相对于顺序存储结构来说，插入和删除操作的效率更高，因为只需要修改指针的指向即可。

链式存储结构还可以动态地分配内存空间，不受限制于固定大小的内存块。

然而，链式存储结构的缺点是访问数据元素的效率比较低，需要通过遍历链表来查找指定元素。

接下来，我们介绍索引存储结构。

索引存储结构是在原始数据之上建立索引的方式。

索引存储结构通过建立一个索引表来存储关键字和指向对应数据的指针。

通过索引表，可以快速地定位到指定关键字对应的数据元素。

索引存储结构适用于需要频繁查找特定数据的场景，能够提高数据的查找效率。

然而，索引存储结构的缺点是需要额外的存储空间来存储索引表，并且在插入和删除数据时需要同时更新索引表。

最后，我们介绍散列存储结构。

散列存储结构是根据数据的关键字直接计算出存储位置的方式。

散列存储结构通过散列函数将关键字映射到存储位置，不需要进行比较和遍历操作。

散列存储结构的优点是可以快速地定位到数据元素，具有较高的存取效率。

然而，散列存储结构可能会出现冲突，即不同的关键字映射到同一个存储位置的情况，需要解决冲突的方法，如链地址法和开放地址法。

图的常⽤存储结构⼀、邻接矩阵 邻接矩阵是简单的也是⽐较常⽤的⼀种表⽰图的数据结构，对于⼀个有N个点的图，需要⼀个N*N的矩阵，这个矩阵的i⾏第j列的数值表⽰点vi到点vj的距离。

邻接矩阵需要初始化，map[i][i] = 0;map[i][j] = INF(i != j)，对于每组读⼊的数据vi,vj,w(vi为边的起点,vj为边的终点,w为边的权值),赋值map[vi][vj] = w，另外邻接矩阵的值和边的输⼊顺序⽆关。

对于邻接矩阵来说，初始化需要O(n^2)的时间，建图需要O(m),所以总时间复杂度是O(n^2)，空间上，邻接矩阵的开销也是O(n^2)，和点的个数有关。

⼆、前向星 前向星是⼀种通过存储边的⽅式来存储图的数据结构。

构造的时候，只需要读⼊每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完毕，为了查询⽅便，经常会有⼀个数组存储起点为vi的第⼀条边的位置. 由于涉及排序，前向星的构造时间复杂度与排序算法有关，⼀般情况下时间复杂度为O(mlogN)，空间上需要两个数组，所以空间复杂度为O(m + n),有点在于可以应对点⾮常多的情况，可以存储重边，但是不能直接判断任意两个顶点之间是否有边.1 #include <iostream>2 #include <cmath>3 #include <cstdio>4 #include <cstring>5 #include <cstdlib>6 #include <algorithm>7using namespace std;8 typedef long long LL;910const int MAXN = 1000 + 3;11int head[MAXN]; //存储起点为Vi的边第⼀次出现的位置1213struct NODE14 {15int from;16int to;17int w;18 };19 NODE edge[MAXN];2021bool cmp(NODE a, NODE b)22 {23if(a.from == b.from && a.to == b.to) return a.w < b.w;24if(a.from == b.from) return a.to < b.to;25return a.from < b.from;26 }2728int main()29 {30 freopen("input.txt", "r", stdin);31int n,m;32 cin >> n >> m;33for(int i = 0; i < m; i++)34 {35 cin >> edge[i].from >> edge[i].to >> edge[i].w;36 }37 sort(edge, edge + m, cmp);38 memset(head, -1, sizeof(head));39 head[edge[0].from] = 0;40for(int i = 1; i < m; i++)41 {42if(edge[i].from != edge[i - 1].from)43 {44 head[edge[i].from] = i;45 }46 }47for(int i = 1; i <= n; i++)48 {49for(int k = head[i]; edge[k].from == i && k < m; k++)50 {51 cout << edge[k].from << '' << edge[k].to << '' << edge[k].w <<endl;52 }53 }54for(int i = 0; i <= n; i++)55 {56 cout << head[i] << "";57 }58 cout << endl;59return0;60 }三、链式前向星 链式前向星采⽤数组模拟链表的⽅式实现邻接表的功能，并且使⽤很少的额外空间，是当前建图和遍历效率最⾼的存储⽅式.数组模拟链表的主要⽅式是记录下⼀个节点的数组的在哪⼀个位置。

图的存储方法主要有邻接矩阵和邻接表两种。

1. 邻接矩阵：将图中的节点用一个二维数组来表示，如果节点i到节点j之间有一条边，则在数组中对应位上标识出来。

这是一个常用的存储方式，它可以快速地判断任意两个节
点之间是否有直接的连接关系。

但是当图中存在大量的无向边时（即所有的元素都不相
互连通）会造成内存浪费。

2. 链表法: 对于无向图而言, 我们可以使用单链表或者双向链表来保存诸如“v1->v2”
这样的信息, 其中 v1 和 v2 既代表了一条无向连通关系也代表了它们之间所包含的信
息(例如: 距离、时间、代价) , 这样就能够很好地避免内存浪费, 同时更加方便
快速地定位特定连通关系所包含的信息。

图的3种储存⽅式图的储存⽅式有三种⼀。

邻接矩阵 优点：简洁明了，调⽤⽅便，简单易写； 缺点：内存占⽤⼤，⽽且没办法存重边（可能可以，但我不会），点的个数超过 3000 直接爆炸 适⽤范围：点的个数少，稠密图，⼀般结合floyed使⽤，可以传递闭包。

代码：scanf("%d%d",&u,&v,&w);a[u][v]=w;a[v][u]=w;// 双向边⼆。

邻接表 优点：占⽤空间⼩，可以快速查找每个点的出度，重边可以存，写着较为⽅便 缺点：查找和删除边很不⽅便，对于⽆向图，如果需要删除⼀条边，就需要在两个链表上查找并删除，⽤了STL，速度会慢 适⽤范围：⼤部分情况，不要求删除边就⾏ 代码：struct Edge{int v,w;};vector <Edge> edge[maxn];void addedge(int u,int v,int w){edge[u].push_back({v,w});edge[v].push_back({u,w});//双向边}三。

链式前向星 优点：⽐邻接表还省空间，可以解决某些卡空间的问题，删除边也很⽅便，只需要更改next指针的指向即可，速度也快 缺点：好像就是写的⿇烦，理解⿇烦，性能好像很猛 适⽤：需要删除边的题⽬，速度时间都要求⾼的题⽬ 代码：struct Edge{int to,w,next;}edge[maxn*2];int cnt,head[maxn],s,t,n,m;void addedge(int u,int v,int w){edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt;}struct Pre{int v,edge;}pre[maxn]; 解释:这是⽐较难理解的⼀种⽅式,所以做⼀下解释,主要是看别⼈的博客看懂的 对于上图,输⼊为 1 2 2 3 3 4 1 3 4 1 1 5 4 5 对于上⾯的结构体， 其中edge[i].to表⽰第i条边的终点 ,edge[i].next表⽰与第i条边同起点的下⼀条边的存储位置, edge[i].w为边权值. 数组head[],它是⽤来表⽰以i为起点的第⼀条边存储的位置,　head[]数组⼀般初始化为-1　实际上你会发现这⾥的第⼀条边存储的位置其实在以i为起点的所有边的最后输⼊的那个编号. 有了以i为起点的第⼀条边的储存位置和同起点下⼀条边的储存位置我们就可以便利这个i点的每⼀条边了 初始化cnt = 0,这样,现在我们还是按照上⾯的图和输⼊来模拟⼀下: edge[0].to = 2; edge[0].next = -1; head[1] = 0; edge[1].to = 3; edge[1].next = -1; head[2] = 1; edge[2].to = 4; edge[2],next = -1; head[3] = 2; edge[3].to = 3; edge[3].next = 0; head[1] = 3; edge[4].to = 1; edge[4].next = -1; head[4] = 4; edge[5].to = 5; edge[5].next = 3; head[1] = 5; edge[6].to = 5; edge[6].next = 4; head[4] = 6; 很明显,head[i]保存的是以i为起点的所有边中编号最⼤的那个,⽽把这个当作顶点i的第⼀条起始边的位置. 这样在遍历时是倒着遍历的,也就是说与输⼊顺序是相反的,不过这样不影响结果的正确性. ⽐如以上图为例,以节点1为起点的边有3条,它们的编号分别是0,3,5 ⽽head[1] = 5 我们在遍历以u节点为起始位置的所有边的时候是这样的: for(int i=head[u];~i;i=edge[i].next) 那么就是说先遍历编号为5的边,也就是head[1],然后就是edge[5].next,也就是编号3的边,然后继续edge[3].next,也就是编号0的边,可以看出是逆序的.。

数据结构图的存储结构及基本操作数据结构图的存储结构及基本操作1·引言数据结构图是一种用来描述数据元素之间关系的图形结构，它可以表示实体之间的联系和依赖关系。

本文将介绍数据结构图的存储结构及基本操作。

2·存储结构2·1 邻接矩阵邻接矩阵是使用二维数组来表示数据结构图中各个节点之间的关系。

矩阵的行和列代表节点，如果两个节点之间存在边，则矩阵相应位置的值为1，否则为0。

2·2 邻接表邻接表是使用链表来表示数据结构图中各个节点之间的关系。

每个节点都有一个链表，链表中的每个元素表示与该节点相邻的节点。

2·3 十字链表十字链表是使用链表来表示数据结构图中各个节点之间的关系。

每个节点都有两个链表，一个表示该节点指向的节点，另一个表示指向该节点的节点。

2·4 邻接多重表邻接多重表是使用链表来表示数据结构图中各个节点之间的关系。

每个节点都有一个链表，链表中的每个元素表示与该节点相邻的边。

3·基本操作3·1 创建图创建一个空的数据结构图，根据需要选择适当的存储结构。

3·2 插入节点在数据结构图中插入一个节点，并建立与其他节点的关系。

3·3 删除节点从数据结构图中删除一个节点，并删除与其他节点的关系。

3·4 插入边在数据结构图中插入一条边，连接两个节点。

3·5 删除边从数据结构图中删除一条边，断开两个节点的连接。

3·6 遍历图按照某种规则遍历整个数据结构图，访问每个节点。

本文档涉及附件：无本文所涉及的法律名词及注释：1·邻接矩阵：用于表示图的存储结构，矩阵的行和列代表图的节点，矩阵的值表示节点之间的连接关系。

2·邻接表：用于表示图的存储结构，每个节点都有一个链表，链表中的每个元素表示与该节点相邻的节点。

3·十字链表：用于表示图的存储结构，每个节点都有两个链表，一个表示该节点指向的节点，另一个表示指向该节点的节点。

图的种类及储存⽅式⼀.图的种类（以下的分类不是并列的）1.有向图：图中边的⽅向是⼀定的，不能逆序⾛。

2.⽆向图：图中的边没有⽅向，可以逆序⾛。

没有正负⽅向3.完全图：完全图：对于顶中的每⼀个顶点，都与其他的点有边直接相连⽆向完全图：任意⼀个具有n个结点的⽆向简单图，其边数n*(n-1)/2;我们把边数恰好等于n*(n-1)/2的n个结点的称为完全图。

有向完全图：在⼀个n个结点的中，最⼤边数为n*(n-1)。

4.稀疏图和稠密图：⼀般的对于⼀个图来说，边的数⽬多的就是稠密图，边的数⽬少的就是稀疏图。

5.⼆部图与完全⼆部图（⼆部图也就是⼆分图）⼆分图的概念：简⽽⾔之，就是顶点集V可分割为两个互不相交的⼦集，并且图中每条边依附的两个顶点都分属于这两个互不相交的⼦集，两个⼦集内的顶点不相邻。

两个⼦集：A，B；性质满⾜：A∩B=∅，A∪B=V，这就是⼆分图。

6.图的⽣成树：把图中的n个点，和图中的n-1条边挑出来，如果这n-1条边能把这n个点连起来，那这就是图的⼀个⽣成树7.有向⽹，⽆向⽹：⽹就是加权的图8.活动⽹络：AOV图：顶点是活动，有向边表⽰活动之间的前驱后继关系--拓扑排序AOE图：E，也就是⽤边表⽰活动，⽤边表⽰的⽬的是利⽤边的权值，⽐如⽤边的权值表⽰最长时间--关键路径⼆：图的存储表⽰1. 邻接矩阵也就是⽤jz[i][j]表⽰i--j的连通情况，可以表⽰权值，也可以表⽰是否连通。

2.邻接表：就是把同⼀个顶点出发的边的链接储存在同⼀个边链表中，边链表的每⼀个结点代表⼀条边，称为边结点，边结点包括的信息可以⾃⼰确定。

⼀种⽅法：g[i][j]代表从i出发的第j条边的编号，对应着edge数组中的储存着边的信息，可以直接从g[i]得到从i出发的边的数⽬。

另⼀种就是边表了。

3.边表：就不介绍了，因为⼀直以来我都是⽤“邻接矩阵”和“边表”的，⽐较熟悉。