2237: DS-模拟题5
金币值：2
定数：9
时间限制：1.000 s
内存限制：128 M
正确：16
提交：57
正确率：28.07% 命题人：
题目描述
建立一个无向连通图的邻接矩阵（顶点中存储的信息为顶点编号），然后给出深度优先搜索该图得到的序列（设图中顶点从1开始编号，从编号为1的顶点开始深度优先搜索）。(仅提交填空部分)
#include <stdio.h>
#define MAXVEX 100 /* 最大顶点数由用户定义 */
typedef struct {
char vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];//下标为0的地方不存储有效数据
int numNodes;
int numEdges;
} AMGraph;
int visited[MAXVEX]; //设置一个全局数组表示图中的顶点是否已经访问过，0号单元不表示有效数字
void DFS(AMGraph G, int v);
void CreateGraph(AMGraph &G) ; /*该函数平台已提供*/
int main(void) {
AMGraph G;
scanf("%d %d",&G.numNodes,&G.numEdges);
CreateGraph(G);
DFS(G,1); //从编号为1的顶点开始进行深度优先搜索
return 0;
}
void DFS(AMGraph G, int v) {
______________
} 输入格式
第1行输入两个整数，分别表示图中的顶点数n和边数m
第2-m+1行每行输入两个整数i和j，分别表示编号为i的顶点和编号为j（编号从1开始）的顶点之间有一条边
第2-m+1行每行输入两个整数i和j，分别表示编号为i的顶点和编号为j（编号从1开始）的顶点之间有一条边
输出格式
共1行信息有n个整数，表示深度优先搜索该图得到的序列，序列之间用一个空格隔开
输入样例 复制
8 9
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 7输出样例 复制
1 2 4 8 5 3 6 7提示
平台已提供的代码如下(文心一言费好大劲才写出出来并调试成功的，大家借鉴一下):
void CreateGraph(AMGraph &G) {
// 初始化顶点信息，这里假设顶点信息不需要，因此省略
// 初始化邻接矩阵，将所有元素设为0
for (int i = 1; i <= G.numNodes; i++) {
for (int j = 1; j <= G.numNodes; j++) {
G.arc[i][j] = 0;
}
}
// 输入边的信息，构建邻接矩阵
for (int k = 0; k < G.numEdges; k++) {
int i, j;
scanf("%d %d", &i, &j); // 读取一条边的两个顶点
G.arc[i][j] = 1; // 无向图，需要添加G->arc[j][i] = 1;
G.arc[j][i] = 1;
}
}