图：

图有顶点和顶点之间的边组成；
图分为有向图和无向图，还可以根据边长分为有权图和无权图；
我们用临结表来构造图，label表示顶点，动态数组vector中存储从当前顶点出发与当前顶点相通的顶点；
例如，从顶点 0 出发，顶点 0 和 1，2相通，那么我们就令label = 0，vector中存入顶点1，顶点2的图结构即可；

图结构：

struct GraphNode {
    int label;
    vector<GraphNode *> neighbors;  //临接表
    GraphNode(int x) : label(x) {};
};

输入图中所示的图结构，对其进行深度优先搜索：

image.png

递归过程：

对于图中顶点 0 ，若 0 未被访问，判断由 0 出发的路径相通的点中未被访问的点，首先找到了 1 ，打印顶点 1 ，然后继续向下搜索，从 1 出发，找到了尚未被访问的 2 ，打印顶点 2 ，从 2 出发，发现 0 被访问过，return；
顶点 2 中没有相通的顶点了，该层结束，return；
顶点 1 中没有相通的顶点了，该层结束，return；
继续从顶点 0 出发，判断其他的路径相通的点中未被访问的点，找到了 4 ，打印顶点 4 ，顶点 4 中没有相通的顶点了，该层结束，return；
顶点 1 中没有相通的顶点了，该层结束，自此，顶点 0 的递归结束了；
然后继续遍历，依次判断图中剩余的 4 个顶点，顶点 1 被访问过，不递归；顶点 2 被访问过，不递归；顶点 3 未被访问过，打印顶点 3 ，递归，发现不存在 3 出发的路径相通的点中未被访问的点；递归结束；顶点 4 被访问过，不递归；

My Solution(C/C++)

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct GraphNode {
    int label;
    vector<GraphNode *> neighbors;  //临接表
    GraphNode(int x) : label(x) {};
};

class Solution {
public:
    void DFS_graph(GraphNode* node, int visit[]) {
        visit[node->label] = 1;
        printf("%d ", node->label);
        for (int i = 0; i < node->neighbors.size(); i++) {
            if (visit[node->neighbors[i]->label] == 0) {
                DFS_graph(node->neighbors[i], visit);
            }
        }
    }
};

int main() {
    const int MAX_N = 5;  //图的顶点数
    GraphNode *Graph[MAX_N];
    for (int i = 0; i < MAX_N; i++) {
        Graph[i] = new GraphNode(i);  //为图的顶点分配存储空间
    }
    Graph[0]->neighbors.push_back(Graph[1]);  //连线，将顶点0指向顶点1；
    Graph[0]->neighbors.push_back(Graph[4]);
    Graph[1]->neighbors.push_back(Graph[2]);
    Graph[2]->neighbors.push_back(Graph[0]);
    Graph[3]->neighbors.push_back(Graph[2]);
    Graph[3]->neighbors.push_back(Graph[4]);
    Graph[4]->neighbors.push_back(Graph[0]);
    Solution s;
    int visit[MAX_N] = { 0 };
    for (int i = 0; i < MAX_N; i++) {
        if (visit[Graph[i]->label] == 0) {  //只打印没有被搜索访问过的顶点
            printf("从顶点 %d 出发：", Graph[i]->label);
            s.DFS_graph(Graph[i], visit);
            printf("\n");
        }
    }
    for (int i = 0; i < MAX_N; i++) {
        delete Graph[i];
    }
    return 0;
}

结果

从顶点 0 出发：0 1 2 4
从顶点 3 出发：3