SHAOXIAOJ-1687:图-无向连通图的深度优先遍历

金币值：2 定数：10 时间限制：1.000 s 内存限制：128 M

正确：7 提交：28 正确率：25.00% 命题人：

点赞量：0 收藏量：0 题目类型：程序知识点：数据结构-图

建立一个无向连通图的邻接表（邻接表的建立方式约定采用头插法，边的输入顺序按照顶点的编号由小到大输入，顶点中存储的信息为顶点编号，顶点从1开始编号），然后给出该图的深度优先搜索序列（从编号为1的顶点开始深度优先搜索）。

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX 30

int visited[MAXVEX]; // 定义一个全局数组，表示图中的顶点是否已经访问过，0表示没有访问，1表示已经访问，0号单元不用

typedef char VertexType; // 顶点类型应由用户定义
typedef int EdgeType; // 边上的权值类型应由用户定义

typedef struct EdgeNode { // 边表结点
	int adjvex;    // 邻接点域,存储该顶点对应的下标
	EdgeType info;  // 用于存储权值,对于非加权图可以不需要
	struct EdgeNode *next; // 链域,指向下一个邻接点
} EdgeNode;

typedef struct VertexNode { // 顶点表结点
	VertexType data;  // 顶点域,存储顶点信息
	EdgeNode *firstEdge; // 边表头指针
} VertexNode;

typedef struct Graph {
	int numNodes, numEdges;
	VertexNode AdjList[MAXVEX]; //0号单元不用
} ALGraph;
void DFS(ALGraph G, int v);
void CreateGraph(ALGraph &G) {
   /*该函数平台已提供*/
}

int main(void) {
	ALGraph G ;
	scanf("%d %d", &G.numNodes, &G.numEdges);
	CreateGraph(G); //假设图中顶点从1开始编号，建立图的连接表
	DFS(G,1); //从编号为1的顶点开始深度优先搜索图
	return 0;
}
/*仅提交以下代码*/ 
void DFS(ALGraph G, int v) {

}

第1行输入两个整数，分别表示图中的顶点数n和边数m
第2-m+1行每行输入两个整数i和j，分别表示编号为i的顶点和编号为j的顶点之间有一条边（顶点编号从1开始，按照顶点编号从小到大的顺序输入边）

输出1行信息共有n个整数，分别表示深度优先搜索图经过的顶点编号序列，每两个整数之间有一个空格。

1 3 7 6 2 5 8 4

注意:按照指定的要求输入边的信息

平台已提供的代码:(可以学习下)

void CreateGraph(ALGraph &G) {  
	int i, j;  
	EdgeNode *e;  
	
	// 初始化邻接表  
	for (i = 1; i <= G.numNodes; i++) {  
		G.AdjList[i].firstEdge = NULL;  
	}  
	
	// 读取边信息并构建邻接表  
	for (i = 0; i < G.numEdges; i++) {  
		int v1, v2; // 假设边的信息是通过顶点对给出的  
		scanf("%d %d", &v1, &v2); // 读取一条边的两个顶点  
		
		// 为v1->v2添加一条边  
		e = (EdgeNode *)malloc(sizeof(EdgeNode));  
		e->adjvex = v2;  
		e->next = G.AdjList[v1].firstEdge;  
		G.AdjList[v1].firstEdge = e;  
		
		// 如果图是无向图，还需要为v2->v1添加一条边  
		// 如果是有向图，则不需要下面的代码  
		e = (EdgeNode *)malloc(sizeof(EdgeNode));  
		e->adjvex = v1;  
		e->next = G.AdjList[v2].firstEdge;  
		G.AdjList[v2].firstEdge = e;  
	}  
}

1687: 图-无向连通图的深度优先遍历

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

提示