链式前向星存图

一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，根据边的起点将边存入对应链表中。通过和链表一样的遍历可以查出以某个点出发的边。除了不能直接用起点终点定位以外，前向星几乎是完美的。

边

每条边需要包含一下信息

1. 这条边的起点
2. 这条边的重点
3. 下一条同样起点的边的地址
4. 权值（可选）

struct edge{
	int from, to, next;
}E[1000010]; 

示例

假设我们要存一张这样的图：

那它在内存中应该是这么存储的：

图的构建

依次插入所有的边。

每次插入边时，总是更改链表头部。

void addEdge(int from, int to){
	E[++cnt].from=from;
	E[cnt].to=to;
	E[cnt].next=head[from];
	head[from]=cnt;
}

图的遍历

可以通过DFS或BFS。

这里只给出怎么从前向星里获得以某个点为起点的所有边，具体如何用DFS或BFS根据实际情况。

int temp=head[x]; //x是图中某个点
while(temp!=0){
		//dfs到E[temp].to
		//bfs到E[temp].to
		temp=E[temp].next;
}