JZTXT

图论学习笔记

发布时间 2023-08-17 17:03:06作者: JJL0610

图论

图基础

  1. 图的概念：一张图 \(G\) 由若干个点和连接这些点的边构成。称点的集合为 点集 \(V\)，边的集合为 边集 \(E\)，记 \(G=(V,E)\)。

  2. 图的特定名称：

    • 图 \(G\) 的点数 \(|V|\) 称为阶，记作 \(|G|\)。

    • 途径，连接一串节点的边称为序列，如 $ \overrightarrow{puck} $ 就是一条途径。

    • 路径，不经过重复点与重复边的途径称为路径。

    • 回路，有相同头和尾并且不经过重复边的途径称作回路。

    • 环，除了头和尾没有重复边的回路。

    • 重边，端点和方向一样的两条边。

    • 自环，两个端点都是自己的边。

  3. 特殊的图

    • 简单图：不含自环和重边的图。
    • 完全图：完全图的定义是任意两个点之间都有边的无向图，记完全图中点的数量为 \(n\) ，那么 \(n\) 记作那么完全图的边数则为 $C_n^2 = \frac{n!}{2!(n - 2)!} = \frac{n\times (n - 1)}{2} $ 。
    • 有向无环图：不含环的有向图称为有向图无环图，简称 DAG。

  4. 图的分类方法：

    图的分类有多种方法，但是主要的有两种：

    • 无向图和有向图，无向图的定义为 \(e\in E\) 没有方向，那么称为无向图记作 \(e = (a,b)\)；若 \(e \in E\) 有方向，这时候我们就需要使用向量来表示边的方向了记作 $ \overrightarrow{ab} \(， 当然也可以特别的认为\)\text{无向图}\in\text{有向图}$，因为无向边 \(e = (a,b)\) 等价于 $\overrightarrow{ab}, \overleftarrow{ab} $ 。
    • 稠密图与稀疏图，稠密图的定义就是 \(|E|\) 接近于完全图的边数的图，否则就为稀疏图。

  5. 约定

    • 一般记 \(n\) 表示点集的大小 \(|V|\)，\(m\) 表示边集大小 \(|E|\)。

图的储存方法

邻接矩阵：

直接使用数组储存，\(d_{i,j}\) 表示 \(i\) 到 \(j\) 的距离，同时我们

邻接表：

  1. 链式前向星，使用链表记录两点之间距离。

    struct edge{
    int to, next;
}e[M << 1];
int head[N], tot;

void add(int from, int to){
    e[++tot] = edge{to, head[from]};
    head[from] = tot;
}

    2.vector

    vector<edge>s[];
for(i~n){
	int u = read(), v = read(), d = read()...;
	s[].push(edge{...})
}

图上 DFS 与 BFS

邻接矩阵的搜索的时间复杂度为 \(O(n^2)\)，使用邻接表则为 \(O(n + m)\)。

DFS

DFS使用递归实现的，同时有两种重要的操作——搜索和回溯。

bool vis[];
void dfs(现在已经达到的点){
	for(查找这个点链接的边){
        /*
        dis[] = min(dis[] + 1);
        if(vis[])conitnue;
        vis[] = 1;
        */
		dfs(查找的点, 答案累加);	
        /*
        vis[] = 0;
        */
        \\回溯
	}
}

BFS

BFS使用队列实现，满足优先级。

void bfs(){
	//初始化
	dis[i] = 0;
	while(判定队列非空){
		int fq = 队列头;
		for(查找链接的边){
			记录答案，并且放入队列
		}
	}
}

特殊的搜索

双端队列BFS

BFS的本质是队列，而队列含有优先级，有先进先出的顺序，所以BFS也是具有优先级的，同时由于需要找的是最短路径，那么优先级就是越小的越先出队，那么，双端队列BFS是如何进行维护优先级的呢？我们可以将需要改变的 \(x\) 放置队尾，而不需要改变的 \(y\) 放置队头，使得队列头的权值一定是比队尾小的。

P4667 BalticOI 2011 Day1] Switch the Lamp On - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

Casper 正在设计电路。有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。有 \(N\times M\) 个这样的元件，你想将其排列成 \(N\) 行，每行 \(M\) 个。 电源连接到板的左上角。灯连接到板的右下角。只有在电源和灯之间有一条电线连接的情况下，灯才会亮着。为了打开灯，任何数量的电路元件都可以转动 90°（两个方向）。

