首页 > 编程语言 >图——图的遍历（DFS与BFS算法详解）

图——图的遍历（DFS与BFS算法详解）

时间：2024-07-19 16:56:09浏览次数：13  
标签：遍历 int graph DFS BFS 访问 visited

前面的文章中我们学习了图的基本概念和存储结构，大家可以通过下面的链接学习：

图的定义和基本术语

图的类型定义和存储结构

这篇文章就来学习一下图的重要章节——图的遍历。

目录

一，图的遍历定义：

二，深度优先搜索(DFS)

连通图的深度优先遍历

邻接矩阵法实现DFS

邻接表法实现DFS

DFS算法效率分析：

非连通图的深度优先遍历

三， 广度优先搜索（BFS）

邻接矩阵法实现BFS

邻接表法实现BFS

 BFS算法效率分析：

DFS与BFS算法效率比较

一，图的遍历定义：

        从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

图遍历的实质：找每个顶点的邻接点的过程。

要进行图的遍历，我们需要知道图的特点，从而用合适，高效的方法来实现遍历。

图有哪些特点？

图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 

那么，如何避免在遍历时重复访问？

解决思路：

设置辅助数组 visited [n ]，用来标记每个被访问过的顶点。

        初始状态为0

        被访问，改 visited [i]为1，防止被多次访问。

图常用的遍历有两种：

深度优先搜索（Depth First Search,DFS）    

广度优先搜索(Breadth First Search,BFS)    

二，深度优先搜索(DFS)

引例：

点亮迷宫中所有的灯，我们会一条道走到头，如果走不动了，再往回退寻找其他没有走过的。

因此我们可以总结DFS的详细归纳：

在访问图中某一起始顶点 v 后，由 v 出发，访问 它的任一邻接顶点 w 1 ； 再从 w 1 出发DFS 邻接 但还 未被访问 过的顶点 w 2 ； 然后再从 w 2 出发，进行类似的访问， … 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步， 退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。           如果有， 则访问此顶点，之后再从此顶点出发，进行与前述类似的访问。    

         如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

连通图的深度优先遍历

仿树的先序遍历过程

 先根，再左子树，最后右子树。

下面是一个练习：

 它的深度优先搜索结果是：2→1→3→5→4→6

那么，在计算机中我们该如何实现DFS的过程？

邻接矩阵法实现DFS

在上一篇文章中我们学习了图的存储结构的邻接矩阵法，借助一个辅助数组 visited [n ]来保存邻接矩阵的信息。

在编程时，使用邻接矩阵法DFS的实现可以采用递归算法：

void DFS(AMGraph G, int v){        	//图G为邻接矩阵类型 
  cout<<v;  visited[v] = true;  		//访问第v个顶点
  for(w = 0; w< G.vexnum; w++)  	//依次检查邻接矩阵v所在的行  
        if((G.arcs[v][w]!=0)&& (!visited[w]))  
            DFS(G, w); 
      //w是v的邻接点，如果w未访问，则递归调用DFS 
}

而下面是完整的c语言使用邻接矩阵法来实现图的深度优先搜索：

注意：

这里我使用了C语言的一个库#include <stdbool.h>，来声明我使用了布尔型数据

大家也可以自己定义布尔类型，true代表1为真，false代表0为假

typedef int bool;
#define true 1
#define false 0

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// 定义邻接矩阵和访问标记数组
int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
int num_vertices;

