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

电玩女神 2022-05-27 07:20 561阅读 0赞

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

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

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

![20180413184647515][]

图中包括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);
    		}
    	}
    }

输出结果如下：

![20180413185320986][]

[20180413184647515]: /images/20220527/050e77c0fef440e7b50d67d9c87762fd.png
[20180413185320986]: /images/20220527/7fad06f19b604ca98deb01df4d3fea09.png