树的遍历-深度优先遍历和广度优先遍历

深度优先遍历类似于树的先序遍历。假设给定初态是图中所有顶点均未被访问过，从图中某一顶点vi出发遍历图中的定义如下：首先访问出发点vi，并将其访问标志置为1；然后，从vi出发点依次搜索vi的每个邻接点vj。如vj未被访问过，则以vj为新的出发点继续进行深度优先搜索。

广度优先遍历，类似于树的按层次遍历。设图G是连通的，且图G的初态是所有顶点均未被访问过。从图G的任一顶点vi出发按广度优先搜索遍历图的步骤是：访问vi后，依次访问与vi邻接的所有顶点w1,w2,w3......wn，再按w1,w2,w3......wn的顺序访问其中每个顶点的所有未被访问的邻接点，再按此顺序，依次访问它们所有未被访问的邻接点，以此类推，直到图中所有顶点均被访问过为止。

比如，以下面的图为例（包括不连通的顶点）：

图中包括9个顶点，顶点序号为0~8，顶点信息为依次为字符 'a' ~ ' i'，其中顶点8不与其他顶点相连通。

利用递归形式的深度优先遍历：

遍历结果：0->1->3->7->4->5->2->6 ->8         输出结果：a->b->d->h->e->f->c->g->i

利用非递归形式（栈）的深度优先遍历：

遍历结果：0->1->3->7->4->5->2->6 ->8         输出结果：a->b->d->h->e->f->c->g->i

利用广度优先遍历（队列）：

遍历结果：0->1->2->3->4->5->6->7 ->8         输出结果：a->b->c->d->e->f->g->h->i

程序如下（有问题共同交流）：

#include<iostream>
#include<assert.h>
#include<string>

#define NUM 9
#define MAXSIZE 15
using namespace std;

typedef struct graph
{
	char vertexs[NUM];
	int matrixs[NUM][NUM];
};

typedef struct stack
{
	int dataNum[MAXSIZE];
	int top;
	int stackSize;
};

typedef struct queue
{
	int dataArray[MAXSIZE];
	int front;
	int rear;
};

//直接创建图
void CreateGraph(graph * g);
//深度优先遍历（递归形式）图中所有连通顶点，打印顶点信息
void DFS(graph* g, int i, int visit[NUM]);
//深度优先遍历（递归形式）图中剩余其他顶点，打印顶点信息
void FinalDFS(graph* g, int visit[NUM]);

//创建栈
void CreateStack(stack *s);
//判断栈是否为空
int EmptyStack(stack *s);
//将顶点序号入栈
void PushStack(stack *s, int k);
//出栈，取栈顶元素
int PopStack(stack *s);
//利用栈，深度优先遍历（非递归形式）图中每个顶点
void DFS_Stack(graph *g, int i, stack* s, int visit[NUM]);
//利用栈，深度优先遍历（非递归形式）图中所有顶点
void FinalDFS_Stack(graph *g, stack* s, int visit[NUM]);

//创建队列
void CreateQueue(queue *q);
//判断队列是否为空
int EmptyQueue(queue *q);
//入队，将顶点序号入队
void ENQUEUE(queue *q, int e);
//出队，将队头元素出队
int DEQUEUE(queue *q);
//利用队列，广度优先遍历图中和源点i相连通的所有顶点
void BFS_Queue(graph *g, int i, queue* q, int visit[NUM]);
//利用队列，广度优先遍历图中所有顶点（包括不连通顶点）
void FinalBFS_Queue(graph *g, queue* q, int visit[NUM]);


int main()
{
	graph g;
	CreateGraph(&g);
	int visit[NUM] = {0};

	//利用深度优先搜索遍历（递归形式）
	printf("深度优先遍历（递归形式）: ");
	FinalDFS(&g,visit);
	printf("\n");

	//利用深度优先遍历（非递归形式：栈）
	printf("深度优先遍历（非递归形式 栈）: ");
	int visit1[NUM] = { 0 };
	stack s;
	CreateStack(&s);
	FinalDFS_Stack(&g, &s, visit1);
	printf("\n");

	//利用广度优先遍历（队列）
	printf("广度优先遍历（队列）: ");
	int visit2[NUM] = { 0 };
	queue q;
	CreateQueue(&q);
	FinalBFS_Queue(&g, &q, visit2);
	printf("\n");

	return 0;
}

//创建图
void CreateGraph(struct graph * g)
{
	//默认9个顶点信息依次为字符"a b c d e f g h i"
	for (int i = 0; i < NUM; i++)
	{
		g->vertexs[i] = 'a'+i;
	}

	//直接创建图的邻接矩阵
	g->matrixs[0][1] = 1;
	g->matrixs[0][2] = 1;

	g->matrixs[1][0] = 1;
	g->matrixs[1][3] = 1;
	g->matrixs[1][4] = 1;

	g->matrixs[2][0] = 1;
	g->matrixs[2][5] = 1;
	g->matrixs[2][6] = 1;

	g->matrixs[3][1] = 1;
	g->matrixs[3][7] = 1;

	g->matrixs[4][1] = 1;
	g->matrixs[4][7] = 1;

	g->matrixs[5][2] = 1;
	g->matrixs[5][7] = 1;

	g->matrixs[6][2] = 1;
	g->matrixs[6][7] = 1;

	g->matrixs[7][3] = 1;
	g->matrixs[7][4] = 1;
	g->matrixs[7][5] = 1;
	g->matrixs[7][6] = 1;
}


