图论

树和图的存储

详情点击查看

1.树是一种特殊的图，无环连通图

所以只需要考虑图是怎么存储的

2.图分为两种：有向图和无向图

无向图是一种特殊的有向图，所以只需要考虑有向图是怎么存储的

3.有向图：

邻接矩阵 g[a, b] 存储a->b的信息，true代表有边，false代表没有边；

用的比较少，因为空间复杂度是n^2的，适合存储稠密图

邻接表 n个点，每个点上都连了一个单链表

单链表上存储该点可以走到的所有的点

树和图的遍历

详情点击查看

树和图的深度优先遍历和宽度优先遍历其实是特殊的DFS和BFS

树和图的深度优先遍历

详情点击查看

例题：树的重心

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式
第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围
1≤n≤105

#include <iostream>
#include <cstring> 

using namespace std;

const int N = 1e5 + 10, M = N * 2;//无向图有两个方向 

int h[N], e[M], ne[M], idx;
bool st[N];//记录每个点有没有被遍历到

int ans = N; 
int n;

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

//返回以u为根的子树中点的数量 
int dfs(int u){
	st[u] = true;//标记一下，已经被搜过了
	
	int sum = 1, res = 0;//sum存的是以u为根子树的大小，res存的是删掉u点后，每一个连通块大小的最大值 
	for(int i = h[u]; i != -1; i = ne[i]){
		int j = e[i];
		if(!st[j]) {
			int s = dfs(j);//当前这个子树的大小
			res = max(res, s); 
			sum += s; 
		} 
	}
	res = max(res, n - sum);
	
	ans = min(ans, res);
	
	return sum;
}

int main (){
	cin >> n; 
	memset(h, -1, sizeof h);//将所有头结点初始化成-1 
	
	for(int i = 0; i < n - 1; i++){
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);//因为无向边，所以两边都要添加一下 
	}
	
	dfs(1);
	
	cout << ans << endl;
	
	return 0;
} 

树和图的宽度优先遍历

详情点击查看

例题：图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围
1≤n,m≤105

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs(){
	int hh = 0, tt = 0;
	q[0] = 1;//第一个点进入队列 
	
	memset(d, -1, sizeof d);//初始化距离 
	
	d[1] = 0;//第一个点距离为0 
	
	while(hh <= tt){
		int t = q[hh ++];//取出队头 
		for(int i = h[t]; i != -1; i = ne[i]){
			int j = e[i];
			if(d[j] == -1){
				d[j] = d[t] + 1;
				q[++ tt] = j;
			}
		}
	}
	return d[n];
}

int main(){
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	
	for(int i = 0; i < m; i ++){
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	
	cout << bfs() << endl;
	
	return 0;
} 

拓扑排序

详情点击查看

拓扑序列，所有边都是从前指向后的

如果存在环，那么就一定不存在拓扑序。

可以证明，有向无环图一定至少存在一个入度为0的点，一定存在拓扑序列，所以有向无环图又被称为拓扑图。

有向图中，一个点有几条边指向自己就称有几条入度

​ 一个点有几条边指出去就称有几条出度

所以，拓扑图中，所有入度为0的点都可以作为起点，排在当前最前面的位置

拓扑排序第一步：把当前所有入度为0的点入队

第二步，宽搜，取出队头—>t

第三步，枚举t的所有出边t—>j

第四步，删掉t—>j，d[j]—

第五步，如果d[j] == 0,j—>queue

例题：有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围
1≤n,m≤105

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];//d数组存点的入度 

void add(int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort(){
	int hh = 0, tt = -1;//空队列tt = -1,，tt = 0的情况是队列中已经加了一个点 
	
	for(int i = 1; i <= n; i++){
		if(!d[i]){
			q[++tt] = i;//把入度为0的点加入队列 
		}
	}
	while(hh <= tt){
		int t = q[hh ++];
		
		for(int i = h[t]; i != -1; i = ne[i]){
			int j = e[i];
			d[j] --;
			if(d[j] == 0) q[++tt] = j;
		}
	}
	return tt == n - 1;//如果tt==n-1，说明队列中一共进了n个点 ，说明所有点都进入队列了，说明这是一个有向无环图
						//否则存说明在环，不存在拓扑序 
}

int main(){
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		add(a, b);
		d[b]++;//一条a指向b，b的入度+1 
	}
	
	if(topsort()){
		for(int i = 0; i < n; i++) cout << q[i] << " ";
		cout << endl;
	}
	else puts("-1");
	return 0;
}