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

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

```//
// 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");
printf("\n");
}
}
return 0;
}```

0 条评论

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

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

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

Q：已知一个字符串，求用该字符串的无重复字符的最长子串（有的要求求长度，今天直接求子串）

• ### 解决关系推理，从图网络入手！DeepMind图网络库开源了！

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

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

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

• ### docker虚拟化之订制python环境

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

• ### 盒子的未来：客厅不死，互联网永生

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

• ### 美国「四院院士」为你实力科普深度学习

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