算法竞赛备赛——【图论】链式前向星

图论

图的存储方式：

通用的三种：邻接矩阵、邻接表、边集数组

有向图：十字链表

无向图：多重邻接表

刷题常用：邻接矩阵、链式前向星（邻接表变形）

链式前向星

算法题常用:

邻接矩阵、二维vector模拟邻接表、链式前向星

n个点 m条边 m>nlogn算稠密图 m<nlogn算稀疏图

稠密图：邻接矩阵 O(n^2)

稀疏图：邻接表---->二维vector（无权）/链式前向星（带权） O(n+m) （边多了连的多不合适）

无权无向图

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=5e4+5; 

//无权无向图 ---->二维vector 模拟邻接表 多用于存无权图
int n,m;

vector<vector<int>> g;
int v[105];

void dfs(int x){
	if(v[x]) return;
	printf("%d ",x); 
	v[x]=1;
	int y;
	for(int i=0;i<g[x].size();++i){
		y=g[x][i];
		dfs(y);
	}
}

int main(){
	cin>>n>>m;
	g.resize(n+1);
	int x,y;
	for(int i=1;i<=m;++i){
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;++i){
		if(v[i]==0) dfs(i);
	}
	return 0;
}
/*输入样例 
4 5
1 2
1 4
2 3
2 4
3 4
*/

有权无向图

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=5e4+5; 

//带权无向图 ---->链式向前星 ----> 静态链表模拟邻接表 
int n,m;
int head[105]; 
int v[105]; 
struct edge{
	int to;//该边的终点 
	int w;//该边的权值 
	int nex;//和该边同起点的另一条边的下标 
}e[10005];//边的条数最大为n*(n-1) 

int cnt=0;
void add(int x,int y,int wi){
	//x--wi->y
	e[cnt].to=y;
	e[cnt].w=wi;
	//模拟链表的头插法 
	e[cnt].nex=head[x];
	head[x]=cnt;
	
	cnt++;
}

void dfs(int x){
	if(v[x]) return ;
	printf("%d ",x);
	v[x]=1;
	for(int i=head[x];i!=-1;i=e[i].nex){//枚举x所有出边 找x的临界点 
		int y=e[i].to;
		dfs(y); 
	}
}

int main(){
	memset(head,-1,sizeof head);
	cin>>n>>m;
	int x,y,wi;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>wi;
		add(x,y,wi);
		add(y,x,wi);
	}
	for(int i=1;i<=n;++i){
		if(v[i]==0) dfs(i);
	}
	return 0;
}
/*输入样例 
4 5
1 2 5
1 4 3
2 3 8
2 4 12
3 4 9
*/