本文主要是介绍图的深度优先搜索(邻接矩阵)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
给出图的顶点数和顶点与顶点之间的连接关系，请输出用邻接矩阵存储的图的深度优先搜索顶点序列。
Input
输入的第一行是一个整数T表示测试示例的数目，每组示例的第一行有两个数m(2<=m<=10)和n(1<=n<=m*(m-1)/2)，m表示顶点的个数(顶点的标号从1-m)，n表示边的个数。下面n行的每行表示一条边。后面一行是一个数k，k表示需要搜索的顶点数量。后面k行每行有一个数表示从该顶点开始搜索。在搜索过程中与同一个顶点相邻的顶点按顶点标号从小到大进行搜索。
Output
每组输出k行，每行为从输入的一个顶点开始搜索的深度优先搜索序列。每组搜素结果之间用空行隔开。
Sample Input
1 2 1 1 2 2 1 2
Sample Output
1 2 2 1
//标程： #include<stdio.h> #include<string.h> int n,m,map[15][15],vis[15],cnt; void dfs(int x) {cnt++; if(cnt<m) printf("%d ",x); if(cnt==m) printf("%d\n",x); for(int i=1;i<=m;i++) { if(map[x][i] && !vis[i]) { vis[i]=1; dfs(i); vis[i]=0; } } } int main() { //freopen("a.txt","r",stdin);int t,i,k,a,b,x; scanf("%d",&t);while(t--) { scanf("%d%d",&m,&n); memset(map,0,sizeof(map)); for(i=1;i<=n;i++) { scanf("%d%d",&a,&b); map[a][b]=map[b][a]=1; } scanf("%d",&k); for(i=1;i<=k;i++) { scanf("%d",&x); memset(vis,0,sizeof(vis)); cnt=0; vis[x]=1; dfs(x); } if(t!=0) printf("\n"); } return 0; }
这篇关于图的深度优先搜索(邻接矩阵)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
