「Day 4—图的存储 & 图上搜索」

图的基本操作

图的存储

1.邻接矩阵

//对于一个正常的边 (u,v,w)
vector<int> a[MAXN];
a[u].push_back(v);
a[v].push_back(u);

2.链式前向星

//对于一个正常的边 (u,v,w)
struct node{
	int to,next,len;
}e[MAXN];
int tot = 0,h[MAXN];
void add(int x,int y,int len){
	e[++ tot] = {y,h[x],len};
	h[x] = tot;
}

图的遍历

1.邻接矩阵

for(int i = 1;i <= n;i ++){
	for(auto x:a[i]){
		cout << x << " ";
	}
}

2.链式前向星

for(int i = h[x];i;i = e[i].next){
	int to = e[i].to;
	int v = e[i].len;
	cout << i << ' ' << to << " " << v;
}

习题

图的存储

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,m;
vector<int> a[500005];

int main(){
	int T;
	cin >> T;
	while(T --){
		cin >> n >> m;
		for(int i = 1;i <= n;i ++){
			a[i].clear();
		}
		for(int i = 1;i <= m;i ++){
			int u,v;
			cin >> u >> v;
			a[u].push_back(v);
		}
		for(int i = 1;i <= n;i ++){
//			if(a[i].size() == 0){
//				cout << "\n";
//				continue;
//			}
			sort(a[i].begin(),a[i].end());
			for(int j = 0;j < a[i].size();j ++){
				cout << a[i][j] <<" ";
			}
			cout << "\n";
		}
	}
		
	return 0;
}