6-1 邻接矩阵存储图的深度优先遍历

这篇具有很好参考价值的文章主要介绍了6-1 邻接矩阵存储图的深度优先遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

6-1 邻接矩阵存储图的深度优先遍历

分数 20
作者 DS课程组
单位 浙江大学

试实现邻接矩阵存储图的深度优先遍历。

函数接口定义:

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );

其中MGraph是邻接矩阵存储的图,定义如下:

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数   */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

函数DFS应从第V个顶点出发递归地深度优先遍历图Graph,遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时,要求按序号递增的顺序。题目保证V是图中的合法顶点。

裁判测试程序样例:

#include <stdio.h>


typedef enum {false, true} bool;

#define MaxVertexNum 10  /* 最大顶点数设为10 */

#define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/

typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */

typedef int WeightType;  /* 边的权值设为整型 */


typedef struct GNode *PtrToGNode;

struct GNode{

    int Nv;  /* 顶点数 */

    int Ne;  /* 边数   */

    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */

};

typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

bool Visited[MaxVertexNum]; /* 顶点的访问标记 */


MGraph CreateGraph(); /* 创建图并且将Visited初始化为false;裁判实现,细节不表 */


void Visit( Vertex V )

{

    printf(" %d", V);

}


void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );



int main()

{

    MGraph G;

    Vertex V;


    G = CreateGraph();

    scanf("%d", &V);

    printf("DFS from %d:", V);

    DFS(G, V, Visit);


    return 0;

}


/* 你的代码将被嵌在这里 */

输入样例:

给定图下
6-1 邻接矩阵存储图的深度优先遍历

5

输出样例:

DFS from 5: 5 1 3 0 2 4 6

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C (gcc)

思路:

深度优先遍历类似于树的先根遍历,是树先根遍历的推广,遍历过程如下:

(1)将图中所有顶点做未访问的标记

(2)任选图中一个未访问过的顶点v作为遍历起点

(3)访问v结点,然后深度优先访问v的第一个未被访问的邻接点w1

(4)再从w1出发深度优先访问w1的第一个未被访问的邻接点w2,…如此下去,直到到达一个所有邻接点都被访问过的顶点为止

(5)然后一次退回,查找前一节点Wi-1是否还有未被访问的邻接点,如果存在则访问此邻接点,并从该节点出发按深度优先的规则访问。如果结点Wi-1不存在尚未被访问的结点,则再退后一步,直到找到所有未被访问的邻接点的顶点

(6)重复上述过程,直到图中所有与v有路径此相连的顶点都被访问过
c
(7)若此时图中仍有未被访问的顶点,则返回到(2);否则遍历结束

递归思路:

1.访问结点V
2.找到v的第一个邻接点w
3.如果邻接点w存在且未被访问,则从w出发深度优先遍历图;否则,结束
4.找顶点v关于w的下一个邻接点,返回(3)文章来源地址https://www.toymoban.com/news/detail-448309.html

AC代码:

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
    Visited[V]=true;//先标记顶点被访问
    Visit(V);//访问顶点的邻接点
    for(int i=0;i<Graph->Nv;i++)
    {
        //遍历顶点的邻接点
        if(Graph->G[V][i]==1&&!(Visited[i]))
            DFS(Graph,i,Visit);//如果邻接点可达并且没有被访问过,那么以邻接点为顶点再次进行深度优先遍历
    }
    return;
}

