数据结构:图的深度优先搜索

以邻接矩阵作存储结构,编写程序对给定的无向图(图中包含n个顶点,编号为0至n-1)进行深度优先遍历,并在遍历的过程中计算图G的连通分量个数及边的数目。

本题限定在遍历过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问,以顶点0为遍历起点。

邻接矩阵的类型描述

#define MaxVexNum 20 //最大顶点数目
typedef struct
{ int arcs[MaxVexNum][MaxVexNum];
int vexnum, arcnum;
}AMGraph;
输入格式:
第一行输入图的顶点数和边数。

接下来每行代表一条边,输入边依附的两个顶点的编号。各边输入先后次序无要求。

输出格式
输出分三行

第一行 深度优先遍历序列。序列中每个顶点编号后跟一个空格。
第二行 连通分量个数
第三行 边数

输入样例:
9 8
0 1
0 2
1 3
3 4
2 5
2 6
5 6
7 8
输出样例:
0 1 3 4 2 5 6 7 8
2
8