深度优先遍历
深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如图所示，从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。
代码
/* 基于邻接表实现的无向图类 */
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
/* 顶点类 */
struct Vertex {
int val;
Vertex(int x) : val(x) {
}
};
/* Concatenate a vector with a delim */
template <typename T> string strJoin(const string &delim, const T &vec) {
ostringstream s;
for (const auto &i : vec) {
if (&i != &vec[0]) {
s << delim;
}
s << i;
}
return s.str();
}
/* Get the Vector String object */
template <typename T> string getVectorString(vector<T> &list) {
return "[" + strJoin(", ", list) + "]";
}
/* Print a vector */
template <typename T> void printVector(vector<T> list) {
cout << getVectorString(list) << '\n';
}
/* 输入值列表 vals ，返回顶点列表 vets */
vector<Vertex *> valsToVets(vector<int> vals) {
vector<Vertex *> vets;
for (int val : vals) {
vets.push_back(new Vertex(val));
}
return vets;
}
/* 输入顶点列表 vets ，返回值列表 vals */
vector<int> vetsToVals(vector<Vertex *> vets) {
vector<int> vals;
for (Vertex *vet : vets) {
vals.push_back(vet->val);
}
return vals;
}
class GraphAdjList {
public:
// 邻接表，key：顶点，value：该顶点的所有邻接顶点
unordered_map<Vertex *, vector<Vertex *>> adjList;
/* 在 vector 中删除指定节点 */
void remove(vector<Vertex *> &vec, Vertex *vet) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == vet) {
vec.erase(vec.begin() + i);
break;
}
}
}
/* 构造方法 */
GraphAdjList(const vector<vector<Vertex *>> &edges) {
// 添加所有顶点和边
for (const vector<Vertex *> &edge : edges) {
addVertex(edge[0]);
addVertex(edge[1]);
addEdge(edge[0], edge[1]);
}
}
/* 获取顶点数量 */
int size() {
return adjList.size();
}
/* 添加边 */
void addEdge(Vertex *vet1, Vertex *vet2) {
if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
throw invalid_argument("不存在顶点");
// 添加边 vet1 - vet2
adjList[vet1].push_back(vet2);
adjList[vet2].push_back(vet1);
}
/* 删除边 */
void removeEdge(Vertex *vet1, Vertex *vet2) {
if (!adjList.count(vet1) || !adjList.count(vet2) || vet1 == vet2)
throw invalid_argument("不存在顶点");
// 删除边 vet1 - vet2
remove(adjList[vet1], vet2);
remove(adjList[vet2], vet1);
}
/* 添加顶点 */
void addVertex(Vertex *vet) {
if (adjList.count(vet))
return;
// 在邻接表中添加一个新链表
adjList[vet] = vector<Vertex *>();
}
/* 删除顶点 */
void removeVertex(Vertex *vet) {
if (!adjList.count(vet))
throw invalid_argument("不存在顶点");
// 在邻接表中删除顶点 vet 对应的链表
adjList.erase(vet);
// 遍历其他顶点的链表，删除所有包含 vet 的边
for (auto &adj : adjList) {
remove(adj.second, vet);
}
}
/* 打印邻接表 */
void print() {
cout << "邻接表 =" << endl;
for (auto &adj : adjList) {
const auto &key = adj.first;
const auto &vec = adj.second;
cout << key->val << ": ";
printVector(vetsToVals(vec));
}
}
};
vector<Vertex *> graphBFS(GraphAdjList &graph,Vertex *startVex) {
vector<Vertex *> res;
unordered_set<Vertex *> visited = {startVex};
queue<Vertex *> que;
que.push(startVex);
//以顶点vet 为起点 循环直至访问完所有顶点
while (!que.empty()) {
Vertex *vet = que.front();
que.pop();
res.push_back(vet);
for(auto adjVet: graph.adjList[vet]) {
if(visited.count(adjVet)){
continue;
}
que.push(adjVet);
visited.emplace(adjVet);
}
}
return res;
}
void dfs(GraphAdjList &graph,unordered_set<Vertex *> &visited,vector<Vertex *> &res,Vertex *vex) {
res.push_back(vex);
visited.emplace(vex);
for (Vertex *addVet : graph.adjList[vex]) {
if(visited.count(addVet)) {
continue;
}
dfs(graph, visited, res, addVet);
}
}
/* 深度优先遍历 */
/**
* @brief 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
* @param graph
* @param startVex
* @return vector<Vertex *>
*/
vector<Vertex *> graphDFS(GraphAdjList &graph,Vertex *startVex) {
vector<Vertex *> res;
unordered_set<Vertex *> visited = {startVex};
queue<Vertex *> que;
que.push(startVex);
//以顶点vet 为起点 循环直至访问完所有顶点
while (!que.empty()) {
Vertex *vet = que.front();
que.pop();
res.push_back(vet);
for(auto adjVet: graph.adjList[vet]) {
if(visited.count(adjVet)){
continue;
}
que.push(adjVet);
visited.emplace(adjVet);
}
}
return res;
}
int main() {
/* 初始化无向图 */
vector<Vertex *> v = valsToVets({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
vector<vector<Vertex *>> edges = {{v[0], v[1]}, {v[0], v[3]}, {v[1], v[2]}, {v[1], v[4]},
{v[2], v[5]}, {v[3], v[4]}, {v[3], v[6]}, {v[4], v[5]},
{v[4], v[7]}, {v[5], v[8]}, {v[6], v[7]}, {v[7], v[8]}};
GraphAdjList graph(edges);
cout << "初始化后，图为" <<endl;
graph.print();
/* 广度优先遍历 */
// vector<Vertex *> res = graphBFS(graph, v[0]);
// cout << "\n广度优先遍历（BFS）顶点序列为" << endl;
// printVector(vetsToVals(res));
cout << "深度优先遍历（DFS）顶点序列为" << endl;
vector<Vertex *> res = graphDFS(graph, v[0]);
printVector(vetsToVals(res));
// 释放内存
for (Vertex *vet : v) {
delete vet;
}
return 0;
}输出
初始化后，图为
邻接表 =
8: [5, 7]
7: [4, 6, 8]
6: [3, 7]
1: [0, 2, 4]
4: [1, 3, 5, 7]
5: [2, 4, 8]
0: [1, 3]
3: [0, 4, 6]
2: [1, 5]
深度优先遍历（DFS）顶点序列为
[0, 1, 3, 2, 4, 6, 5, 7, 8]