到了这里,关于6-1 邻接矩阵存储图的深度优先遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图的邻接矩阵存储及遍历操作

    任务描述 本关任务:要求从文件输入顶点和边数据,包括顶点信息、边、权值等,编写程序实现以下功能。 1)构造无向网G的邻接矩阵和顶点集,即图的存储结构为邻接矩阵。 2)输出无向网G的各顶点和邻接矩阵。 3)输出无向网G中顶点H的所有邻接顶点。 测试说明 平台会对

    2024年02月06日
    浏览(40)
  • 深度优先遍历(邻接矩阵,邻接表)

        深度优先遍历也称为深度优先搜索,简称为DFS。     深度优先遍历的思路是从图中某个顶点V出发,访问此顶点,然后从V的未被访问过的邻接点出发深度优先遍历图,直到图中所有与V路径相通的顶点都被访问到     该遍历过程用到递归。     深度优先遍历用到了一个辅

    2024年02月08日
    浏览(43)
  • 图用邻接矩阵实现,深度优先遍历和广度优先遍历

    邻接矩阵的结构体 邻接矩阵图的建立         图的建立有多种实现方式,我这里是从键盘输入顶点数,边条数,并从键盘输入边的关系 图是带有权值的,并且把环的权值赋值为0,两个顶点没有边权值为32767。 查找顶点v,并且返回v的相关信息         通过循环去找顶点,如

    2024年02月04日
    浏览(42)
  • C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

    目录 定义无向图邻接矩阵 构造无向图 打印邻接矩阵 无向图邻接矩阵深度优先遍历(DFS) 无向图邻接矩阵广度优先遍历(BFS) 测试  完整代码 定义无向图邻接矩阵 构造无向图 1、输入总顶点数和总边数 2、依次输入顶点信息存入顶点表 3、 初始化邻接矩阵,使每个权值初始化

    2024年02月06日
    浏览(78)
  • 邻接矩阵储存图实现深度优先遍历(C++)

          目录 基本要求: 图的结构体: 图的构造: 图的深度优先(DFS): 图的打印输出: 完整代码: 测试数据:  运行结果:      通过给出的图的顶点和边的信息,构建无向图的邻接矩阵存储结构。在此基础上,从A顶点开始,对无向图进行深度优先遍历,输出遍历序列

    2024年02月03日
    浏览(44)
  • 【数据结构】图的创建(邻接矩阵,邻接表)以及深度广度遍历(BFS,DFS)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中: 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫 做边的集合。 完全图:在有n个顶点的无向图中,若有n * (n-1)/2条边,

    2024年02月04日
    浏览(42)
  • 利用邻接矩阵进行的深度优先和广度优先遍历(含全部代码+图解)

    目录     --------------------------------------目录------------------------------------------ 图的定义和术语 图的邻接矩阵构建法   深度优先遍历算法(DFS)   广度优先遍历算法 (BFS) 全部代码          图 :G = (V,E) V:顶点的有穷非空集合 E:边的有穷集合          无向图 :每条

    2024年02月05日
    浏览(38)
  • 基于邻接矩阵的有向图的广度优先遍历(BFS)和深度优先遍历(DFS)算法

    概念: 广度优先遍历算法是图的另一种基本遍历算法,其基本思想是尽最大程度辐射能够覆盖的节点,并对其进行访问。 以迷宫为例,广度优先搜索则可以想象成一组人一起朝不同的方向走迷宫,当出现新的未走过的路的时候,可以理解成一个人有分身术,继续从不同的方

    2024年02月06日
    浏览(61)
  • [数据结构]:25-图深度优先遍历(邻接矩阵)(C语言实现)

    目录 前言 已完成内容 图深度优先遍历实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-AdjMatrixFunction.cpp 04-DFS.cpp 结语         此专栏包含408考研数据结构全部内容,除其中使用到C++引用外,全为C语言代码。使用C++引用主要是为了简化指针的使用,避免二重指针的

    2023年04月10日
    浏览(47)
  • 图的数据结构,系统学习图的基本概念、定义和建立,学会邻接矩阵、邻接表以及实现六度空间案例,遍历图的方式——广度、深度访问

    图 :G = (V,E) Graph = (Vertex, Edge) V:顶点(数据元素)的有穷非空集合; E:边的有穷集合。 有向图 :每条边都是有方向的     无向图 :每条边都是无方向的   完全图 :任意两点之间都有一条边相连    无向完全图:n个顶点,n(n-1)/2条边 无向完全图:n个顶点,n(n-1)条边 稀疏

    2023年04月22日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包