//深度优先遍历（递归形式）图中所有联通顶点，打印顶点信息
void DFS(graph* g, int i, int visit[NUM])
{
	//将访问到的顶点的标志位赋1
	visit[i] = 1;
	//打印访问到的顶点信息
	printf("%c ", g->vertexs[i]);
	for (int j = 0; j < NUM; j++)
	{
		if (g->matrixs[i][j]==1 && visit[j]==0)
		{
			DFS(g,j,visit);
		}
	}
}

//深度优先遍历（递归形式）图中所有顶点，打印顶点信息
void FinalDFS(graph* g, int visit[NUM])
{

	//遍历所有顶点
	for (int m = 0; m < NUM; m++)
	{
		if (visit[m] == 0)
		{
			DFS(g, m, visit);
		}
	}
}

//创建栈
void CreateStack(stack *s)
{
	//将栈置空
	s->top = -1;
	s->stackSize = MAXSIZE;
}

//判断栈是否为空
int EmptyStack(stack *s)
{
	if (s->top==-1)  return 1;
    else return 0;
}

//将顶点序号入栈
void PushStack(stack *s, int k)
{
	if (s->top == (s->stackSize-1))
	{
		printf("overflow");
		return;
	}
	else
	{
		s->top++;
		s->dataNum[s->top] = k;
	}
}

//出栈，取栈顶元素
int PopStack(stack *s)
{
	if (EmptyStack(s)==1)
	{
		return -1;
	}
	else
	{
		int vexNum=s->dataNum[s->top];
		s->top--;
		return vexNum;
	}
}

//利用栈，深度优先遍历（非递归形式）图中每个顶点
void DFS_Stack(graph *g, int i, stack* s, int visit[NUM])
{
	visit[i] = 1;
	//将第一个顶点入栈
	PushStack(s,i);
	//打印第一个顶点信息
	printf("%c ",g->vertexs[s->dataNum[s->top]]);
	while (s->top!=-1)
	{
		int x = s->dataNum[s->top];
		int flag = 0;
		for (int j = 0; j < NUM;j++)
		{
			if (g->matrixs[x][j] == 1 && visit[j] == 0)
			{
				visit[j] = 1;
				PushStack(s,j);
				flag = 1;
				printf("%c ", g->vertexs[s->dataNum[s->top]]);
				break;
			}
		}	
		if (flag==0)
		{		
			PopStack(s);
		}  
	}
}

//利用栈，深度优先遍历（非递归形式）图中所有顶点
void FinalDFS_Stack(graph *g, stack* s, int visit[NUM])
{

	//遍历所有顶点
	for (int m = 0; m < NUM; m++)
	{
		if (visit[m] == 0)
		{
			DFS_Stack(g, m, s, visit);
		}
	}
}

//创建队列
void CreateQueue(queue *q)
{
	q->front = q->rear = 0;
}

//判断队列是否为空
int EmptyQueue(queue *q)
{
	if (q->front == q->rear) return 1;
	else return 0;
}

//入队，将顶点序号入队
void ENQUEUE(queue *q, int e)
{
	if (q->rear-q->front==(MAXSIZE-1))
	{
		printf("队满上溢");
		return;
	}
	else
	{
		q->dataArray[q->rear] = e;
		q->rear++;
	}
}

//出队，将队头元素出队
int DEQUEUE(queue *q)
{
	if (EmptyQueue(q)==1)
	{
		return -1;
	}
	else
	{
		int frontNum =q->dataArray[q->front];
		q->front++;
		return frontNum;
	}
}

//利用队列，广度优先遍历图中和源点i相连通的所有顶点
void BFS_Queue(graph *g, int i, queue* q, int visit[NUM])
{
	visit[i] = 1;
	//将第一个顶点入队
	ENQUEUE(q,i);
	//打印第一个顶点信息
	//printf("%c ", q->dataArray[q->front]);

	while (EmptyQueue(q)!=1)
	{
		int k = DEQUEUE(q);
		printf("%c ", g->vertexs[k]);
		for (int j = 0; j < NUM;j++)
		{
			if (g->matrixs[k][j] == 1 && visit[j] == 0)
			{
				visit[j] = 1;
				ENQUEUE(q, j);
			}
		}
	}
}

//利用队列，广度优先遍历图中所有顶点（包括不连通顶点）
void FinalBFS_Queue(graph *g, queue* q, int visit[NUM])
{
	//遍历所有顶点
	for (int m = 0; m < NUM; m++)
	{
		if (visit[m] == 0)
		{
			BFS_Queue(g, m, q, visit);
		}
	}
}

输出结果如下：