专栏首页算法其实很好玩Day22-图算法-图的深搜和宽搜

Day22-图算法-图的深搜和宽搜

一 唠嗑

更两篇文章着实有点累,今天偷个懒~

今天先更一下图算法的基础知识-宽搜和深搜

二 问题来了

Q:给定一个图,给出图的深度优先搜索和宽度优先搜索结果。

三 讲一讲

图有邻接矩阵和邻接表两种表示方法,我在下面写的是邻接表。

概念解释

深度优先搜索:

从图中某个顶点V出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发,深度优先搜索遍历图,直至图中所有和V有路径相通,且未被访问的顶点,都被访问到。若此时还有其他顶点未被访问到,就选一个未被访问的顶点,重复上述过程。

宽度优先搜索:(类似于二叉树的层次遍历,利用队列)

从图中某个顶点V出发,在访问了V之后,依次访问V的各个未被访问的邻接点,然后分别从这些邻接点出发,依次访问他们的邻接点。并保证,先被访问的顶点的邻接点,要先于,后被访问的顶点的邻接点被访问。直至图中已被访问的顶点的邻接点,全被访问到。若此时还有其他顶点未被访问到,就选一个未被访问的顶点,重复上述过程。

四 完整代码及注释

//
// Created by renyi on 2019-07-10.
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//图的顶点的数据结构
struct GraphNode{
    int value;
    vector<GraphNode*> neighbors;//相邻节点指针数组
    GraphNode(int v) : value(v) {};
};

//图的深度优先搜索
void depthFirstSearch(GraphNode* root, int visit[]){
    visit[root->value] = 1;//标记已经访问的图的顶点
    printf("%d ", root->value);
    for (int i = 0; i < root->neighbors.size(); i++) {//遍历该顶点相邻的,且未被访问的顶点
        if (visit[root->neighbors[i]->value] != 1){
            depthFirstSearch(root->neighbors[i], visit);
        }
    }
}

//图的宽度优先搜索
void breadthFirstSearch(GraphNode* root, int visit[]){
    queue<GraphNode*> q;
    q.push(root);
    visit[root->value] = 1;

    while (!q.empty()){
        GraphNode* node = q.front();
        q.pop();
        printf("%d ", node->value);
        for (int i = 0; i < node->neighbors.size(); i++) {
            if (visit[node->neighbors[i]->value] != 1){
                q.push(node->neighbors[i]);
                visit[node->neighbors[i]->value] = 1;
            }
        }
    }
}

int main(){
    const int maxN = 5;
    GraphNode* graph[maxN];//建立一个数组graph,存储图的各个顶点
    for (int i = 0; i < maxN; i++) {
        graph[i] = new GraphNode(i);
    }
    //有了5个顶点之后,开始按照配图连接边
    graph[0]->neighbors.push_back(graph[4]);
    graph[0]->neighbors.push_back(graph[2]);
    graph[1]->neighbors.push_back(graph[0]);
    graph[1]->neighbors.push_back(graph[2]);
    graph[2]->neighbors.push_back(graph[3]);
    graph[3]->neighbors.push_back(graph[4]);
    graph[4]->neighbors.push_back(graph[3]);

    int depthVisit[maxN] = {0};//建立数组,标记各个顶点是否被访问
    printf("深度优先搜索的结果是:\n");
    for (int i = 0; i < maxN; i++) {
        if (depthVisit[i] == 0){
            printf("第%d次加入的节点是: %d\n", i, graph[i]->value);
            printf("加入后遍历的结果是:\n");
            depthFirstSearch(graph[i], depthVisit);
            printf("\n");
        }
    }

    int breadthVisit[maxN] = {0};
    printf("宽度优先搜索的结果是:\n");
    for (int i = 0; i < maxN; i++) {
        if (breadthVisit[i] == 0){
            printf("第%d次加入的节点是: %d\n", i, graph[i]->value);
            printf("加入后遍历的结果是:\n");
            breadthFirstSearch(graph[i], breadthVisit);
            printf("\n");
        }
    }
    return 0;
}

运行结果

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

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

原始发表时间:2019-07-10

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day5-线性表-栈-最小栈问题

    而且今天本来按照之前说的,应该更两篇的,但是今天只有一篇盒饭,还不是因为最近需求排的紧,加班加点干活,大哥们见谅

    BUPTrenyi
  • Day8-字符串-最长回文串

    例如:s = “abccccddaa”,可生成的最长回文字符串的长度为9,如“dccaaaccd”,“adccbccda”,“acdcacdca”等都是...

    BUPTrenyi
  • Day11-字符串-无重复字符最长子串

    Q:已知一个字符串,求用该字符串的无重复字符的最长子串(有的要求求长度,今天直接求子串)

    BUPTrenyi
  • 解决关系推理,从图网络入手!DeepMind图网络库开源了!

    DeepMind提出的简单而强大的关系推理网络“graph network”终于开源了!

    新智元
  • 重磅!强化学习进阶,前沿算法及应用梳理一览、有视频

    用户1908973
  • Mockplus演示和分享原型设计的8种方式

    Mockplus目前是国内比较流行的原型设计工具,功能上,相比Axure不算全面和强大,但在不少功能上有它独到之处。 Axure有个比较让人头疼的地方,就是对于...

    奔跑的小鹿
  • docker虚拟化之订制python环境

    前面我们讲了python爬虫用到的工具及模块:phantomjs、beautifulsoup4、selenium、lxml等,如果我们想随时随地用到这个已经搭建...

    py3study
  • 判断无向图是否是一颗树

    DuncanZhou
  • 盒子的未来:客厅不死,互联网永生

    家里的乐视盒子和有线机顶盒的点播套餐纷纷到期,朋友送的百度影棒才刚用没几天,今天百度又发布影棒2了。在外观设计、硬件配置和视频内容支持等方面均有所提升,...

    罗超频道
  • 美国「四院院士」为你实力科普深度学习

    作者:特伦斯 · 谢诺夫斯基,世界十大 AI 科学家之一,美国四大国家学院(国家科学院、国家医学院、国家工程院、国家艺术与科学学院)在世仅 3 位的“四院院士”...

    用户1737318

扫码关注云+社区

领取腾讯云代金券