图论学习笔记

图

图论绘图在线

图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系!点一般用字母v表示，如v1，v2，v3，v4

一些简单的术语：

• 路径：一些边组成的序列，满足第一条边的终点为第二条边的起点，第二条边的终点为第三条边的起点...如果边有权值，则我们把这些边权的和作为路径的长度；如果没有权值，则我们把边的条数作为路径的长度，即可以看作每条边的权值为1
• 点/边的权值：点/边的属性，题目可能会用到。
• 重边：起点与终点都相同的边被称为重边
• 自环：点到自己有一条边
• 简单路径：如果路径中没有经过重复点，则我们称这条路径为简单路径
• 环：起点和终点相同的简单路径
• 子图：在原图的边和点中选择一些保留下来，其他删除，就是子图
• 连通性相关：两个点之间有路径，则称两点之间互相联通

存图

有以下边：

0 2
0 4
0 5
1 4
1 5
2 3
2 4
4 5

1.邻接矩阵

存储方式如下表：

每一条边（记为\((x,y)\)）都将\(a[x][y]\)存为\((x,y)\)的长度（无向图也要把边\((y,x)\)存入）
但可以看到有很多-，也就是浪费了很多空间（开了\(n^2\)的空间却只用了m,一般\(m\le 2*n\)）
所以可以优化

2.邻接表

0 2
0 4
0 5
1 4
1 5
2 3
2 4
4 5

存储方式如下表：

后面还是有很多空，但可以动态分配空间(vector或链表实现)

vector实现

struct node{
	int to,len;
}//结构体
/////////////////////////////加边/////////////////////////////
void add(int x,int y,int s){
	v[x].push_back(node{y,i});
	//v[y].push_back(node{x,i});当为无向图时要反向加边
}
/////////////////////////////遍历/////////////////////////////
//单点
for(int i=0;i<v[x].size();i++)/*边为v[x][i]*/;
//dfs序
void dfs(int a,int s){
	if(b[a])return;
	b[a]=1;
	cout<<a<<" ";
	for(int i=0;i<v[a].size();i++){
		if(!b[v[a][i]])dfs(v[a][i],s+1);	
	}
}
//bfs序
void bfs(){
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int u=q.front();	
		q.pop();
		if(b2[u])continue;
		cout<<u<<" ";
		b2[u]=1;
		for(int i=0;i<v[u].size();i++)q.push(v[u][i]);
	}
}

链表实现

int e[N],cnt,h[N];
struct node{
	int to,len,next;
}//结构体
/////////////////////////////加边/////////////////////////////
void add(int x,int y,int s){
    e[++cnt].to=y;
    e[cnt].len=w;
    e[cnt].next=h[x];
    h[x]=cnt;
}
/////////////////////////////遍历/////////////////////////////
//单点
for(int i=h[x];i;i=e[i].next)/*用e[i]*/;
//dfs/bfs序遍历代码同

例题

P5318 【深基18.例3】查找文献

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>v[550000];
int n,m,l,r,T,b[550010]={0},b2[550010]={0};
void dfs(int a,int s){
	if(b[a])return;
	b[a]=1;
	cout<<a<<" ";
	for(int i=0;i<v[a].size();i++){
		if(!b[v[a][i]]){
			dfs(v[a][i],s+1);	
		}
	}
}
void bfs(){
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int u=q.front();	
		q.pop();
		if(b2[u])continue;
		cout<<u<<" ";
		b2[u]=1;
		for(int i=0;i<v[u].size();i++){
			q.push(v[u][i]);	
		} 
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		v[l].push_back(r);
	}
	for(int i=1;i<=n;i++){
		sort(v[i].begin(),v[i].end());
	}
	dfs(1,0);
	cout<<endl;
	bfs();
	return 0;
}

B3643 图的存储
B3613 图的存储与出边的排序
P3916 图的遍历

最短路

SPFA

它死了

int spfa(int x){
	memset(b,0,sizeof(b));
	for(int i=0;i<=n;i++)dis[i]=1e18;
	queue<int>q;
	q.push(1);
	b[1]=1;
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		b[u]=0;
		for(int i=0;i<v[u].size();i++){
			int a=v[u][i].to,s=v[u][i].len;
			if(dis[u]+s<dis[a]){
				dis[a]=dis[u]+s;
				if(!b[a]){
					b[a]=1;
					q.push(a); 
				}
			}
		}	
	}
	return dis[n];
}

Dijkstra(堆优化)

struct dj{
	int dis,bb;
	bool operator < (const dj &a) const{
		return a.dis<dis;
	}
};
void dijkstra(){
	priority_queue<dj>q;
	for(int i=1;i<=n;i++)dis[i]=1e18;
	dis[1]=0;
	q.push((dj){0,1});
	while(!q.empty()){
		dj now=q.top();
		q.pop();
		if(vis[now.bb])continue;
		vis[now.bb]=true;
		for(int i=0;i<v[now.bb].size();i++){
			if(dis[v[now.bb][i].to]>dis[now.bb]+v[now.bb][i].len){
				dis[v[now.bb][i].to]=dis[now.bb]+v[now.bb][i].len;
				q.push((dj){dis[v[now.bb][i].to],v[now.bb][i].to});
			}
		}
	}
}