图的几种存储方式

介绍几种提高厨房利用率的储物方式 #生活乐趣# #生活分享# #美食生活分享# #家居生活分享#

 第一次给501的同学们讲课，所以好好准备了一下。

本博客大多为自己整理的，错误或不妥当之处还望各位多多指正！谢谢了！

本博客代码所用例题为SDUT OJ 图的存储专题的第一题-------> https://acm.sdut.edu.cn/onlinejudge3/problems/3116

废话不多说，直接上目录

图的几种存储结构：

1、邻接矩阵

2、邻接表

3、链式前向星

4、C++中vector的邻接表实现（补充）

（一）邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。

邻接矩阵的好处：

（1）直观、简单、好理解

（2）方便检查任意一对定点间是否存在边

（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

（4）方便计算任一顶点的度

对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。

对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。

邻接矩阵的局限性：时间复杂度O(n^2），空间复杂度O(n^2)

（1）浪费空间。对于稠密图还是很合算的。

                          但是对于稀疏图（点很多而边很少）有大量无效元素。

（2）浪费时间。要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

bb这么多，我们直接来以OJ此专题第一题为例

这题二维数组map不能用int，会爆内存，bool可以自己百度，简而言之就是用于逻辑判断，只有true和false两种情况。

bool类型在存储二值变量，或者说只有真假时，更具优势，因为只有0和1即false和true，省空间

（int型的0和1都是4字节，bool都是1字节）

#include<stdio.h>

#include<string.h>

#include<stdbool.h>

bool map[5001][5001];

int main()

{

int n,m;

int u,v;

int q;

while(~scanf("%d %d",&n,&m))

{

memset(map,false,sizeof(map));

while(m--)

{

scanf("%d %d",&u,&v);

map[u][v]=true;

}

scanf("%d",&q);

while(q--)

{

scanf("%d %d",&u,&v);

if(map[u][v])

{

printf("Yes\n");

}else

{

printf("No\n");

}

}

}

return 0;

}

（二）邻接表

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。

邻接表的特点如下：

（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。

（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。

（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct node

{

int data;

struct node *next;

};

int main()

{

int n, u, j, i, v;

struct node *p, *a[5050];

while(~scanf("%d", &n))

{

for(i = 0; i < n; i++)

a[i] = NULL;

for(i = 0; i < n; i++)

{

for(j = 0; j < n; j++)

{

scanf("%d", &u);

if(u == 1)

{

if(a[i] == NULL)

{

p = (struct node *)malloc(sizeof(struct node));

p -> data = j;

p -> next = NULL;

a[i] = p;

}

else

{

p = (struct node *)malloc(sizeof(struct node));

p -> next = a[i] -> next;

p -> data = j;

a[i] -> next = p;

}

}

}

}

int q;

scanf("%d", &q);

while(q--)

{

scanf("%d%d", &u, &v);

p = a[u];

int flag = 0;

while(p)

{

if(p -> data == v)

{

flag = 1;

break;

}

p = p -> next;

}

if(flag)

printf("Yes\n");

else

printf("No\n");

}

}

return 0;

}

（三）链式前向星

 https://blog.csdn.net/Binary_Heap/article/details/78209086

1. 结构

这里用两个东西：

1 结构体数组edge存边，edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)

struct edge{

int to;

int w;

int next;

}e[500010];

2.增边

若以点u为起点的边新增了一条，在edge中的下标为cnt.

那么edge[++cnt].next=head[u];然后head[u]=cnt.

即每次新加的边作为第一条边，最后倒序遍历

void add(int u, int v, int w)

{

e[cnt].to = v;

e[cnt].w = w;

e[cnt].next = head[u];

head[u] = cnt++;

}

3. 遍历

遍历以st为起点的边

for(int i=head[st]; i!=0; i=edge[i].next)

 i 开始为第一条边，每次指向下一条(以0为结束标志)  （若下标从0开始，next应初始化-1）

链式前向星主要是用来优化的，可以用来优化BFS，SPFA算法等等。在做最短路的时候一直T就是因为没有用链式前向星存边导致的超时，所以这个坑我先和你们说下。

（四）vector的邻接表（补充）

vector是C++STL里面的一个东西，简单的来说就是一个可变长的数组，你可以通过往它里面压入数据来使它变长，

想深入了解的可以自己百度一波，还是以这道题为例：

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

#define N 500001

vector<int>MAP[N];

int main()

{

int n,m,u,v,i;

while(~scanf("%d %d",&n,&m))

{

while(m--)

{

scanf("%d %d",&u,&v);

MAP[u].push_back(v);

}

int q;

scanf("%d",&q);

while(q--)

{

scanf("%d %d",&u,&v);

int len=MAP[u].size();

int flag=0;

for(i=0;i<len;i++)

{

if(MAP[u][i]==v)

{

flag=1;

}

}

if(flag)

{

cout<<"Yes"<<endl;

}else

{

cout<<"No"<<endl;

}

}

for(int i=0; i<N; i++)

{

MAP[i].clear();

}

}

return 0;

}

网址：图的几种存储方式 https://www.yuejiaxmz.com/news/view/338048

相关内容

储存方式分为哪几种
Android 五大数据存储 (最实用的开发详解) 一 五种存储方式区别
不同食品的保存方式，21种食品存储方式介绍
DAS、SAN、NAS三种存储方式的概念及应用
常见三种存储方式DAS、NAS、SAN的架构及比较
浏览器的四种本地存储方式
一种存储砧板的制作方法
生姜怎么保存不干不烂不发芽？两种新鲜生姜储存一年的方法图解
人类存储方式的变革史
新型的物品存储方式（迷你考拉仓）

随便看看