图论初步

图的基本概念

1.图由节点和边的集合组成的二元组。

2.节点若一个图的节点数为n。

3.边，用(u,v)表示，u和v关联。一个图的边数最多为n(n-1)/2，n为点的数量。因为n个点可以连接n-1个点，而两个点才能连成一条边，所以要/2。

4.节点的度数，既与节点有关的边数，每个节点的度数不可能超过n-1。

5.路径图的一条路径是一个节点序列，如果节点和边都不重复出现，则称为简单路径反之称为环、圈或回路。

图的一些基本分类

a.连通图和非连通图 一个图中任意两点都有路径连接称为连通图，反之称为非连通图。

b.无向图和有向图 边都是单向的图叫有向图，反之叫无向图。有向图的一条边(u,v)的顶点u可以通向v，v却不可以通向u。

c.无权图和加权图 图中的节点是否带权，则称为无权图和加权图，通常在节点和边上加权，表示路费，距离等。 待更新。。。

d.完全图 边数达到n(n-1)/2的图。

e.树 既没有环的连通图。

图的存储和遍历

a.用矩阵（二维数组）存储遍历

1.建图

以下图这个无向图为例：

二维数组：

g	1	2	3	4
1	false		true	true
2	false		true	false
3	true	true	false
4	true	false	false

g[u][v]表示节点u,v间有没有边。

2.遍历 从u点出发，每经过一个节点用flag[u]标记，枚举其他的点v，如果边(u,v)存在，且v没被走过，就可以去下一个点，所有的点都走过之后就退出循环。

3.代码模板

#include<iostream>
using namespace std;
const int N=1000;
int n,k,m;
bool g[N][N],flag[N];
void dfs(int u){
	flag[u]=true;
	cout<<u<<" ";
	for(int i=1;i<=n;i++){
		if(g[u][i]&&!flag[i]){
			dfs(i);
		}
	}
}
int main(){
	cin>>n>>k>>m;
	for(int i=1;i<=k;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]=true;
		g[v][u]=true;//如果是有向图，那么这行可以删掉
	}
	for(int i=1;i<=n;i++)if(!flag)dfs(i);
}

虽然这种方法删边增边容易，但是太浪费空间。

b.用链表储存

1.建图 这种方法常用vector来实现。

节点编号	可以连	接的点
1	4	3
2	3
3	2	1
4	1

g[u][i]表示u的第i个可以连接的点的编号。

2.遍历 枚举每个点，从这个点开始向四周遍历，如果有边且这个点没被遍历过，那么进行下一轮遍历。

3.代码模板

#include<iostream>
#include<vector>
using namespace std;
const int N=1000;
int n,k,u,v;
bool flag[N];
vector<int> g[N];
void dfs(int u){
	cout<<u<<" ";
	flag[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!flag[v])dfs(v);
	} 
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!flag)dfs(i);
}

虽然这种是常用的建图遍历方法，有效地解决了第一种方法的空间问题，但是增边删边困难。

c.前向星静态链表储存

前向星建图遍历模板

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=100000+10;
int n,k,u,v,tot,head[N],sum;
bool flag[N],f;
struct node{
	int v,next;
}g[400001];
void add_edge(int u,int v){
	g[++tot].v=v;
	g[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u){
	cout<<u<<" "; 
	flag[u]=true; 
	for(int i=head[u];i!=-1;i=g[i].next){
		int v=g[i].v;
		if(!flag[v])dfs(v);
	}
}
signed main(){
	memset(head,-1,sizeof(head));
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!flag[i])dfs(i);
	}
}

判环问题

1.无向图判环

