图的遍历：深度优先遍历

/*
	图的遍历：深度优先遍历
	递归
	2014-4-3 08:36:49
*/

/*
	测试数据
9 12
5 8 29
6 1 12
8 3 11
1 2 4
3 1 22
4 3 17
7 4 25
6 5 9
8 7 7
1 6 9
3 2 19
6 7 4

*/

#include <iostream>
#include <cstdlib>
#define MAX 10000
using namespace std;

int head[MAX]; //存储节点数组中起点为i的位置,0为结束标记
struct Node{
	int to, w, next; //起点，权值，下一点
};
Node Edges[MAX];

bool s[MAX];

void DFS(int x){
	s[x] = true; //标记当前点已被访问
	printf("%d\n", x);
	int i;
	//对于每个未被访问的相邻节点，使用DFS。遍历返回后尝试其他支路
	for(i = head[x]; i != 0; i = Edges[i].next){
		if(s[Edges[i].to] == false) DFS(Edges[i].to);
	}
}

int main(){
	int n, m; //n个点，m条边
	int to, from, w;
	
	//存储
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		cin >> from >> to >> w;
		Edges[i].to = to;
		Edges[i].w = w;
		Edges[i].next = head[from];
		head[from] = i; //更新
	}
	
	/*//遍历
	for(int i = 1; i <= n; ++i){
		for(int j = head[i]; j != 0; j = Edges[j].next)
			cout << i << ‘ ‘ << Edges[j].to << ‘ ‘ << Edges[j].w << endl;
	}*/
	
	//DFS
	DFS(1);
	system("pause");
	return 0;
}

图的遍历：深度优先遍历,布布扣,bubuko.com

图的遍历：深度优先遍历

原文：http://blog.csdn.net/chang_mu/article/details/22897733