数组模拟邻接表 #图论
文章目录
- 为什么要用数组来模拟邻接表
- 存储思路
- 遍历思路
树是特殊的图，因此邻接表可以存储图和树两种数据结构。
为什么要用数组来模拟邻接表
在算法设计当中，利用数组来代替结构体模拟各种数据结构会更加简单。
存储思路
给定如下数据,我们可以构造如下的一个邻接表
请看代码
/**
idx:索引,代表数组哪个位置,是否连续不重要,
因为我们的存储是链式的。
h[idx] : 顶点表,下标idx代表是哪个顶点,初始值全部为-1,代表没有数据
e[idx] : 边表,下标idx存储的边值
ne[idx] : 索引为idx的下一个索引
其中a是顶点,b是边表。即a指向b
如果其是一个无向图，那么我们可以建立a指向b和b指向a。
如果其实一个树,那么a代表父节点,b代表孩子节点
**/
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
遍历思路
下面演示遍历1号头结点
for(int i=h[1]; i!=-1; i=ne[i]){
int j=e[i];//当前边的值
cout<<j;
}