数据结构-图的深度优先遍历(DFS)

3/8/2017来源:ASP.NET技巧人气:371

#include <stdio.h>

#define MAX 6
//邻接矩阵 
int matrix[MAX][MAX];

//图的深度优先遍历 
void DFS(int s) {
	int stack[MAX] = {0};  //栈 
	int visited[MAX] = {0};

	int top = 0, down = 0;  //栈顶和栈底

	stack[top] = s;//入栈 
	visited[s] = 1;
	PRintf("%d ", s + 1);
	
	int i;
	int v = s;
	int count = 1;
	while (count != MAX) {
		int is = 0;
		for (i = 0; i < MAX; i++) {
			if (matrix[v][i] == 1) {
				if (visited[i] == 0) {
					stack[++top] = i;  //入栈 
					visited[i] = 1;
					printf("%d ",i + 1);
					count++;
					v = stack[top];
					is = 1;
					break;
				}
			}
		}

		if (is == 0) {  //不存在没有被访问过的邻结点  弹出一个顶点 
			v = stack[--top];
		}
	}
	printf("\n");
}

void inputData() {
	int i, j;
	freopen("data.txt", "r", stdin);
	/*
	0 1 0 0 1 0
	1 0 1 0 1 0
	0 1 0 1 0 0
	0 0 1 0 1 1
	1 1 0 1 0 0
	0 0 0 1 0 0 
	*/
	for (i = 0; i < MAX; i++) {
		for (j = 0; j < MAX; j++) {
			scanf("%d", &matrix[i][j]);
		}
	}
}

int main() {

	inputData();
	for (int i = 0; i < MAX; i++) {
		DFS(i); //以i作为起始点进行深度优先遍历 
	}
	
	return 0;
}