从零开始学数据结构系列之第四章《图的遍历总代码》

2024-07-10 15:10:03
开发
19

文章目录

概念回顾
- 深度优先遍历（DFS）
- - 概念
  - 图的深度优先遍历
  - 深度优先遍历算法步骤
- 广度优先遍历（BFS）
- - 概念
  - 广度优先遍历算法步骤
程序总代码
往期回顾

概念回顾

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

深度优先遍历（DFS）

概念

深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。

深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点,再访问与邻接且未被访问的任一顶点,重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

简单来说就是：

这种遍历方式主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完成。它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

有个简单的口诀可以方便记忆：

一条路走到黑
不到南墙不回头撞墙之后再回头
回头之后再撞墙
直到无墙可撞为止

图的深度优先遍历

深度优先遍历，从初始访问结点出发，初始访问节点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前的第一个邻接结点
我们可以看到，这样的访问策略是优先纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问
显然，深度优先搜索是一个递归的过程

深度优先遍历算法步骤

访问初始结点 v，并标记结点 v 为已访问
查找结点 v 的第一个邻接结点 w
若 w 存在，则继续访问 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续
若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当作另一个 v ，然后进行步骤 123）
查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3

广度优先遍历（BFS）

概念

广度优先遍历(Breadth First Search)，又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

简单来说就类似于我们之前学的层次遍历

广度优先遍历算法步骤

访问初始结点 v 并标记结点 v 为已访问
结点 v 入队列
当队列非空时，继续执行，否则算法结束
出队列，取得头结点 u
查找结点 u 的第一个邻接结点 w
若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤
1. 若结点 w 尚未被访问，则访问结点 w 并标记为已访问
2. 结点 w 入队列
3. 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤6

程序总代码

我们用的是以下这张图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VdtKDkiM-1720206040893)(https://i-blog.csdnimg.cn/direct/b8a615ffedfa487fab7a250e92aecf19.png)]
同时注意，这里是不带权值的图

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5

/*
*	vexs -存放的是顶点，也就是内容，如字符“ABCD”这样子的
*	arcs -存放的是边数，也就是是否相连，相连设为1，不相连设为0
*	vexNum  -存放的是顶点数量
*	arcNum	-存放的是边数，也就是各顶点的连接的总数，注意这边用的是无序，所以要/2，例如AB与BA实际上就是一条，但是数还是会数2条
*/

typedef struct Graph 
{
    char* vexs;
    int** arcs;
    int vexNum;
    int arcNum;
}Graph;

typedef struct Queue {
    int front;
    int rear;
    int data[MAXSIZE];
}Queue;

Queue* initQueue() 
{
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    Q->front = Q->rear = 0;
    return Q;
}

int isFull(Queue* Q) 
{
    if ((Q->rear + 1) % MAXSIZE == Q->front) 
	{
        return 1;
    }
    else {
        return 0;
    }
}

int isEmpty(Queue* Q) 
{
    if (Q->front == Q->rear) 
	{
        return 1;
    }
    else {
        return 0;
    }
}

int enQueue(Queue* Q, int data) 
{
    if (isFull(Q)) 
	{
        return 0;
    }
    else 
	{
        Q->data[Q->rear] = data;
        Q->rear = (Q->rear + 1) % MAXSIZE;
        return 1;
    }
}

int deQueue(Queue* Q) 
{
    if(isEmpty(Q))
	{
        return -1;
    }
    else {
        int data = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAXSIZE;
        return data;
    }
}

Graph* initGraph(int vexNum) 
{
	int i=0;
	Graph *T =(Graph*)malloc(sizeof(Graph));
	T->vexs =(char*)malloc(sizeof(char) * vexNum);
	T->arcs =(int**)malloc(sizeof(int*) * vexNum);
	T->vexNum = vexNum;
	T->arcNum = 0;
	for(i=0;i<T->vexNum;i++)
		T->arcs[i] =(int*)malloc(sizeof(int) * vexNum);
	return T;
}

void createGraph(Graph* G, char* vexs, int* arcs) 
{
	int i=0,j=0;
	for(;i<G->vexNum;i++)
	{
		G->vexs[i] = vexs[i];
		for(;j<G->vexNum;j++)
		{
            // 二维数组存放值，差不多就是偏移量计算
			G->arcs[i][j] = *(arcs + i * G->vexNum +j);
			 if (G -> arcs[i][j])
                G -> arcNum ++;
		}
	}
	G -> arcNum/=2;
}

void DFS(Graph* G, int* visited, int index) 
{
	int i=0;
	printf("%c ",G->vexs[index]);
	visited[index] = 1;
	for(i=0;i<G->vexNum;i++)
	{
		if(G->arcs[index][i] && !visited[i])
			DFS(G,visited,i);
	}
}

void BFS(Graph* G, int* visited, int index) 
{
	int j = 0;
	int i = 0;
    Queue* Q = initQueue();
    printf("%c ", G -> vexs[index]);
    visited[index] = 1;
    enQueue(Q, index);
    while (!isEmpty(Q)) 
	{
        i = deQueue(Q);
        for (j = 0; j < G -> vexNum; j++) 
		{
            if (G -> arcs[i][j] && !visited[j]) 
			{
                printf("%c ", G -> vexs[j]);
                visited[j] = 1;
                enQueue(Q, j);
            }
        }
    }
}

int main() 
{
	int i = 0;
	int arcs[5][5] = 
	{
        0,1,1,1,0,
        1,0,1,1,1,
        1,1,0,0,0,
        1,1,0,0,1,
        0,1,0,1,0
    };
    Graph* G = initGraph(5);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (; i < G -> vexNum; i++)
        visited[i] = 0;
    
    createGraph(G, "ABCDE", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
	for (i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    BFS(G, visited, 0);
    printf("\n");
    return 0;
}

往期回顾

原文地址:https://blog.csdn.net/qq_62548908/article/details/140203380 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1810934491624116224.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部