// 深度优先搜索函数
void dfs(int vertex) {
    // 标记当前节点为已访问
    visited[vertex] = true;
    // 输出当前节点
    printf("%d ", vertex);

    // 遍历当前节点的所有邻接节点
    for (int i = 0; i < num_vertices; i++) {
        // 如果邻接节点存在且未被访问，则递归调用dfs函数
        if (graph[vertex][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

int main() {
    // 输入顶点数和边数
    printf("请输入顶点数和边数：");
    scanf("%d", &num_vertices);

    // 输入邻接矩阵
    printf("请输入邻接矩阵：");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    // 输出深度优先遍历结果
    printf("深度优先遍历结果：");
    // 初始化访问标记数组
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
    }

    // 遍历所有节点，如果节点未被访问，则调用dfs函数
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    return 0;
}

输入实例：

输出结果：

 

邻接表法实现DFS

我们知道图的存储结构除了邻接矩阵法之外还有邻接表法，那么使用邻接表法能否实现图的深度优先搜索？ 

当然可以，同样要借助辅助数组visited [n ]

 使用邻接表法DFS的实现也可以采用递归算法：

void DFS(ALGraph G, int v){        //图G为邻接表类型 
  cout<<v;  visited[v] = true;          //访问第v个顶点
  p= G.vertices[v].firstarc;             //p指向v的边链表的第一个边结点 
while(p!=NULL){              	      //边结点非空 
  w=p->adjvex;               	      //表示w是v的邻接点 
  if(!visited[w])  DFS(G, w); 	     //如果w未访问，则递归调用DFS 
  p=p->nextarc;                	     //p指向下一个边结点 
 } 
}

在实际的编程中，使用邻接表法实现的DFS代码：

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node* adjLists[MAX_VERTICES];
} Graph;

// 添加边函数
void addEdge(Graph* graph, int src, int dest) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// 深度优先搜索函数
void DFS(Graph* graph, int vertex, int visited[]) {
    // 标记当前节点为已访问
    visited[vertex] = 1;
    // 输出当前节点
    printf("%d ", vertex);

    // 遍历当前节点的所有邻接节点
    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        // 如果邻接节点未被访问，则递归调用DFS函数
        if (!visited[connectedVertex]) {
            DFS(graph, connectedVertex, visited);
        }
        temp = temp->next;
    }
}

// 深度优先遍历函数
void DFSTraversal(Graph* graph) {
    // 初始化访问标记数组
    int visited[MAX_VERTICES] = {0};
    for (int i = 0; i < graph->numVertices; i++) {
        // 如果节点未被访问，则调用DFS函数
        if (!visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

int main() {
    // 创建图
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = 5;

    // 初始化邻接表
    for (int i = 0; i < graph->numVertices; i++) {
        graph->adjLists[i] = NULL;
    }

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);

    // 输出深度优先遍历结果
    printf("Depth First Traversal: ");
    DFSTraversal(graph);

    return 0;
}

输出结果：

Depth First Traversal: 0 2 1 4 3 

DFS算法效率分析：

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。

用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

结论：

稠密图适于在邻接矩阵上进行深度遍历；

稀疏图适于在邻接表上进行深度遍历。

非连通图的深度优先遍历

如下图例子，连通分量分开访问，先DFS访问完第一个，再访问第二个。

三， 广度优先搜索（BFS）

同样是点亮迷宫中的灯案例，广度优先搜索没有一条道走到黑，而是每个道都走，一层一层实现遍历。

 简单归纳：

        在访问了起始点v之后，依次访问 v的邻接点；

        然后再依次访问这些顶点中未被访问过的邻接点；

        直到所有顶点都被访问过为止。

 广度优先搜索是一种 分层 的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。   因此，广度优先搜索 不是一个递归 的过程，其算法也不是递归的。

 BFS基本思想：——仿树的层次遍历过程

在计算机中，如何实现BFS？

与DFS相比，除辅助数组visited [n ]外，还需再开一辅助队列。

算法思想：

从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。

只要队列不空，则重复下述处理。

           ① 队头顶点u出队。

           ② 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。

同样对于BFS可以使用邻接矩阵或邻接表法来实现。

邻接矩阵法实现BFS

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

#define MAX_SIZE 100

// 定义队列结构体
typedef struct {
    int data[MAX_SIZE]; // 队列数据
    int front, rear; // 队头和队尾指针
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否已满
int isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue *q, int x) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        exit(1);
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

// 出队
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        exit(1);
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return x;
}

// 广度优先搜索
void BFS(int graph[][MAX_SIZE], int visited[], int start, int n) {
    Queue q;
    initQueue(&q);
    enqueue(&q, start);
    visited[start] = 1;
    printf("%d ", start);

    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        for (int i = 0; i < n; i++) {
            if (graph[current][i] && !visited[i]) {
                enqueue(&q, i);
                visited[i] = 1;
                printf("%d ", i);
            }
        }
    }
}

int main() {
    int n, e;
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &n, &e);

    int graph[MAX_SIZE][MAX_SIZE] = {0};
    int visited[MAX_SIZE] = {0};

    printf("Enter the edges (u v):\n");
    for (int i = 0; i < e; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1; 
    }

    printf("BFS traversal starting from vertex 0:\n");
    BFS(graph, visited, 0, n);

    return 0;
}

 输入案例

输出结果

邻接表法实现BFS

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

// 定义邻接表结构体
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 定义图结构体
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

// 创建新的节点
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 添加边到邻接表
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 如果是无向图，需要添加反向边
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 初始化图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// BFS遍历图
void BFS(Graph* graph, int startVertex) {
    int visited[graph->numVertices];
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }

    // 创建一个队列并初始化起始顶点
    Node* queue = createNode(startVertex);
    visited[startVertex] = 1;

    // 当队列不为空时继续遍历
    while (queue != NULL) {
        // 打印当前顶点
        printf("%d ", queue->vertex);

        // 获取当前顶点的邻接顶点列表
        Node* temp = graph->adjLists[queue->vertex];

        // 遍历邻接顶点列表
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            if (!visited[adjVertex]) {
                // 将未访问过的邻接顶点加入队列并标记为已访问
                Node* newNode = createNode(adjVertex);
                newNode->next = queue->next;
                queue->next = newNode;
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }

        // 弹出队列的第一个元素
        Node* dequeuedNode = queue;
        queue = queue->next;
        free(dequeuedNode);
    }
}

