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 条评论
登录 后参与评论

相关文章

来自专栏技术博客

C#基础知识系列十(集合)

  本节主要是来了解学习集合,以方便在程序编写时,什么地方该选用什么集合,让程序更健壮的运行起来。在学习了解集合之前,首先需要了解一些数据结构方面的知识。下面我...

983
来自专栏后端沉思录

hashCode、equals的使用

hash code、equals是Java用来比较对象是否相等,下面介绍一下自己在工作中对hash code、equals的使用. 首先介绍下String类中的...

742
来自专栏一个会写诗的程序员的博客

Kotlin 语言中的“关键字” Keywords in Kotlin修饰符关键字

但在 kotlin, 有一些关键字在某些情况下可以用作标识符。 在 kotlin 中基本上有四种类型的关键字:

1093
来自专栏xingoo, 一个梦想做发明家的程序员

栈的基本操作就是出栈和入栈,这两个的时间复杂度都是O(1) 数据结构 typedef struct Stack{ int data[MAXSIZE]; ...

1919
来自专栏西安-晁州

js各种继承方式汇总

js中的各种继承实现汇总 首先定义一个父类: function Animal(name) { this.name = name || '动物' this...

3266
来自专栏java达人

如何在Java中避免equals方法的隐藏陷阱(二)

陷阱3:建立在会变化字段上的equals定义 让我们在Point类做一个非常微小的变化 public class Point { private int...

1908
来自专栏Golang语言社区

Go语言实现顺序存储的线性表实例

///////// // 顺序存储线性表 //////// package main import "fmt" const MAXSIZE = 20 //定义数...

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

1008. 水仙花数

1008. 水仙花数 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 输入一个三位数n,判断...

2543
来自专栏黑泽君的专栏

Java中数组高级之各种排序代码

651
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

632

扫码关注云+社区