困扰我的邻接表的插入边的函数,今天我弄明白了
作者:
曾炜堃
,
2021-09-03 00:05:49
,
所有人可见
,
阅读 717
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500 ;
int h[N],e[N],ne[N],idx; // 邻接表
//ps : 边从第0条开始
/*
首先,我们开三个数组:
head[i]表示以i为起点的第一条边的存储位置)。说是第一条边,其实是最后读入(编号最大)的边,只是便于从头扫边。
next[i]表示与第i条边同起点的下一条边的存储位置。下一条边,反而是前一个由起点扩展的边,只是便于跳边。
e[i]表示第i条边的终点。(即当前边连向的点)
v[i]表示第i条边的权值(视情况决定是否使用)
*/
/*
怎么建图?
这里用一个add过程。
tot代表当前第几条边,
x为起点,
y为终点,
z为权值(视情况决定是否使用)。
tot++
//为边编号。
e[tot]=y,v[tot]=z
//标终点与权值
next[tot]=head[x]
//当前边的下一个边连给当前的头
head[x]=tot
*/
//当前点的第一个边设为当前边
void add(int a,int b){ // 添加 a 指向 b 的边
e[idx]=b; //表示第i条边的终点 (即当前边连向的点)
ne[idx]=h[a]; //h[i]表示以i为起点的第一条边的存储位置 说是第一条边,其实是最后读入(编号最大)的边,只是便于从头扫边。
//一开始是自带一条位置为-1的边的
//所以以i为起点第一条边的下一条边的存储的位置就是-1
//next[i]表示与第i条边同起点的下一条边的存储位置。下一条边,反而是前一个由起点扩展的边,只是便于跳边。
//当前边的下一个边连给当前的头
h[a]=idx;
//当前的边设为第一条边即第0条边
//然后此时h[a]也就是表示以i为起点的第一条边的存储位置 说是第一条边,其实是最后读入(编号最大)的边,只是便于从头扫边。
//所以h[a]就等于了idx,也就是说,h[a]指向了idx
idx++;
//全局变量,依次自增+1
}
int main()
{
memset(h, -1, sizeof h);
add(1,2),add(1,3),add(1,4) ;
//枚举每条边,输出的e[i]其实是头插之后的每个的终点
//即 1--->-1
// 1--->2--->-1
// 1--->3--->2--->-1
// 1--->4--->3--->2--->-1
for(int i = h[2] ; i != -1 ; i = ne[i])
cout << e[i] << endl ;
return 0 ;
}
不知道在说什么。。。
厉害
感觉很详细,但我就是听不懂😭
感谢!很清晰