/*
无向图判环代码，以前向星写法为例。
我们把已走过的点进行标记，如果回到此次遍历的父节点，则跳过，
避免死循环，如果去到没有走过的点，就进行下一轮的遍历。如果
来到已走过的点，那么就证明有环。 
*/ 
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=100000+10;
int n,k,u,v,tot,head[N],sum;
bool flag[N],f;
struct node{
	int v,next;
}g[400001];
void add_edge(int u,int v){
	g[++tot].v=v;
	g[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u,int fa){//从u点开始，fa表示u的父节点 
	flag[u]=true;//标记已走过的点 
	for(int i=head[u];i!=-1;i=g[i].next){
		int v=g[i].v;
		if(v==fa)continue;//回到父节点 
		if(!flag[v])dfs(v,u);//没走过 
		else f=true;//回到走过的点 
	}
}
signed main(){
	memset(head,-1,sizeof(head));
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	for(int i=1;i<=n;i++){
		dfs(i,-1);
	}
	if(f==false)cout<<"have no circle";
	else cout<<"have circle";
}

2.有向图判环

有向图的判环问题相对较复杂，如果按照无向图判环的思路，会出现很多无中生有的环。如下：

如果按照无向图判环的思路，首先会遍历到1，接着2、3、4，节点4已经没有可以走出去的路了，那么就会回到3，再到2，此时，2还有一条路通向4，由于4已经被标记过了所以程序会认为这是一个环，但实际上并没有。

问题出在哪呢？访问到已经结束访问的点，并不证明存在环。只有真正访问到正在访问的点，才能证明环的存在。

有向图判环模板

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=100000+10;
int n,k,u,v,flag[N],tot,head[N],sum;
bool f;
struct node{
	int v,next;
}g[400001];
void add_edge(int u,int v){
	g[++tot].v=v;
	g[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u){
	flag[u]=1; 
	for(int i=head[u];i!=-1;i=g[i].next){
		int v=g[i].v;
		if(flag[v]==0)dfs(v);
		if(flag[v]==1)f=true;
	}
	flag[v]=-1;
}
signed main(){
	memset(head,-1,sizeof(head));
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		add_edge(u,v);
	}
	for(int i=1;i<=n;i++){
		dfs(i);
	}
	if(f)cout<<"have circle";
	else cout<<"have no circle";
}
 */

例题

A. 图的m着色问题

#include<iostream>
#include<vector>
using namespace std;
const int N=100+1;
int n,k,m,sum,c[N];
bool g[N][N];
bool check(int u,int color){
	for(int i=1;i<=n;i++)if(g[u][i]&&c[i]==color)return false;
	return true;
}
void dfs(int u){
	if(u>n){
		sum++;
		return;
	}
	for(int i=1;i<=m;i++){
		if(check(u,i)){
			c[u]=i;
			dfs(u+1);
			c[u]=0;
		}
	}
}
int main(){
	cin>>n>>k>>m;
	for(int i=1;i<=k;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]=g[v][u]=true;
	}
	dfs(1);
	cout<<sum;
}

B. 羊和狼

#include<iostream>
using namespace std;
int n,m,so,sv,soo,svv;
int xx[4]={-1,0,1,0};
int yy[4]={0,-1,0,1};
char z[255][255];
void dfs1(int x,int y){
    z[x][y]='#';
    for(int i=0;i<4;i++){
        int nx=x+xx[i];
        int ny=y+yy[i];
        if(nx>=0&&ny>=0&&nx<=n+1&&ny<=m+1&&z[nx][ny]!='#')dfs1(nx,ny);
    }
}
void dfs2(int x,int y){
    if(z[x][y]=='o')so++;
    if(z[x][y]=='v')sv++;
    z[x][y]='#';
    for(int i=0;i<4;i++){
        int nx=x+xx[i];
        int ny=y+yy[i];
        if(z[nx][ny]!='#')dfs2(nx,ny);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>z[i][j];
        }
    }
    dfs1(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            so=sv=0;
            if(z[i][j]!='#'){
                dfs2(i,j);
                if(so>sv)soo+=so;
                else svv+=sv;
            }
            z[i][j]='#';
        }
    }
    cout<<soo<<" "<<svv;
}

C. Cow Picnic

思路：

枚举牛们所在的农场，把那里当作起点，开始遍历每经过一个农场，这个农场的计数器加一，知道走不下去为止，最后如果这个农场经过了K头牛，那么这个地方就适合做野餐地点。

