邻接表存储图或者树

邻接表存储图或者树

大家好，我叫徐锦桐，个人博客地址为www.xujintong。平时记录一下学习计算机过程中获取的知识，还有日常折腾的经验，欢迎大家来访。

介绍

• 每个顶点都作为头节点，并且存在一个一维数组中h[N]。
• 树就是相当于一种有向图。
• 存储无向图的时候直接add(a, b), add(b, a)就行了。
• 常用于稀疏图。
  

源码

初始化

int h[N], e[N], ne[N], idx = 0;
memset(h, -1, sizeof h);

添加a到b的一条有向连接

void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}