首页 > 代码库 > 广度优先和深度优先搜索算法
广度优先和深度优先搜索算法
#include <iostream>#include <stdlib.h>#include <vector>#include <string>#include <queue>#include <stack>using namespace std;//邻接矩阵显示图void show_graph(vector<vector<int>> &graph){ for (int i = 0; i < graph.size(); i++) { for (int j = 0; j < graph[i].size(); j++) { cout << graph[i][j] << " "; } cout << endl; }}//邻接矩阵----深度优先遍历----递归void DFS_digui(vector<vector<int>> &graph,vector<bool> &visited,int v){ cout << v + 1 << "---->"; visited[v] = true; for (int i = 0; i < graph.size(); i++) { if (graph[v][i] != 0 && visited[i] == false) DFS_digui(graph, visited, i); }}void BFS(vector<vector<int>> &graph, vector<bool> &visited, int v){ queue<int> myqeue; myqeue.push(v); cout << v + 1 << "---->"; visited[v] = true; while (!myqeue.empty()) { int mark = myqeue.front(); myqeue.pop(); for (int i = 0; i < graph[mark].size(); i++) { if (graph[mark][i] != 0 && visited[i] == false) { cout << i + 1 << "---->"; visited[i] = true; myqeue.push(i); } } }}int main(){ int n = 8; vector<vector<int>> graph(n, vector<int> (n)); vector<bool> visited(graph.size()); for (int i = 0; i < visited.size(); i++) { visited[i] = false; } graph[0] = { 0, 1, 1, 0, 0, 0, 0, 0}; graph[1] = { 1, 0, 0, 1, 1, 0, 0, 0 }; graph[2] = { 1, 0, 0, 0, 0, 1, 1, 0 }; graph[3] = { 0, 1, 0, 0, 0, 0, 0, 1 }; graph[4] = { 0, 1, 0, 0, 0, 0, 0, 1 }; graph[5] = { 0, 0, 1, 0, 0, 0, 1, 0 }; graph[6] = { 0, 0, 1, 0, 0, 1, 0, 0 }; graph[7] = { 0, 0, 0, 1, 1, 0, 0, 0 }; show_graph(graph); cout << endl; DFS_digui(graph, visited, 0); cout << endl; for (int i = 0; i < visited.size(); i++) { visited[i] = false; } BFS(graph, visited, 0); system("pause"); return 0;}
广度优先和深度优先搜索算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。