PTA 邻接矩阵存储图的深度优先遍历

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

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

函数接口定义:

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;
}

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

输入样例:给定图如下

5

输出样例:

DFS from 5: 5 1 3 0 2 4 6
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
    Vertex i;
    Visited[V] = 1;
    Visit(V);
    for(i = 0; i < Graph->Nv ; i++)
    {
        if(Graph->G[V][i] ==1&&!Visited[i])
        {
           DFS(Graph, i, Visit);
        }
    }
    return;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

算法:图的广度优先遍历(Breadth First Search)

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

18810
来自专栏aCloudDeveloper

算法导论第十九章 斐波那契堆

  《算法导论》第二版中在讨论斐波那契堆之前还讨论了二项堆,但是第三版中已经把这块的内容放到思考题中,究极原因我想大概是二项堆只是个引子,目的是为了引出斐波那契...

2138
来自专栏Android先生

快给你的app上锁吧(android图案解锁)

思路 这里又是一个九宫格布局,布局可以参考上一篇快给你的app上锁吧(android数字解锁),只不过这里的九宫格上我们画的是图片(bitmap)。onDraw...

1012
来自专栏开发与安全

数据结构:图的存储结构之邻接表

对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻...

2847
来自专栏决胜机器学习

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(九)——图的定义、存储与两种方式遍历 (原创内容,转载请注明来源,谢谢) 一、定义和术语 1、不同于线性结构和树,图是任意两个...

4557
来自专栏云霄雨霁

有向图----有向图的实现

960
来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】

度度熊保护村庄 Accepts: 13 Submissions: 488 Time Limit: 2000/1000 MS (Java/Others)...

3233
来自专栏算法修养

PAT 甲级 1025 PAT Ranking

1025. PAT Ranking (25) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16000 B 判题...

28510
来自专栏数据结构与算法

24:打印月历

24:打印月历 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定年月,打印当月的月历表。 输入输入为一行两个整数,...

3276
来自专栏恰同学骚年

数据结构基础温故-5.图(中):图的遍历算法

上一篇我们了解了图的基本概念、术语以及存储结构,还对邻接表结构进行了模拟实现。本篇我们来了解一下图的遍历,和树的遍历类似,从图的某一顶点出发访问图中其余顶点,并...

651

扫码关注云+社区