代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1000+1;
int n,k,m,u,v,a[101],farm[1001],sum;
bool flag[N];
vector<int> g[N];
void dfs(int u){
	farm[u]++;
	flag[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!flag[v]){
			dfs(v);
		}
	} 
}
int main(){
	cin>>m>>n>>k;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=m;i++){
		memset(flag,false,sizeof(flag));
		dfs(a[i]);
	}
	for(int i=1;i<=n;i++){
		if(farm[i]==m)sum++;
	}
	cout<<sum;
}

D. 树

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=100000+10;
int n,k,u,v,tot,head[N],sum;
bool flag[N],f;
struct node{
	int v,next;
}g[400001];
void add_edge(int u,int v){
	g[++tot].v=v;
	g[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u,int fa){
	flag[u]=true; 
	for(int i=head[u];i!=-1;i=g[i].next){
		int v=g[i].v;
		if(v==fa)continue;
		if(!flag[v])dfs(v,u);
		else f=true;
	}
}
signed main(){
	memset(head,-1,sizeof(head));
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!flag[i]){
			f=false;
			dfs(i,-1);	
			if(!f)sum++;
		}
	}
	cout<<sum;
}

E. 传话

思路

模板题，枚举n个节点，求以i为起点，i为终点的环是否存在。

代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=1001;
int n,k,u,v,flag[N];
vector<int> g[N];
bool dfs(int u,int last){
	flag[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(flag[v]==0&&dfs(v,last))return true;
		if(flag[v]==1&&v==last)return true;                  
	} 
	flag[u]=-1;
	return false;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		memset(flag,0,sizeof(flag));
		if(dfs(i,i))cout<<"T\n";
		else cout<<"F\n";
	}
	return 0;
}

F. 寻找道路

思路：

第一步，建一个反图，从终点开始，向四周遍历，遍历到的每一个点把它标记起来；第二步，从起点开始，遍历四周的点，如果它没被遍历过且被标记过，那么就进行下一层的遍历。这个过程用广搜最好。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=1e4+1;
int n,k,s,t;
vector<int> g[N];//原图 
vector<int> f[N];//反向图 
bool flag[N],vis[N];
struct node{int x,s;};
void bfs_t(){
	queue<int> q;
	flag[t]=true;
	q.push(t);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<f[u].size();i++){
			int v=f[u][i];
			if(!flag[v]){
				q.push(v);
				flag[v]=true;
			}
		}
	}
	return;
}
bool check_t(int u){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!flag[v])return false;
	}
	return true;
}
void bfs_s(){
	queue<node> q;
	q.push((node){s,0});
	vis[s]=true;
	while(!q.empty()){
		node f=q.front();
		q.pop();
		for(int i=0;i<g[f.x].size();i++){
			int v=g[f.x][i];
			if(v==t){
				cout<<f.s+1;
				exit(0);
			}
			if(!vis[v]&&check_t(v)&&flag[v]){
				vis[v]=true;
				q.push((node){v,f.s+1});
			}
		}
	}
	cout<<"-1";
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v); //原图 
		f[v].push_back(u); //反向图 
	}
	cin>>s>>t;
	bfs_t();
	bfs_s();
	return 0;
}

总结：

这道题考的是思维能力，代码细节较多，建议多看几次题目。

图论初步

图论初步

图的基本概念

图的一些基本分类

图的存储和遍历

a.用矩阵（二维数组）存储遍历

b.用链表储存

c.前向星静态链表储存

判环问题

1.无向图判环

2.有向图判环

例题

思路：

代码：

思路

代码

F. 寻找道路

思路：

代码：

总结：

状态

开发

支持

图论初步

图论初步

图的基本概念

图的一些基本分类

图的存储和遍历

a.用矩阵（二维数组）存储遍历

b.用链表储存

c.前向星静态链表储存

判环问题

1.无向图判环

2.有向图判环

例题

思路：

代码：

思路

代码

F. 寻找道路

思路：

代码：

总结：

状态

开发

支持

登录