一、图的存储

1.邻接矩阵

二维数组G[i][j]，若是无向图，则G[i][j]=1表示i和j点之间存在边；若不存在的边可以设边权为0、-1或是一个很大的数。
缺点：邻接矩阵只适用于顶点数不大（不超过1000）。

2.邻接表

顶点数较大（1000以上）的图就用邻接表存储。
Adj[i]存放顶点i的所有【出边】组成的列表。
（1）若邻接表只存放每条边的终点编号（不存放边权），则vector中的元素类型可以直接定义为int型：vector<int> Adj[N]。
（2）如果要添加从1号结点到3号结点的有向边（边权=4），则可以定义一个Node型的临时变量temp：

struct Node{
	int v;//边的终点编号
	int w;//边权
};
vector<Node>Adj[N];
Node temp;
temp.v=3;
temp.w=4;
Adj[1].push_back(temp);

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

若不想定义临时变量实现加边操作，可以定义结构体Node的构造函数如下：
（复习构造函数）

struct Node{
	int v,w;
	Node(int _v,int _w):v(_v),w(_w){}//构造函数
}
Adj[1].push_back(Node(3,4));

  

 

  
1
  
2
  
3
  
4
  
5
 

二、图的DFS

如果给定的图是一个连通图，则只需要一次DFS就能完成遍历。
伪代码如下：

DFS(u){//访问顶点u
	vis[u]=true;//设置u已被访问
	for(从u出发能到达的所有顶点v)//枚举从u出发可以到达的所有顶点v
		if vis[v]==false//如果v未被访问
			DFS(v) //递归访问v
	}
DFSTrave(G){//遍历图
	for(G的所有顶点u)//对G的所有顶点u
		if vis[u]==false//如果u未被访问
			DFS(u) //访问u所在的连通块
}	

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

定义MAXV为最大顶点数，INF为一个很大的数字。

const int MAXV=1000;//最大顶点数
const int INF=1000000000;//设INF为一个很大的数

  

 

  
1
  
2
 

（1）邻接矩阵版

int n,G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
bool vis[MAXV]={false};//如果顶点i已被访问，则vis[i]==true，初值为false

void DFS(int u,int depth){//u为当前访问的顶点标号，depth为深度
	vis[u]=true;
	//如果需要对u进行一些操作，可以在这里进行
	//下面对所有从u出能到达的分支顶点进行枚举
	for(int v=0;v<n;v++){//对每个顶点v
		if(vis[v]==false && G[u][v]!=INF){//如果v未被访问，且u可到达v
			DFS(v,depth+1);
			}
		}
	}
}
void DFSTrave(){//遍历图G
	for(int u=0;u<n;u++){//对每个顶点u
		if(vis[u]==false){//如果u未被访问
			DFS(u,1);//访问u和u所在的连通块，1表示初始为第一层
		}
	}
}	

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

（2）邻接表版

vector<int>Adj[MAXV];//图G的邻接表
int n;//n为顶点数，MAXV为最大顶点数
bool vis[MAXV]={false};//访问数组

void DFS(int u,int depth){//u为当前访问的顶点标号，depth为深度
	vis[u]=true;
	//如果需要对u进行一些操作，可在此处进行
	for(int i=0;i<Adj[u].size();i++){//对从u出发可以到达的所有顶点v
		int v=Adj[u][i];
		if(vis[v]==false){
			DFS(v,depth+1);
		}
	}
}
void DFSTrave(){//遍历图
	for(int u=0;u<n;u++){
		if(vis[u]==false)
			DFS(u,1);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

1.小栗子：通过DFS计算图的连通分量个数

原题是【1013】Battle Over Cities (求连通分量数)
而DFS还是模板（只不过这题需要在递归过程中遇到要被删除的结点时直接return——而非真的删除该结点），不用加上DFSTrave函数；本题巧妙在要求删除点后增加多少条边后才能连接为连通图，这个边数=连通分量个数-1。而求连通分量个数直接在main函数内：

	for(int i=0;i<qnum;i++){
		scanf("%d",&deletepoint);//删除某结点  
		//
		memset(vis,false,sizeof(vis));
		//vis[deletepoint]=true;
		int block=0;//连通块个数，初值为0
		for(int i=1;i<=vnum;i++){//枚举每个顶点
			if(i!=deletepoint&&vis[i]==false){
				DFS(i);//遍历顶点i所在的连通块
				block++;//连通块个数加1
			}
		}
		printf("%d\n",block-1);//所需增加的边
		//
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

3.图的BFS

过程：把初始顶点加入队列，每次都取出队首点进行访问，并把从该顶点出发可以到达的未曾加入过队列（而不是未访问）的顶点全部加入队列，直到队列为空。
伪代码如下

BFS(u){//遍历u所在的连通块
	queue q;
	将u入队;
	inq[u]=true;//设置u已被加入过队列
	while(q非空){//只要队列非空
		取出q的队首元素u进行访问;
		for(q非空){//只要队列非空
			if(inq[v]==false){//如果v未曾加入过队列
				将v入队;
				inq[v]=true;//设置v已被加入过 队列
			}
		}
	}
}
BFSTrave(G){
	for(G的所有顶点u) //枚举G的所有顶点u
		if(inq[u]==false)//如果u未曾加入过队列
			BFS(u);//遍历u所在的连通块

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

（1）邻接矩阵

int n,G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
bool inq[MAXV]={false};//若顶点i曾入过队列，则inq[i]==true,初值为falsef

void BFS(int u){//遍历u所在的连通块
	queue<int>q;
	q.push(u);
	inq[u]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int v=0;v<n;v++){
			//如果u的邻接点v未曾加入过队列
			if(inq[v]==false&&G[u][v]!=INF){
				q.push(v);
				inq[v]=frue;
			}
		}
	}
}	
void BFSTrave(){
	for(int u=0;u<n;u++){
		if(inq[u]==false)
			BFS(q);

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

（2）邻接表版

vector<int> Adj[MAXV];//图G，Adj[u]存放从顶点u出发可以到达的顶点
int n;//n为顶点数，MAXV为最大顶点数
bool inq[MAXV]={false};

void BFS(int u){
	queue<int>q;
	q.push(u);
	inq[u]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<Adj[u].size();i++){
			int v=Adj[u][i];
			if(inq[v]==false){
				q.push(v);
				inq[v]=true;
			}
		}
	}	
}
void BFSTrave(){
	for(int u=0;u<n;u++)
		if(inq[u]==false)
			BFS(q);

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

（3）输出层号

若要输出所有顶点的层号，则需要定义结构体Node，并在其中存放顶点的编号和层号。
这时的vector邻接表中的元素就不再是int，而是Node。

struct Node{
	int v;
	int layer;
	Node(int a,int b):v(a),layer(b){}
}start;
vector<Node> Adj[N];
void BFS(int s){//s为起始顶点编号
	queue<Node>q;
	start=Node(s,0);//起始顶点——构造函数的写法
	q.push(start);
	inq[start.v]=true;//起始顶点的标号设为已被加入过队列
	while(!q.empty()){
		Node topNode=q.front();
		q.pop();
		int u=topNode.v;//队首顶点的编号
		for(int i=0;i<Adj[u].size();i++){
			Node next=Adj[u][i];//从u出发能到达的顶点next
			next.layer=topNode.layer+1;//next层号等于当前顶点层号加1
			//如果next的编号未被加入过队列
			if(inq[next.v]==false){
				q.push(next);
				inq[next.v]=true;
			}
		}
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

PS：构造函数复习（https://andyguo.blog.csdn.net/article/details/112801861）

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/112800014