算法:图的深度优先遍历(Depth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。

图的遍历方法一般有两种,第一种是深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS。第二种是《广度优先遍历(Breadth  First Search)》,也有称为广度优先搜索,简称为BFS。我们在《堆栈与深度优先搜索》中已经较为详细地讲述了深度优先搜索的策略,这里不再赘述。我们也可以把图当作一个迷宫,设定一个起始点,走遍所有图的顶点并打上标记,直到访问遍所有的顶点为止。如图7-5-2所示,需要注意的是结点I 是在从A->H,H->回溯->D,D->I 的时候被访问到的,而且我们是从A开始递归进入下面的路径,所以会一直回溯到原点A为止表示遍历结束。

下面只给出邻接矩阵和邻接表存储方式时的图的深度优先遍历的算法代码,没有给出整体可供测试运行的代码,其实只需要再写一个创建图的函数就可以进行整体测试了,可以参考《邻接矩阵创建图》和《邻接表创建图

一、如果我们使用的是邻接矩阵的方式,则代码如下:(改编自《大话数据结构》)

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9

typedef struct
{
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
    int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;

bool visited[MAXVEX];/* 访问标志的数组 */
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph MG, int i)
{
    int j;
    visited[i] = true;
    cout << MG.vexs[i] << ' '; /* 打印顶点,也可以其它操作 */
    for (j = 0; j < MG.numVertexes; j++)
        if (MG.arc[i][j] == 1 && !visited[j])
            DFS(MG, j);/* 对为访问的邻接顶点递归调用 */
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph MG)
{
    int i;
    for (i = 0; i < MG.numVertexes; i++)
        visited[i] = false;/* 初始所有顶点状态都是未访问过状态 */
    for (i = 0; i < MG.numVertexes; i++)
        if (!visited[i])
            DFS(MG, i);/* 对未访问过的顶点调用DFS,若是连通图,只会执行一次*/
}

遍历结果为: A B C D E F G H I (上图所示的图结构)

二、如果我们使用的是邻接表的方式,则代码如下:(改编自《大话数据结构》)

/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
    int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
    int weight;     /* 用于存储权值,对于非网图可以不需要 */
    struct EdgeNode *next; /* 链域,指向下一个邻接点 */
} EdgeNode;

typedef struct VertexNode /* 顶点表结点 */
{
    int in; //结点入度
    char data; /* 顶点域,存储顶点信息 */
    EdgeNode *firstedge;/* 边表头指针 */
} VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges; /* 图中当前顶点数和边数 */
} graphAdjList, *GraphAdjList;

bool visited[MAXVEX];/* 访问标志的数组 */
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    visited[i] = true;
    cout << GL->adjList[i].data << ' '; /* 打印顶点,也可以其它操作 */
    p = GL->adjList[i].firstedge;
    while (p)
    {
        if (!visited[p->adjvex])
            DFS(GL, p->adjvex);/* 对为访问的邻接顶点递归调用 */
        p = p->next;
    }
}
/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
    int i;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = false;/* 初始所有顶点状态都是未访问过状态 */
    for (i = 0; i < GL->numVertexes; i++)
        if (!visited[i])
            DFS(GL, i);/* 对未访问过的顶点调用DFS,若是连通图,只会执行一次*/
}

遍历结果为:A F G H E D I C B (上图所示的图结构)

由结果可以看出,因为我们采用了不同的存储方式,即使使用的是同样的深度优先搜索,遍历的结果也是不同的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

3907
来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

3898
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

4486
来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

3224
来自专栏尾尾部落

[剑指offer] 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

842
来自专栏calmound

HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652 题意:类似3555,0-n之间某个数中包含13,且整个数能被13...

3416
来自专栏Android机动车

数据结构——图相关概念

可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。

1012
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

2125
来自专栏架构之路

Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

3706
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

1933

扫码关注云+社区

领取腾讯云代金券