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

 


推荐阅读
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率,使用经典的EK(Edmonds-Karp)和Dinic算法进行求解。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
  • 在多线程编程环境中,线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题,Linux提供了线程局部存储(TLS),使每个线程可以拥有独立的变量副本,确保线程间的数据隔离与安全。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
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社区 版权所有