图的存储

邻接矩阵

边集数组
Kruskal算法中，我们需要直接对边按权重排序，需要这么存
结构体存第i条边的{起点u，终点v，边权w}
遍历的时候在查 这是第几条边 这条边的起点和循环中的遍历变量是否对得上

void dfs(int u){
	vis[u] = true;
	for(int i = 1; i <=m;i++)//m是其中所有的边的数量，我们在枚举每个编号，一个编号对应了一条边
	//验证的是 dfs进入的起点和当前编号的边的起点是否相同 
		if(e[i].u==u){ //如果第一条边的起点 == 我函数进入的起点那么说明就是找到了一组
			int v= e[i].v, w=e[i].w //取出这个编号的组里的终点
			cout<<u<<v<<w;
			if(vis[v]) continue; //如果终点 作为起点已经被遍历过了，就跳过这个点
			dfs(e[i].v); //搜到底了，dfs往回退一层，这条边的起点上，再通过for循环找他的另一个边的编号
			//还是找不到的话就继续退一格，二叉树的话就直接退到顶，然后遍历编号，到另一枝
		}
}

邻接表 不能处理反向边
使用的是出边数组 存的是u这个点的所有出边和权重，出边和权重是一个组作为链表吊在以点编号的数组后面
形状和哈希表是一样的

也就是说 与该点相连的点的信息都存储在该点的后面吊着

搜的时候是一个道理

void dfs(int u,int fa){
	for(auto ed:e[u]){//遍历这个点的出边，也就是吊着的那部分
		int v=ed.v, w=ed.w;
		if(v==fa) continue //这个出边的父节点如果搜过，就跳过 因为无论是父子节点，在邻接表里都表现为吊在后面 在ed：e[u]这个环节会把这个点的上面那条边和所有的枝都探一遍，所以需要一个fa来修正往下搜的方向
		cout << u << v << w;
		dfs(v,u)//再把搜到的出边作为起点 继续往下搜
	}
}

链式邻接表 每条边 两个点 不同方向存了两次，可以处理反向边的问题了
边集数组 存储第j条边的{起点u，终点v，边权w} 和之前边集数组的方式是一致的
表头数组 存储u点的所有出边的编号
表头数组定义成 也就是单个元素是数组的可变长数组 这是一个数组，数组里的每一个元素又都是数组，套娃了

和 之前的这个 边集数组存的 边的编号 的数组有一些不同，这个数组，反复存了 一组（两个点，一条边，方向不同）正反存两次，大小是之前那个数组的两倍

关于表头数组的理解 存的是 这个点，这个点的表示主要就反映在u上面 就是第一个点，他的相邻边都在下标是 的vector数组里

struct edge{int u,v,w;};
vector<edge> e;
vector<int> h[N];
 
void add(int a,int b,int c){
	e.push_back({a,b,c}); //数组e，每个元素是结构体，每个格子存每个 边点 的信息
	h[a].push_back(e.size()-1) //vector数组的下标是h[a] a是起点，vector [h[a]] 里面存的是连接了该点的边 e.size()-1这里记录的是第几条边，也就是给边编号然后吊在数组下面的过程
}
void dfs(int u,int fa){
	for(int i = 0; i<h[u].size();i++){ //起点是点，但是遍历的是与点相关的边 h[u].size 是与该点相连的边的条数
		int j = h[u][i]; //取出这条边 h[u] 看成一个H[] H[i]是它的第几个边
		int v = e[j].v, w = e[j].w/
		if(v == fa) continue; //他是八爪鱼一样在搜，相连的都探，验证父节点是否探过，保证是往下搜
		cout << u << v << w;
		dfs(v,u); //往下搜一层，进来的起点变成下一层的终点
	}
}

链式前向星 边集数组是头插法插进去的，越后插进去的越先访问，这一点和前面尾插法的边集数组不同
大体思路和上面差不多，但是把链式邻接表的表头数组和边集数组升级了
存了三个东西，分别是 终点v，边权w，下一条边ne
里面 读进来的第一个点的 add(a,b,c) 也就是这里的a，它的第一条出边的编号，也就是说先读了一个(4,3) 又后来读了一个(4,5)，通过更新，h里面会存4的第一个出边也就是3

struct edge{int v,w,ne;};
edge e[M];
int idx,h[N]; //idx 用来形成每条边的编号，读入的第一组abc 获得编号0 诸如此类
 
void add(int a,int b,int c){
	e[idx] = {b,c,h[a]};
	h[a] = idx++; 
}
 
void dfs(int u,int fa){
	for(int i = h[u]; ~i; i = e[i].ne){ //循环里的逻辑是 u是一个起点，h[u]是一个这个起点的一个出边
	//只要这个边 i 没有搜到录入的第一条边，也就是编号0，说明这个图还没走完，i 更新为这条边对应的出点
	//这个出点存在e里
		int v = e[i].v, w=e[i].w;
		if(v==fa) continue;
		cout<<u<<v<<w;
		dfs(v,u);
	}
}