在DFS中，显然是选最后加入的那一个；在BFS中，是选最先加入的那一个。因为选哪一个其实都可以，按照这样的方式取是最方便的，所以这个问题也就解决了。
到这里就可以开始编码实现了。
编码实现
这里采用《算法(第4版)》中的图处理算法的设计模式：
1. DFS因为DFS是用 “栈” 来控制顺序的，所以有两种写法：一种是显示地使用一个栈，用迭代的方式来实现；另一种是隐式地使用栈，用递归的方式实现。
1 #pragma once 2 #include <stack> 3 #include "Graph.h" 4 using namespace std; 5 6 class DepthFirstSearch { 7 private: 8 bool* mymarked; //在递归写法中：某一个时间截面记录已经访问过的节点 9 //在迭代写法中：某一个时间截面记录已经压过栈的节点 10 //在dfs结束后记录与s节点连通的所有节点 11 12 public: 13 DepthFirstSearch(Graph G, int s) { 14 //初始化辅助数组mymarked 15 mymarked = new bool[G.v()]; 16 for (int i = 0; i < G.v(); i++) 17 mymarked[i] = false; 18 19 //深度优先搜索 20 //dfs_recursion(G, s); 21 dfs_iteration(G, s); 22 } 23 24 void dfs_recursion(Graph G, int s) { 25 //Step1: 访问当前节点 26 mymarked[s] = true; 27 28 //Step2: 对于S的所有邻居，如果没有访问过的话，调用dfs自身来访问它 29 for (int i = 0; i < G.adj(s).size(); i++) { 30 if (mymarked[G.adj(s)[i]] == false) 31 dfs_recursion(G, G.adj(s)[i]); 32 } 33 } 34 35 void dfs_iteration(Graph G, int s) { 36 stack<int> S; 37 38 //Step0: 初始化栈：放入source节点 39 S.push(s); 40 mymarked[s] = true; 41 42 while (!S.empty()) { 43 //Step1: 取出栈顶元素进行访问 44 int cur = S.top(); 45 S.pop(); 46 47 //Step2: 将cur节点的邻居节点中，尚未被访问过的节点压栈 48 for (int i = 0; i < G.adj(cur).size(); i++) { 49 if (mymarked[G.adj(cur)[i]] == false) { 50 mymarked[G.adj(cur)[i]] = true; 51 S.push(G.adj(cur)[i]); 52 } 53 } 54 } 55 } 56 57 bool marked(int w) { 58 return mymarked[w]; 59 } 60 61 };