7-41 图深度优先遍历分数 20

编写程序对给定的有向图（不一定连通）进行深度优先遍历，图中包含n个顶点，编号为0至n-1。本题限定在深度优先遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点0为遍历起点。

输入格式:

输入第一行为两个整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过50。接下来e行表示每条边的信息，每行为两个整数a、b，表示该边的端点编号，但各边并非按端点编号顺序排列。

输出格式:

输出为一行整数，每个整数后一个空格，即该有向图的深度优先遍历结点序列。

输入样例1:

3 3
0 1
1 2
0 2

输出样例1:

0 1 2 

输入样例2:

4 4
0 2
0 1
1 2
3 0

输出样例2:

0 1 2 3 

代码长度限制

16 KB

时间限制

50 ms

内存限制

64 MB

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#define MaxVertexNum 20000
int Visited[MaxVertexNum];
typedef struct ENode* PtrToENode;
struct ENode {
	int V1, V2;
};
typedef PtrToENode Edge;
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode {
	int AdjV;
	PtrToAdjVNode Next;
};
typedef struct Vnode {
	PtrToAdjVNode FirstEdge;
}AdjList[MaxVertexNum];
typedef struct GNode* PtrToGNode;
struct GNode {
	int Nv;
	int Ne;
	AdjList G;
};
typedef PtrToGNode LGraph;
LGraph CreateGraph(int VertexNum) {
	int V;
	LGraph Graph;
	Graph = (LGraph)malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for (V = 0; V < Graph->Nv; V++)
		Graph->G[V].FirstEdge = NULL;
	return Graph;
}
void InsertEdge(LGraph Graph, Edge E) {
	PtrToAdjVNode NewNode, w;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V2;
	NewNode->Next = NULL;
	w = Graph->G[E->V1].FirstEdge;
	if (w == NULL)
		Graph->G[E->V1].FirstEdge = NewNode;
	else {
		if (w->AdjV > NewNode->AdjV) {
			Graph->G[E->V1].FirstEdge = NewNode;
			NewNode->Next = w;
		}
		else {
			while (w->Next && w->Next->AdjV < NewNode->AdjV) {
				w = w->Next;
			}
			NewNode->Next = w->Next;
			w->Next = NewNode;
		}
	}
}
void Visit(int v) {
	printf("%d ", v);
}
void DFS(LGraph Graph, int v) {
	if (!Visited[v]) {
		PtrToAdjVNode w;
		Visit(v);
		Visited[v] = 1;
		for (w = Graph->G[v].FirstEdge; w; w = w->Next) {
			if (!Visited[w->AdjV])
				DFS(Graph, w->AdjV);
		}
	}
}
int main() {
	LGraph Graph;
	Edge E;
	int V, e;
	int Nv, i;
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	scanf("%d", &(Graph->Ne));
	if (Graph->Ne != 0) {
		E = (Edge)malloc(sizeof(struct ENode));
		for (i = 0; i < Graph->Ne; i++) {
			scanf("%d%d", &E->V1, &E->V2);
			InsertEdge(Graph, E);
		}
	}
	for (i = 0; i < Graph->Nv; i++)
		Visited[i] = 0;
	for (i = 0; i < Graph->Nv; i++) {
		if (!Visited[i]) {
			DFS(Graph, i);
		}
	}
	return 0;
}