热门标签 | 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
*/ 

 


推荐阅读
  • 在HDU 1166敌军布阵问题中,通过运用线段树数据结构,可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解,还能够灵活应对动态变化的战场局势,为实时决策提供支持。 ... [详细]
  • 如何利用正则表达式(regexp)实现高效的模式匹配?本文探讨了正则表达式在编程中的应用,并分析了一个示例程序中存在的问题。通过具体的代码示例,指出该程序在定义和使用正则表达式时的不当之处,旨在帮助读者更好地理解和应用正则表达式技术。 ... [详细]
  • 题目链接:POJ 2777。问题描述:给定一个区域,需要进行多次涂色操作,并在每次操作后查询某个区间内的不同颜色数量。解决方案:由于题目中颜色种类不超过30种,可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记,避免了不必要的节点更新,从而显著提高了算法的效率。此外,该方法还能有效应对大规模数据输入,确保在合理的时间内完成所有操作。 ... [详细]
  • 在晴朗天气条件下,对一种神奇的魔法现象进行了深入分析。该题目为原创,基准时间限制为1秒,空间限制为131072KB,分值20,属于3级难度的算法题。研究发现,这种魔法现象在阳光明媚的环境中表现得尤为显著,进一步探讨了其背后的科学原理和技术实现方法。 ... [详细]
  • 在解决区间相关问题时,我发现自己经常缺乏有效的思维方式,即使是简单的题目也常常需要很长时间才能找到解题思路,而一旦得到提示便能迅速理解。题目要求对一个包含n个元素的数组进行操作,并给出一个参数k,具体任务是…… ... [详细]
  • 探索偶数次幂二项式系数的求和方法及其数学意义 ... [详细]
  • 利用Python进行学生学业表现评估与成绩预测分析
    利用Python进行学生学业表现评估与成绩预测分析 ... [详细]
  • 哈希表(Hash Table)是一种高效的查找算法,与传统的链表和树结构相比,其在查找过程中无需进行逐个元素的比较。本文将深入探讨哈希表的基本原理、应用场景以及优化策略,帮助读者全面理解其在实际开发中的优势和局限性。通过实例分析和代码示例,我们将展示如何有效利用哈希表提高数据处理效率,并解决常见的冲突问题。 ... [详细]
  • 题目链接:http://codeforces.com/gym/101190/attachments题意:在一个共享三轮车站点,某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说,需要设计一种算法,在满足所有用户需求的同时,最小化总等待时间和资源浪费。通过合理的数据结构和算法优化,可以显著提高系统的整体性能和用户体验。 ... [详细]
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 本文详细解析了九度编程平台上的斐波那契数列高效算法挑战(题目编号:1387)。该挑战要求在1秒的时间限制和32兆的内存限制下,设计出高效的斐波那契数列计算方法。通过多种算法的对比和性能分析,本文提供了优化方案,帮助参赛者在限定资源条件下实现高效计算。 ... [详细]
  • 针对NOJ1102黑白图像问题,本文采用深度优先搜索算法进行详细分析与实现。该问题要求在给定的时间限制(普通Java为1000-3000毫秒)和内存限制(65536KByte)内,处理一个n×n的黑白图像。通过对图像的逐像素遍历,利用深度优先搜索算法有效地识别并标记相连的黑色区域,从而实现图像的高效处理。实验结果显示,该方法在多种测试用例中均能稳定达到预期效果,具有较高的准确性和效率。 ... [详细]
  • 利用 Spring BeanUtils 实现 JavaBean 的深度克隆与属性复制 ... [详细]
  • [BZOJ1047] [HAOI2007] 单调队列在理想正方形问题中的应用与优化
    本文探讨了在解决理想正方形问题时,如何利用单调队列进行高效优化。具体而言,给定一个由整数组成的 \(a \times b\) 矩阵,目标是从中找到一个 \(n \times n\) 的子矩阵,使该子矩阵内所有元素的最大值与最小值之差最小。输入部分首先提供三个整数,分别表示矩阵的行数、列数以及子矩阵的边长。通过引入单调队列,算法能够显著提高搜索效率,从而快速找到最优解。 ... [详细]
  • 基址获取与驱动开发:内核中提取ntoskrnl模块的基地址方法解析
    基址获取与驱动开发:内核中提取ntoskrnl模块的基地址方法解析 ... [详细]
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社区 版权所有