首页 > 代码库 > 图的深度优先搜索与广度优先搜索
图的深度优先搜索与广度优先搜索
无向图的深度优先搜索与广度优先搜索
#include "stdafx.h" #include<vector> #include<iostream> using namespace std; #define N 9 typedef struct{ int vexnum, arcnum; char vexs[N]; int matirx[N][N]; }graph; graph g; int a[N] = { 0 }; // 初始化图数据 // 0---1---2---3---4---5---6---7---8--- // A---B---C---D---E---F---G---H---I--- void initiate_graph() { // A-B, A-D, A-E g.matirx[0][1] = 1; g.matirx[1][0] = 1; g.matirx[0][3] = 1; g.matirx[3][0] = 1; g.matirx[0][4] = 1; g.matirx[4][0] = 1; // B-C g.matirx[1][2] = 1; g.matirx[2][1] = 1; // C-F g.matirx[2][5] = 1; g.matirx[5][2] = 1; // D-E, D-G g.matirx[3][4] = 1; g.matirx[4][3] = 1; g.matirx[3][6] = 1; g.matirx[6][3] = 1; // E-F, E-H g.matirx[4][5] = 1; g.matirx[5][4] = 1; g.matirx[4][7] = 1; g.matirx[7][4] = 1; // F-H, F-I g.matirx[5][7] = 1; g.matirx[7][5] = 1; g.matirx[5][8] = 1; g.matirx[8][5] = 1; // G-H g.matirx[6][7] = 1; g.matirx[7][6] = 1; // H-I g.matirx[7][8] = 1; g.matirx[8][7] = 1; } //深度优先搜寻,递归实现 void DFS(int k) { a[k] = 1;//标记为已经訪问过 int mm = 0; while (mm < N) { if (g.matirx[k][mm] == 1) { if (a[mm] != 1) { cout << "[" << k << "]" << "[" << mm << "]" << endl; DFS(mm); } } mm++; } } void BFS() { vector<int>vec; vector<int>aa; int k = 0; vec.push_back(0); a[0] = 1; while (vec.size() != 0) { while (k < vec.size()) { cout << vec[k] << endl; int mm = 0; //a[vec[k]] = 1; while (mm < N) { if (g.matirx[vec[k]][mm] == 1) { if (a[mm] != 1) { aa.push_back(mm); a[mm] = 1; } } mm++; } k++; } vec = aa; k = 0; aa.clear(); } } int _tmain(int argc, _TCHAR* argv[]) { initiate_graph(); //DFS(0); BFS(); system("pause"); return 0; }
图的深度优先搜索与广度优先搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。