在上面的图片中，灯是关着的。如果右边的第二列的任何一个电路元件被旋转 90°，电源和灯都会连接，灯被打开。现在请你编写一个程序，求出最小需要多少旋转多少电路元件。

思路

我们发现电路只有两种操作——转和不转，可以使用双端队列 BFS，如果需要改变电路的方向我们就把 \(fx,fy\) 放入队尾，否则放入队尾，思路很好想，代码量还是有点的。

AC Code

#include <iostream>
#include <deque>
#include<cstring>
using namespace std;

inline int read(){
	int f = 1,x = 0;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
inline void print(int x){
	if(x > 9)print(x / 10);
	putchar(x % 10 + '0');
}

const int dx[4]={1, -1, -1, 1};
const int dy[4]={1, 1, -1, -1};
const char dc[4]={'\\', '/', '\\', '/'};
const int ix[4]={0, -1, -1, 0};
const int iy[4]={0, 0, -1, -1};

struct edge{
	int x,y;
};
deque<edge> q;
int dis[501][501];
char map[501][501];
int l, c;

void bfs(){
	memset(dis, 0x3f, sizeof(dis));
	q.push_back(edge{0, 0});	
	dis[0][0] = 0;
	while(!q.empty()){
		edge fq = q.front();q.pop_front();
		for(int i = 0;i < 4;i++){
			int fx = fq.x + dx[i], fy = fq.y + dy[i];
			int jx = fq.x + ix[i], jy = fq.y + iy[i];
			if(fx < 0 || fx > l || fy < 0 || fy > c)continue;
			if(dc[i] != map[jx][jy]){
				int d = dis[fq.x][fq.y] + 1;
				if(d < dis[fx][fy]){
					q.push_back(edge{fx, fy});
					dis[fx][fy] = d;
				}
			}else{
				int d = dis[fq.x][fq.y];
				if(d < dis[fx][fy]){
					q.push_front(edge{fx, fy});
					dis[fx][fy] = d;
				}
			}
 		}
	}
	cout << dis[l][c];
}

signed main(){
	l = read(), c = read();
	for(int i = 0;i < l;i++)
		scanf("%s", map[i]);
	if((l + c) & 1)
		puts("NO SOLUTION");
	else 
		bfs();
	return 0;
}

最短路

floyd

floyd 的主要思想 dp。

我认为与区间dp很像，也很容易理解，主要操作就是枚举中间的断点，状态转移方程就是 \(dp_{i,j} = min(dp_{i,k} + dp_{k,j})\) ，当然值得注意的是枚举 \(k\) 一定要放在最外面，否则容易失分，我可不会说 @ZyC12345 在考试的时候写错丢了 \(70\) 分。

for(int k = 1;k <= n;k++)
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

dijkstra

主要思想贪心，操作如下。

现在有三个点与三条边将三个点都连接起来了这时：

dis1 dis2 dis3
0 5 10

\(1\) 会先找到 \(2\) 然后，对 \(2\) 进行操作，则路径就会变成这样，由于走一条弯路比走两条路远远多走，那么我们还不如直接删除那条长的路，留下短的路。

dis1 dis2 dis3
0 5 8

image-20230817161924847

代码实现：

暴力

for(int i = 1;i <= n;i++){
	u = -1; minn = INT_MAX;
	for(int v = 1;v <= n;v++)
		if(!vis[v] && dis[v] < minn)
			minn = dis[v], u = v;
	if(u == -1)break;
	else vis[u] = 1;
	for(auto i : a[u]){
		dis[i.to] = min(dis[i.to], dis[u] + i.v);
	}
}

堆优化

void dijkstra(){
	for(int i = 1;i <= n;i++)
		dis[i] = 0x7fffffff;
	dis[s] = 0;
	q.push(edge{0, s});
	while(!q.empty()){
		int now = q.top().e;q.pop();
		if(vis[now])continue;
        vis[now] = 1;
        for(int i = head[now];i;i = e[i].next){
        	int to = e[i].to, d = e[i].dis;
        	if(dis[to] > dis[now] + d){
        		dis[to] = dis[now] + d;
        		q.push(edge{dis[to], to});
			}
		}
	}
}