图论算法（一）深度优先搜索

流程：

1、访问当前节点v，标记为已访问

2、遍历v的所有相邻节点c，然后对所有相邻顶点递归执行该操作，如果当前节点已经没有未访问的相邻顶点，则回溯到v

3、如果还有相邻顶点没有访问，则从该顶点继续开始深度优先搜索，直到所有顶点都被访问

深度优先搜索遍历算法，总是沿着图的某一深度进行遍历，尽可能深的搜索与当前相邻的顶点——如果相邻的顶点都已被访问则回溯到上一层，直至所有顶点都已被访问。

算法的具体实现通过栈来迭代实现：

1 将要访问的第一个顶点 v 入栈，然后首先对其进行访问；

2 将顶点 v 出栈，依次将与顶点 v 相邻且未被访问的顶点 c 压入栈中；

3 重复第一步操作，直至栈为空。

实际也可以递归完成，这样更加简便

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

class Graph {
private:
    int n;  //!< 顶点数量
    vector<int> *edges;  //!< 邻接表
    bool *visited;
public:
    Graph(int input_n) {
        n = input_n;
        edges = new vector<int>[n];
        visited = new bool[n];
        memset(visited, 0, n);
    }

    ~Graph() {
        delete[] edges;
        delete[] visited;
    }

    void insert(int x, int y) {
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    void dfs(int vertex) {
        cout<<vertex<<endl;//访问当前节点vertex
        visited[vertex]=true;//将vertex标记为已访问
        for(int adj_vertex:edges[vertex]){//遍历vertex的所有邻居节点
            if(!visited[adj_vertex]){//如果没有访问
                dfs(adj_vertex);//对邻居节点递归调用
            }
        }
    }
};

int main() {
    int n, m, k;
    cin >> n >> m;
    Graph g(n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        g.insert(x, y);
    }
    cin >> k;
    g.dfs(k);
    return 0;
}