挑战程序设计竞赛 第十二章 图

本文主要是介绍挑战程序设计竞赛 第十二章 图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

图的搜索 ：

DFS(深度优先搜索)
BFS(广度优先搜索）
这两种算法对有向图无向图都适用
BFS常用作求最短路径的算法

图的表示

分为邻接表，邻接矩阵两种方法

DFS(12.3)

用递归实现深度优先搜索

#include<iostream>

using namespace std;

const int N = 100;

int m[N][N];
int color[N] , d[N],f[N],tt=0;
int n;

void dfs_v(int u){
	int v;
	color[u] = 1;		//标记为正在走此点
	d[u] = ++tt;
	for(v=1;v<=n;v++){
		if(m[u][v] == 0)	continue;
		if(color[v] == 0){		//如果v点没有走过，进行递归遍历
			dfs_v(v);
		}
	}
	color[u] = 2;				// 2代表此点已经走完
	f[u] = ++tt;

}
void dfs()
{
	int i,u;
	for(i=1;i<=n;i++)	color[i] = 0; //全部初始化为没走过
	for(i=1;i<=n;i++){
		if(color[i] == 0){				//依次进行dfs
			dfs_v(i);			
		}
	}
	for(i=1;i<=n;i++){
		cout << i <<" "<< d[i] <<" " <<f[i] <<endl;
	}

}
int main()
{
	int u,v,k,i,j;
	cin >> n;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)	
			m[i][j] = 0;	//全部初始化为0
	}

	for(i=0;i<n;i++){
		cin >> u >>k;
		for(j=0;j<k;j++){
			cin >> v;
			m[u][v] = 1;			//初始化为1
		}
	}

	dfs();
	return 0;
	
}

这篇关于挑战程序设计竞赛 第十二章 图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！