专栏首页工科狗和生物喵【图】深度优先算法(DFS)

【图】深度优先算法(DFS)

正文之前

好久没弄C++了,上学期颓废了半学期,这学期开学就搞课程设计快疯了。待会要考试CSP,所以弄点代码储备,待会到了考场说不定能省点功夫!

正文

#include <iostream>
#include<vector>
#define Max 1000;

using namespace std;
struct Graph
{
   int  a[10][10];
};


vector<int> path;
bool visited[10];
int deepth=0;

void DFS(Graph tu,int start)
{
    visited[start]=true;
    for(int i=0;i<10;i++)
    {
        if (visited[i]==false && (tu.a)[start][i]<1000)
        {
            visited[i]=true;
            path[deepth]=i;
            ++deepth;
            DFS(tu,i);
        }
    }
}

// 1 4 1 3 1 5 2 5 2 3 4 5 5 6 5 7 
int main()
{
    Graph tu;
    for(auto &s:tu.a)
        for(auto &x:s)
            x=Max;
    int a,b,s;
    path.push_back(0);
    for(auto &x:visited)
        x=false;
    for(int i=0;i<8;++i)
    {
        cin>>a>>b;
        tu.a[a][b]=tu.a[b][a]=1;
        path.push_back(0);
    }
    path[deepth]=1;
    ++deepth;
    DFS(tu,1);
    cout<<"====~ The Path is ~====="<<endl;
    for(auto &s:path)
        if(s!=0)
            cout<<"\""<<s<<"\""<<" --> ";
    cout<<" | Stop ~ "<<endl;
}

Output:

Last login: Sun Mar 18 11:44:22 on ttys000


= * = * = * = * = * = * = * = * = * = * = * = * = * = * 
✧。٩(ˊᗜˋ)و✧* Hello! Welcome 张照博!!开启愉快的一天吧!
= * = * = * = * = * = * = * = * = * = * = * = * = * = * 


HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/DFS ; exit;
1 4 1 3 1 5 2 5 2 3 4 5 5 6 5 7 
====~ The Path is ~=====
"1" --> "3" --> "2" --> "5" --> "4" --> "6" --> "7" -->  | Stop ~ 
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[进程已完成]

正文之后

祝我好运!发誓这次考试后一定苦学!上学期太飘了。

本文分享自微信公众号 - 工科狗和生物喵(gh_3507b116a1f8),作者:HustWolf

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【小算法】图的遍历之深度优先(DFS)

    其实就是一个权重矩阵,用 1 代表两个结点有连接,0 表示没有连接,这样的表示方式通俗易懂,特别适合稠密图,也就是大多数结点是亮亮连接的情况。

    Frank909
  • 图的深度优先和广度优先算法(DFS递归与非递归)

    阅读本文前,可以先参考本博客 各种基本算法实现小结(四)—— 图及其遍历   和  图的一些基本算法

    阳光岛主
  • 深度优先DFS和广度优先BFS

    之前在HTML渲染过程这篇分享有人在评论问我,这个过程是DFS还是BFS,发现自己好水,确实不知道渲染过程是什么优先,到现在都不知道。

    wade
  • 深度优先搜索(DFS)

    深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只...

    刘开心_1266679
  • 深度优先搜索(DFS)

    里面有着大大小小的文件以及子文件夹,当你需要搜索一个名字为:仙士可.txt的文件时

    仙士可
  • 【python刷题】回溯算法(深度优先搜索DFS)

    结果: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    西西嘛呦
  • 深度优先搜索DFS(一)

    mathor
  • DFS-深度优先搜索—2

    在这一篇博客:http://blog.csdn.net/hacker_zhidian/article/details/54773762中我们通过一道全排列的例子...

    指点
  • 图的遍历之深度优先搜索(DFS)

    深度优先搜索(depth-first search)是对先序遍历(preorder traversal)的推广。”深度优先搜索“,顾名思义就是尽可能深的搜索一个...

    llhthinker

扫码关注云+社区

领取腾讯云代金券