int main() {
    int vertices = 6;
    Graph* graph = createGraph(vertices);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 5);

    printf("BFS traversal starting from vertex 0: ");
    BFS(graph, 0);

    return 0;
}

输出结果：

 BFS算法效率分析：

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。

用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

DFS与BFS算法效率比较

空间复杂度相同，都是O(n)(借用了堆栈或队列）；

时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

最后是一个小练习

 图的遍历到此就结束啦，如果文章对你有用的话请点个赞支持一下吧！

标签：遍历,int,graph,DFS,BFS,访问,visited
From： https://blog.csdn.net/Blusher1/article/details/140440146

相关文章

  • mysql8+seaweedfs-csi-driver
     mysql8使用seaweedfs-storage 启动异常如下：mysql07:28:20.10mysql07:28:20.11WelcometotheBitnamimysqlcontainermysql07:28:20.11Subscribetoprojectupdatesbywatchinghttps://github.com/bitnami/containersmysql07:28:20.12Submitissuesandfeatu......
  • 遍历（强连通）
    https://www.luogu.com.cn/problem/P2194第3题   遍历 查看测评数据信息给定n个点，m条边的有向图，每个节点有一个权重v(i)，你的任务是把n个点遍历一遍，点可以重复经过。允许的操作如下：每次你可以选择一个开始节点i，如果可以从i出发，最后可以回到i节点，那么你的花费为v(i)。问：最......
  • 代码随想录算法训练营Day13 | 二叉树理论基础 二叉树的递归遍历 前序、中序、后序遍历
    一、二叉树理论基础1. 二叉树种类①满二叉树：顾名思义就是结点都满的二叉树。定义：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。     深度为k，结点数为2^k-1的二叉树②完全二叉树：最后一层可以不满，但最后一层从左......
  • 170 加成序列 dfs 剪枝
    //170加成序列.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*https://www.acwing.com/problem/content/172/满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：X[1]=1X[m]=nX[1]<X[2]<…<X[m−1]<X[m]对于每个k（2≤k≤m）都存在两......
  • 代码随想录算法训练营第16天|LeetCode112路径总和LeetCode113路径总和iiLeetCode106.
    代码随想录算法训练营Day16代码随想录算法训练营第16天|LeetCode112路径总和LeetCode113路径总和iiLeetCode106.从中序与后序遍历序列构造二叉树LeetCode105.从前序与中序遍历序列构造二叉树目录代码随想录算法训练营前言LeetCode112路径总和,LeetCode113路径......
  • 算法力扣刷题记录 五十【106.从中序与后序遍历序列构造二叉树】和【105.从前序与中序
    前言记录三十八的四、二叉树构建通过层序遍历的数组实现。层序遍历中，某个节点下标是i，那么左孩子的下标2i+1，右孩子的下标2i+2。这是统一的规律。那么通过中序序列和后序序列如何构造二叉树？通过中序序列和前序序列如何构造二叉树？通过前序序列和后序序列如何构造二叉树？一......
  • 从前序与中序遍历序列构造二叉树-递归
    题目描述：个人题解：        只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。这样的话，我们就......
  • leetcode145. 二叉树的后序遍历，递归法+迭代法，全过程图解+步步解析，一点点教会你迭代法
    leetcode145.二叉树的后序遍历，递归法+迭代法给你一棵二叉树的根节点root，返回其节点值的后序遍历。示例1：输入：root=[1,null,2,3]输出：[3,2,1]示例2：输入：root=[]输出：[]示例3：输入：root=[1]输出：[1]递归法还是一如既往的简单。postorder函数是递归函数，用......
  • 利用递归的二叉树的先序，中序，后序遍历
    一.常见的二叉树的遍历①先序遍历：先访问根节点，再访问左右子树（根左右）③中序遍历：先访问左子树，再访问根节点，最后访问右子树（左根右）③后序遍历：先访问左右子树，再访问根节点（左右根）先定义二叉树的数据结构：typedefcharElemType;typedefstructBTNode{ ElemTypedata; ......
  • java陷阱之遍历数据源数据
    日常我们执行刷数更新避免使用分页偏移,如何涉及到条件变更会丢数据比如满足条件的数据12 34 567根据分页偏移查询当处理第一页12，12处理后不满足条件分页指针偏移到2，这个时候条件12已经不满足了就丢了34数据采用id偏移的方式针对要修改的db场景，还应该避免大事务......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99