图的存储方法

图的存储方法

• 邻接矩阵
• 前向星
• 链式前向星

1.邻接矩阵存图

逻辑结构分为两部分：V和E集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵
------百度百科

1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

//数据
int G[maxn][maxn];
int w[maxn];
int n,m;
int x,y;
for(int i=1;i<=m;i++)
{
	scanf("%d%d",&x,&y);
	G[x][y]=0;
	scanf("%d",&w[x][y]); 
} 

是一种比较容易掌握的存图方法，但是缺点是空间消耗太大，无论有几条边，都需要占用n²的空间

2.前向星存图

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
同样来自百度百科的说

struct edge{
	int v;//结点 
	int w;//边权 
}l;
vector<edge> G[maxn];
int n,m;
int x;
for(int i=1;i<=m;i++)
{
	scanf("%d%d%d",&x,&l.v,&l.w);
	G[x].push_back(l); //表示x点所连的点有G[x].v，边权为G[x].w  
} //当我查询时，可以直接查询边权。 

这种方法也是一种比较好理解的方法

3.链式前向星存图（玄学存图QAQ）
接下来有请白学家登场（鼓掌~~

链式前向星是ssfz神牛Malash创造的（至少Baidu上没有搜到）名词，或许这种数据结构有其他更加正规易懂的名字，但我还是没有搜到。（有一个资料称之为加上next数组前向星，但这个名字实在不好） 该数据结构可能是Jason911神牛或其他神牛发明的。
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。

为什么我觉得vector加数组存图是邻接表呢

struct edge{
	int next;//下一条边的存储下标 
	int v;//这条边的终点 
	int w;//权值 
}G[maxm];
int n,m,cnt;
int head[maxn]; 

void add(int u,int v,int w)//起点，终点，权值
{
	edge[++cnt].next=head[u];
	edge[cnt].w=w;
	edge[cnt].next=v;
	head[u]=cnt;
 } //这里的操作有点类似于链表 
 int main() {
	int s, t, w;
	cin >> n >> m;
	for(int i=1; i<=m; i++) {
		cin >> s >> t >> w;
		Add(s, t, w);
	}
}

下面再给出遍历的方法

for(int i=head[st]; i!=0; i=edge[i].next) //就把这个东西当成跟线性表的顺序遍历一样

以上就是图的3种存储方法了，还有其他的方法（蒟蒻我不会

背上了剑离开这里 深深地吸一口气 给自己鼓励
这片泥泞不堪的地 也不知道留下了 多少的足迹
时光一点一点流转成了回忆
陌生的天空也渐渐地 变熟悉
虽然这一路上很多次想放弃
但是我拼命坚持到了这里
我站在这个洒满阳光雨后初晴的世界里
俯瞰着的风景多美丽
不需要太多的勇气 只需要有一点点毅力
最终 结局 便是胜利
时光流转从前 光阴如梦似箭
阳光有点刺眼 雨天也很讨厌
但是我相信着
这个世界给予我们的 也不尽全部是考验

刀剑3真好看，虽然是1的图
刀剑3我吹爆

2018.10.13