根据邻接矩阵对图进行深度广度优先搜索

题目：以邻接矩阵给出一张以整数编号为顶点的图，其中0为不相连，1为相连。按深度和广度优先进行遍历，输出全部结果。要求遍历时优先较小的顶点。

#include <deque> #include <iostream> #include <stack> #include <vector> #include <algorithm> using namespace std; class Graph { private: int V; vector<vector<int>> adj; public: Graph(int vertices, int** arr): V(vertices) { adj.resize(V); for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (arr[i][j] == 1) { adj[i].push_back(j); } } sort(adj[i].begin(), adj[i].end()); } } void DFS(int start) { stack<int> s; vector<bool> visited(V, false); //第一个参数是元素个数，第二个是元素的初始值 s.push(start); while (!s.empty()) { int temp = s.top(); s.pop(); if (!visited[temp]) { visited[temp] = true; cout << temp << " "; } for (auto it = adj[temp].rbegin(); it != adj[temp].rend(); it++) { //利用反向迭代器得到里面的数据 if (!visited[*it]) { s.push(*it);//这里必须要用*it是为了解引用迭代器，否则it就只是个位置指示器，而不是一个具体的数据 } } } cout << endl; } void WFS(int start) {//统一在入队的时候进行让visited数组为true deque<int> q; vector<bool> visited(V, false); //初始节点入队并标记 q.push_back(start); visited[start] = true; while (!q.empty()) { int v = q.front(); q.pop_front(); //if(!visited[v]){ cout << v << " "; //这里直接输出，不要再次检查 //} for (auto it = adj[v].begin(); it != adj[v].end(); it++) { if (!visited[*it]) { q.push_back(*it); visited[*it] = true; } } } cout << endl; } //这里需要注意的是，DFS使用的是栈，所以在出栈的时候标记访问，因为是所有元素一下全部进栈 //而WFS用的是队列，没访问完一个元素将他弹出的时候就访问他的neighbor并把他们入队 //所以这里就要求的每次入队的时候就标记访问 }; int main() { int size; cin >> size; int** maze = new int* [size]; for (int i = 0; i < size; i++) { maze[i] = new int[size]; } for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { int a; cin >> a; maze[i][j] = a; } } Graph graph(size, maze); cout << "DFS" << endl; for (int i = 0; i < size; i++) { graph.DFS(i); } cout << "WFS" << endl; for (int i = 0; i < size; i++) { graph.WFS(i); } for (int i = 0; i < size; i++) { delete[] maze[i]; } delete[] maze; }

需要注意两种遍历方法的不同。