数据结构快速回顾——图的遍历

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <queue> 
#define NODE_SIZE 	100


typedef struct __GRAPH{

	int	n;
	int e;
	int matrix[NODE_SIZE][NODE_SIZE];
}Graph;

//使用栈 递归式深度优先遍历 
void DFS_0(Graph g, int v0, bool* visit)
{
	int i,j,k;
	visit[v0] = true;
	printf("visit %d\t",v0);
	
	for(i =0; i <g.n; i++)
	{
		if(g.matrix[v0][i] != 0 && visit[i] == false)
		{
			DFS_0(g,i,visit); 
		}
	}	

}

//使用栈 非递归式深度优先遍历 
void DFS(Graph g, int v0)
{
	bool *visit = new bool[g.n];
	int i,j,k;
	for( i =0;i < g.n; i++)
	{
		visit[i] = false;
	}

	visit[v0] = true;
	printf("visit %d\t",v0);
	std::stack<int> s;
	s.push(v0);
	
	while(!s.empty())
	{
		int tmpNode,i;
		tmpNode = s.top();
		
		for(i =0; i <g.n; i++)
		{
			if(g.matrix[tmpNode][i] != 0 && visit[i] == false)
			{
				printf("visit %d\t",i);
				visit[i] = true;
				s.push(i);
				break;
			}
		}
		if(i == g.n)
			s.pop();
	}
}

//使用栈 非递归式广度优先遍历 
void BFS(Graph g, int v0)
{
	bool *visit = new bool[g.n];
	int i,j,k;
	for( i =0;i < g.n; i++)
	{
		visit[i] = false;
	}

	visit[v0] = true;
	printf("visit %d\t",v0);
	std::queue<int> s;
	s.push(v0);
	
	while(!s.empty())
	{
		int tmpNode,i;
		tmpNode = s.front();
		s.pop();
		
		for(i =0; i <g.n; i++)
		{
			if(g.matrix[tmpNode][i] != 0 && visit[i] == false)
			{
				printf("visit %d\t",i);
				visit[i] = true;
				s.push(i);
			}
		}

	}
}

int main()
{
	int m, n;

	while(scanf("%d %d",&n,&m)!= EOF)
	{
		Graph g;
		g.n = n;
		g.e= m;

		int *dist = (int*)calloc(n,sizeof(int));
		int *path = (int*)calloc(n,sizeof(int));


		memset(g.matrix,0,sizeof(int)*NODE_SIZE*NODE_SIZE); 

		int s,t;//边的起点和终点 
		for(int i =0; i <m; i++)
		{
			scanf("%d %d",&s,&t);
			if(g.matrix[s][t] > 0)
				continue;
			g.matrix[s][t]=i+1;
			g.matrix[t][s]=g.matrix[s][t];
		}

		DFS(g,0);
		printf("\nDFS_0: \n");
		
		bool *visit = new bool[g.n];
		for( int i =0;i < g.n; i++)
		{
			visit[i] = false;
		}

		DFS_0(g,0,visit);
		printf("\nBFS_0: \n");
		BFS(g,0);
	}

}

5	5
0 	1
0	2
2 	4
4	1
1	3