圖：
圖有頂點和頂點之間的邊組成；
圖分為有向圖和無向圖吨些，還可以根據(jù)邊長分為有權(quán)圖和無權(quán)圖；
我們用臨結(jié)表來構(gòu)造圖，label表示頂點顽爹，動態(tài)數(shù)組vector中存儲從當(dāng)前頂點出發(fā)與當(dāng)前頂點相通的頂點纤泵；
例如，從頂點 0 出發(fā)镜粤，頂點 0 和 1捏题，2相通，那么我們就令label = 0肉渴，vector中存入頂點1公荧，頂點2的圖結(jié)構(gòu)即可；
圖結(jié)構(gòu)：
struct GraphNode {
int label;
vector<GraphNode *> neighbors; //臨接表
GraphNode(int x) : label(x) {};
};
輸入圖中所示的圖結(jié)構(gòu)同规，對其進(jìn)行深度優(yōu)先搜索：
遞歸過程：
對于圖中頂點 0 循狰，若 0 未被訪問，判斷由 0 出發(fā)的路徑相通的點中未被訪問的點券勺，首先找到了 1 绪钥，打印頂點 1 ，然后繼續(xù)向下搜索关炼，從 1 出發(fā)程腹，找到了尚未被訪問的 2 ，打印頂點 2 儒拂，從 2 出發(fā)寸潦，發(fā)現(xiàn) 0 被訪問過色鸳，return；
頂點 2 中沒有相通的頂點了见转，該層結(jié)束命雀，return；
頂點 1 中沒有相通的頂點了池户，該層結(jié)束咏雌，return；
繼續(xù)從頂點 0 出發(fā)校焦，判斷其他的路徑相通的點中未被訪問的點赊抖，找到了 4 ，打印頂點 4 寨典，頂點 4 中沒有相通的頂點了氛雪，該層結(jié)束，return耸成；
頂點 1 中沒有相通的頂點了报亩，該層結(jié)束，自此井氢，頂點 0 的遞歸結(jié)束了弦追；
然后繼續(xù)遍歷，依次判斷圖中剩余的 4 個頂點花竞，頂點 1 被訪問過劲件，不遞歸；頂點 2 被訪問過约急，不遞歸零远；頂點 3 未被訪問過，打印頂點 3 厌蔽，遞歸牵辣，發(fā)現(xiàn)不存在 3 出發(fā)的路徑相通的點中未被訪問的點；遞歸結(jié)束奴饮；頂點 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; //圖的頂點數(shù)
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 出發(fā)：", Graph[i]->label);
s.DFS_graph(Graph[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++) {
delete Graph[i];
}
return 0;
}
結(jié)果
從頂點 0 出發(fā)：0 1 2 4
從頂點 3 出發(fā)：3
