首页 > 其他分享 >DFS

DFS

时间:2022-11-05 14:25:20浏览次数:72  
标签:map 遍历 int DFS 100 include

概念

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.百度

实现思想

无向图通过转换为一个临界矩阵,其实就是遍历临界矩阵

如上图所示,先遍历v1,然后2和3随便,加入是2,现在4和5随机,如果是4,遍历8,接下来是5,然后递归结束依次返回,

最后返回到1,然后遍历3,6和7随便,如果是6,然后就是7,然后依次返回6,3,1,遍历完成

代码实现

#include<iostream>
#include<climites>
#include<string>
using namespace std;
int N;
int map[100][100];//将图转换为临界矩阵,100这是为了简化,这样写不好,浪费空间
int visited[100];//查询是否已经遍历过
void CreateMap(){//建立邻接表
    int n;
    
    cin>>n;//现在输入连通
    for(int i = 0;i<n;i++){
        int p1,p2;
        cin>>p1>>p2;
        map[p1][p2] = 1;
        map[p2][p1] = 1;
    }
}

void DFS(int& n){
    if(visited[n]==0)cout<<n<<" ";//输出访问的节点
    visited[n]=1;
    for(int i = 1;i<N;i++){
        if(visited[i]==0&&map[n][i]==1){
            DFS(i);
        }
    }
}
void dfstraverse(){
    memset(visited,0,N+1);//初始化是否遍历
    for(int i = 1;i<=N;i++){
        if(visited[i]==0){
            DFS(i);
        }
    }
}
int main(){
    cin>>N;//输入图的节点个数
    CreateMap();
    dfstraverse();
}
/*
输入:
8
9
1 2
2 4
2 5
4 8
5 8
1 3
3 6
6 7
7 3
end:
1 2 4 8 5 3 6 7
 */

标签:map,遍历,int,DFS,100,include
From: https://www.cnblogs.com/tsqo/p/16860088.html

相关文章

  • 第2-1-1章 FastDFS分布式文件服务背景及系统架构介绍
    目录1背景1.1为什么需要分布式文件服务1.1.1单机时代1.1.2独立文件服务器1.1.3分布式文件系统1.2什么是FastDFS2系统架构2.1Tracker集群2.2Storage集群2.3Storag......
  • 浅谈 BFS 与 IDDFS
    前记为什么没有\(\text{CSDN}\)和博客园的同步输出了呢?因为博主懒得贴实践代码(实际上\(6\)种搜索的效率对比数据本人是有的),认为\(\text{CSDN}\)和博客园发博文不会......
  • HDFS接口编程 FDFS课堂测试
    调用HDFS文件接口实现对分布式文件系统中文件的访问,如创建、修改、删除等。  这个代码确实是有问题的,这个老师,有点内个  这老师有点不太靠谱啊,是不是写一个截图......
  • 03-分布式文件系统HDFS
    目录​​一,HDFS简介​​​​1,什么是HDFS​​​​2,优缺点​​​​2.1优点​​​​2.2缺点​​​​二,HDFS原理​​​​1,系统架构​​​​1.1角色分工​​​​1.2设计思想......
  • 使用HDFS做一个记事本功能
       pom.xml<?xmlversion="1.0"encoding="UTF-8"?><projectxmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.w3.org/2001/XMLSchem......
  • 详细的最新版fastdfs单机版搭建
    前言目前项目是tomcat单机部署的,图片、视频也是上传到tomcat目录下,关键是此项目的主要内容还就是针对图片、视频的,这让我非常担忧;文件服务器的应用是必然的,而且时间还不......
  • HDFS集成Kerberos的一些问题记录
    参考的两个教程:https://blog.csdn.net/mnasd/article/details/126954062https://blog.csdn.net/weixin_47677170/article/details/125668673 安装hadoop的教程https:......
  • FastDFS收藏起来,现在开始用Minio吧
    MinIo分布式文件存储一、Minio介绍MinIO是全球领先的对象存储先锋,目前在全世界有数百万的用户。高性能,在标准硬件上,读/写速度上高达183GB/秒和171GB/秒,拥有更高的吞吐量和......
  • FastDFS
    FastDFS入门分布式文件系统分布式文件系统(DistributedFileSystem)是一个软件/软件服务器,这个软件可以用来管理文件。但这个软件所管理的文件通常不是在一个服务......
  • hdfs课堂测试
    补充某天的hdfs课堂测试,具体是哪天的,我也不记得了看一下题目  直接上代码了packagecom.rsh.hdfs.test2;importorg.apache.hadoop.conf.Configuration;i......