1360 - 算法7-4,7-5：图的遍历—

1360 - 算法7-4,7-5：图的遍历——深度优先搜索

通过次数

提交次数

旧版界面

时间限制 : 1 秒内存限制 : 32 MB

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

其算法可以描述如下：

<span style="font-family:宋体;">在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。</span>

<span></span>

题目输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

题目输出

只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

输入/输出样例

输入格式

输出格式

0 1 3 2

C语言解答

#include <stdio.h>
#include <string.h>
int isvisited[51],mat[51][51],cnt,n;
void dfs(int start){
	if (cnt>=n)
	{
		return ;
	}
	cnt++;
	isvisited[start]=1;
	printf("%d ",start);
	for (int i=0;i<n;i++)
	{
		if (!isvisited[i]&&mat[start][i]==1)
		{
			dfs(i);
		}
	}
}
int main(){
	int i,j;
//	freopen("1.txt","r",stdin);
	while (scanf("%d",&n)==1)
	{
		for (i=0;i<n;i++)
		{
			for (j=0;j<n;j++)
			{
				scanf("%d",&mat[i][j]);
			}
		}
		cnt=0;
		memset(isvisited,0,sizeof(isvisited));
		for (i=0;i<n;i++)
		{
			if (!isvisited[i])
			{
				dfs(i);
			}
		}
		printf("\n");
	}
//	fclose(stdin);
	return 0;
}

C++解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status; /* 函数结果状态代码,如OK等 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 50 /* 最大顶点个数 */
typedef int VRType;
typedef char InfoType;
typedef int VertexType;
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct {
	VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
	/* 对带权图，c则为权值类型 */
	InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
	AdjMatrix arcs; /* 邻接矩阵 */
	int vexnum,arcnum; /* 图的当前顶点数和弧数 */
	GraphKind kind; /* 图的种类标志 */
}MGraph;

Status CreateUDG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
	int i,j;
	scanf("%d",&(*G).vexnum);
	for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
		(*G).vexs[i] = i;
	for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
		for(j=0;j<(*G).vexnum;++j)
		{
			scanf("%d",&(*G).arcs[i][j].adj); /* 图 */
			(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
		}
	(*G).kind=AG;
	return OK;
}

int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
	/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
	int i;
	for(i=0;i<G.vexnum;++i)
		if(u == G.vexs[i])
			return i;
	return -1;
}

VertexType* GetVex(MGraph G,int v)
{ /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
	if(v>=G.vexnum||v<0)
		exit(ERROR);
	return &G.vexs[v];
}

int FirstAdjVex(MGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
	/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
	int i,j=0,k;
	k=LocateVex(G,v); /* k为顶点v在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=0;i<G.vexnum;i++)
	if(G.arcs[k][i].adj!=j)
	return i;
	return -1;
}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
	/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
	/*           若w是v的最后一个邻接顶点,则返回-1 */
	int i,j=0,k1,k2;
	k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */
	k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=k2+1;i<G.vexnum;i++)
	if(G.arcs[k1][i].adj!=j)
	return i;
	return -1;
}

bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType); /* 函数变量 */
void DFS(MGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
	VertexType w1,v1;
	int w;
	visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
	VisitFunc(G.vexs[v]); /* 访问第v个顶点 */
	v1 = *GetVex(G,v);
	for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w1 = *GetVex(G,w)))
	if(!visited[w]) DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */
}

void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */
	/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
	/*           一次且仅一次。一旦Visit()失败,则操作失败 */
	int v;
	VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
	for(v=0;v<G.vexnum;v++)
		visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v); /* 对尚未访问的顶点调用DFS */
	printf("\n");
}

Status visit(VertexType i)
{
	printf("%d ",i);
	return OK;
}

int main() {
	int i,j,k,n;
	MGraph g;
	CreateUDG(&g);
	DFSTraverse(g,visit);
	return 0;
}

Java解答



import java.util.Scanner;

public class Main {
   private static Scanner s = new Scanner(System.in) ;
   
   public static void main(String[] args) {
	   int n = s.nextInt() ;
	   int a[][] = new int[n][n] ;
	   boolean visited[] = new boolean[n] ;
	   for (int i = 0; i < a.length; i++) {
		 for (int j = 0; j < a.length; j++) {
			a[i][j] = s.nextInt() ;
		 }
	    }
	   for (int i = 0; i < visited.length; i++) {
		  a[i][i] = 1 ;
	   }
	   
	   Graph g = init(a ,visited) ;
	   deptSearch(g, 0) ;
	   System.out.println() ;
   } 
   
   public static Graph init(int a[][] , boolean visited[]){
	   Graph g = new Graph(a.length) ;
	   g.visited = visited ;
	   g.a = a ;
	   return g ;
   }
   public static void deptSearch(Graph g,int x){
	   for (int i = 0; i < g.n; i++) {
		   if(g.a[x][i] ==1&&g.visited[i]==false){
			   g.visited[i] = true ;
			   visit(i) ;
			   deptSearch(g, i) ;
		   }
	   }
   }
   public static void visit(int i){
	   System.out.print(i+" ");
   }
}

class Graph{
	int n  ;
	int a[][] = new int [n][n] ;
	boolean visited[] = new boolean[n] ;
	public Graph(int n) {
       this.n = n ;
	}
}

上一题下一题提示代码讨论统计