图论学习笔记-JZTXT

图

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

一些简单的术语：

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

存图

有以下边：

1.邻接矩阵

存储方式如下表：

\	v0	v1	v2	v3	v4	v5
v0	-	-	1	-	1	1
v1	-	-	-	-	1	1
v2	1	-	-	1	1	-
v3	-	-	1	-	-	-
v4	1	1	1	-	-	1
v5	1	1	-	-	1	-

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

2.邻接表

存储方式如下表：

\	1	2	3	4	5	6
v0	2	4	5	-	-	-
v1	4	5	-	-	-	-
v2	0	3	4	-	-	-
v3	2	-	-	-	-	-
v4	0	1	2	5	-	-
v5	0	1	4	-	-	-

后面还是有很多空，但可以动态分配空间(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序遍历代码同