热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

图的深度优先遍历(邻接矩阵,递归,非递归)

参考博客:图的深度优先遍历(递归、非递归;邻接表,邻接矩阵)本篇默认连通图,非连通情况会在邻接表处补上1.邻接矩阵的递归解法#include<stdio.h>#d

参考博客:图的深度优先遍历(递归、非递归;邻接表,邻接矩阵)

本篇默认连通图,非连通情况会在邻接表处补上

 

1.邻接矩阵的递归解法

#include
#define MAX 100

typedef struct
{
    int e[MAX][MAX];
    int ves;
    int edge;
    int book[MAX];//标志判断是否有被访问过 
}MGraph;

void createMGraph(MGraph *G)
{
    int i;
    int j;
    int start;
    int end;

    printf("please input the ves and edge:\n");
    scanf("%d %d",&G->ves,&G->edge);
//初始化
    for(i = 0; i ves; i++)
    {
      for(j = 0; j ves; j++)
        G->e[i][j] = 0;
      G->book[i] = 0;//没被访问过的结点置为0 
    }
//创建邻接矩阵 
    printf("please input the (vi,vj)\n");
    for(i = 0; i edge; i++)
    {
       scanf("%d %d",&start,&end);
      G->e[start][end] = 1;
    }
}

void dfs(MGraph *G,int ves)
{
    int i;

    G->book[ves] = 1;//被访问过的结点置为1 
    printf("%d ",ves);

    for(i = 0; i ves; i++)
       if(G->e[ves][i] != 0 && G->book[i] == 0)
           dfs(G,i);
} 

int main()
{
    MGraph G;
    createMGraph(&G);
    dfs(&G,0);
    return 0;
}
/*
输入样例:
8 18
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 1
3 7
4 1
4 7
5 2
5 6
6 2
6 5
7 3
7 4
*/ 

 

2.邻接矩阵的非递归解法

基本思想:

  • 初始化栈
  • 输出起始顶点,起始顶点改为“已访问”标志,将起始顶点进栈
  • 重复以下操作直至栈空:
    • 去栈顶元素顶点,找到未被访问的邻接结点W
    • 输出W,W改为“已访问”,将W进栈
    • 否则当前顶点退栈
#include
#include
#define MAX 100
using namespace std;

typedef struct
{
    int e[MAX][MAX];
    int ves;
    int edge;
    int book[MAX];//标志判断是否有被访问过 
}MGraph;

void createMGraph(MGraph *G)
{
    int i;
    int j;
    int start;
    int end;

    printf("please input the ves and edge:\n");
    scanf("%d %d",&G->ves,&G->edge);
//初始化
    for(i = 0; i ves; i++)
    {
        for(j = 0; j ves; j++)
            G->e[i][j] = 0;
        G->book[i] = 0;//没被访问过的结点置为0 
    }
//创建邻接矩阵 
    printf("please input the (vi,vj)\n");
    for(i = 0; i edge; i++)
    {
        scanf("%d %d",&start,&end);
        G->e[start][end] = 1;
    }
}

void dfs(MGraph* G,int ves)
{
   stack<int> s;//创建一个栈
   printf("%d ", ves);

   G->book[ves] = 1;//已经访问过结点ves了
   s.push(ves);//入栈

   while(!s.empty())
   {
       int data, i;

       data = s.top();//取top的顶点
       for(i = 0; i ves; i++)
       {
           if(G->e[data][i] != 0 && G->book[i] != 1)
       {
           printf("%d ", i);
           G->book[i] = 1;
           s.push(i);
           break;//深度优先 
       }
       }
       if(i == G->ves)//data相邻的结点都访问结束了,就弹出data
       {
           s.pop();
       }
   }
}

int main()
{
    MGraph G;
    createMGraph(&G);
    dfs(&G,0);
    return 0;
}
/*
输入样例:
8 18
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 1
3 7
4 1
4 7
5 2
5 6
6 2
6 5
7 3
7 4
*/ 

 


推荐阅读
  • 洛谷 P4009 汽车加油行驶问题 解析
    探讨了经典算法题目——汽车加油行驶问题,通过网络流和费用流的视角,深入解析了该问题的解决方案。本文将详细阐述如何利用最短路径算法解决这一问题,并提供详细的代码实现。 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 线段树详解与实现
    本文详细介绍了线段树的基本概念及其在编程竞赛中的应用,并提供了一个具体的线段树实现代码示例。 ... [详细]
  • 视觉Transformer综述
    本文综述了视觉Transformer在计算机视觉领域的应用,从原始Transformer出发,详细介绍了其在图像分类、目标检测和图像分割等任务中的最新进展。文章不仅涵盖了基础的Transformer架构,还深入探讨了各类增强版Transformer模型的设计思路和技术细节。 ... [详细]
  • Hanks博士是一位著名的生物技术专家,他的儿子Hankson对数学有着浓厚的兴趣。最近,Hankson遇到了一个有趣的数学问题,涉及求解特定条件下的正整数x,而不使用传统的辗转相除法。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • hlg_oj_1116_选美大赛这题是最长子序列,然后再求出路径就可以了。开始写的比较乱,用数组什么的,后来用了指针就好办了。现在把代码贴 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本问题涉及在给定的无向图中寻找一个至少包含三个节点的环,该环上的节点不重复,并且环上所有边的长度之和最小。目标是找到并输出这个最小环的具体方案。 ... [详细]
  • 本题要求计算一组正整数的最小公倍数(LCM)。输入包括多组测试数据,每组数据首先给出一个正整数n,随后是n个正整数。 ... [详细]
  • 本文详细介绍了如何在循环双链表的指定位置插入新元素的方法,包括必要的步骤和代码示例。 ... [详细]
  • 编译原理中的语法分析方法探讨
    本文探讨了在编译原理课程中遇到的复杂文法问题,特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略,包括递归下降解析、运算符优先级解析等,并提供了相关示例。 ... [详细]
  • 本文提供了一个使用C语言实现的顺序表区间元素删除功能的完整代码示例。该程序首先初始化一个顺序表,然后根据用户输入的数据进行插入操作,最后根据指定的区间范围删除相应的元素,并输出最终的顺序表。 ... [详细]
  • UVa 1579 - 套娃问题
    本题主要涉及动态规划(DP)的应用,通过计算将前i个套娃合并成多个套娃组所需的最小操作次数来解决问题。具体来说,f(i) 表示前i个套娃合并成多个套娃组所需的操作次数,其计算公式为 f(i) = min(f(j) + dp(j+1, i))。 ... [详细]
  • 探讨了一个包含纯虚函数的C++代码片段,分析了其中的语法错误及逻辑问题,并提出了修正方案。 ... [详细]
author-avatar
手机用户2502903031
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有