数组模拟邻接表

邻接表

可以用链表实现，也可以用数组实现。

const int N = 100000;
struct e {
	int to, w, next;
} edge[N];
int head[N], cnt = 0;

void add(int u, int v, int w) {
	edge[cnt].to = v;
	edge[cnt].w  = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}
memset(head, -1, sizeof(head));

head数组可以理解成表头它记录了它第一条边的的坐标。
结构体数组edge[i]数组是第 i 条边，记录了它连接的下一个节点（to)，边的权值(w)，它的下一条边(next）。
列组数据
u v w ———— u是起点，v是终点，w是边权值
1 2 3
1 3 4
1 5 6
2 4 7
3 5 9
edge[0].to=2； edge[0]. w=3； edge[0].next=-1； head[1]=0
edge[1].to=3； edge[1]. w=4； edge[1].next= 1； head[1]=1
edge[2].to=5； edge[2]. w=6； edge[2].next= 2； head[1]=2
edge[3].to=4； edge[3]. w=7； edge[3].next=-1； head[2]=3
edge[4].to=5； edge[4]. w=9； edge[4].next=-1； head[3]=4
每个节点最后一条边的next都是-1；

dfs

void dfs(int u) {
	vis[u] = true;
	for(int i=head[u]; i>=0; i = edge[i].next) {
		int son = edge[i].to;
		if(!vis[son])	dfs(son);
	}
}

bfs

int queue[N];
int vis[N];
void bfs(int u) {
	int start = 0, end = 0;
	queue[0] = u;
	vis[u] = true;
	while(start <= end) {
		int parent = queue[start];
		start++;
		for(int i=head[parent]; i>=0; i = edge[i].next) {
			int son = edge[i].to;
			if(!vis[son]) {
				++end;
				queue[end] = son;
				vis[son] = true;
			}
		}
	}
}

dfs 和 bfs 都只是模板可以改改的