和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：广度优先搜索（Breadth-First Search，BFS）和深度优先搜索（Depth-First Search，DFS）。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。
在实现算法之前，让我们来更好地理解一下图遍历的思想方法。
图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。
完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。
为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。
广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构。
算法
数据结构
描述
深度优先搜索
栈
通过将顶点存入栈中（在第3章中学习过），顶点是沿着路径被探索的，存在新的相邻顶点就去访问
广度优先搜索
队列
通过将顶点存入队列中（在第4章中学习过），最先入队列的顶点先被探索
当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。
白色：表示该顶点还没有被访问。
灰色：表示该顶点被访问过，但并未被探索过。
黑色：表示该顶点被访问过且被完全探索过。
这就是之前提到的务必访问每个顶点最多两次的原因。
9.4.1 广度优先搜索
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深地访问顶点，如下图所示：
以下是从顶点v开始的广度优先搜索算法所遵循的步骤。
(1) 创建一个队列Q。
(2) 将v 标注为被发现的（灰色），并将v入队列Q。
(3) 如果Q非空，则运行以下步骤：
(a) 将u从Q中出队列；
(b) 将标注u为被发现的（灰色）；
(c) 将u 所有未被访问过的邻点（白色）入队列；
(d) 将u 标注为已被探索的（黑色）。
让我们来实现广度优先搜索算法：
var initializeColor = function{ var color = ; for (var i=0; i<vertices.length; i++){ color[vertices[i]] = 'white'; //{1} } return color;};this.bfs = function(v, callback){ var color = initializeColor, //{2} queue = new Queue; //{3} queue.enqueue(v); //{4} while (!queue.isEmpty){ //{5} var u = queue.dequeue, //{6} neighbors = adjList.get(u); //{7} color[u] = 'grey'; // {8} for (var i=0; i<neighbors.length; i++){ // {9} var w = neighbors[i]; // {10} if (color[w] === 'white'){ // {11} color[w] = 'grey'; // {12} queue.enqueue(w); // {13} } } color[u] = 'black'; // {14} if (callback) { // {15} callback(u); } }}; 广度优先搜索和深度优先搜索都需要标注被访问过的顶点。为此，我们将使用一个辅助数组color。由于当算法开始执行时，所有的顶点颜色都是白色（行{1}），所以我们可以创建一个辅助函数initializeColor，为这两个算法执行此初始化操作。
让我们深入学习广度优先搜索方法的实现。我们要做的第一件事情是用initializeColor函数来将color数组初始化为white（行{2}）。我们还需要声明和创建一个Queue实例（行{3}），它将会存储待访问和待探索的顶点。
照着本章开头解释过的步骤，bfs方法接受一个顶点作为算法的起始点。起始顶点是必要的，我们将此顶点入队列（行{4}）。
如果队列非空（行{5}），我们将通过出队列（行{6}）操作从队列中移除一个顶点，并取得一个包含其所有邻点的邻接表（行{7}）。该顶点将被标注为grey（行{8}），表示我们发现了它（但还未完成对其的探索）。
对于u（行{9}）的每个邻点，我们取得其值（该顶点的名字——行{10}），如果它还未被访问过（颜色为white——行{11}），则将其标注为我们已经发现了它（颜色设置为grey——行{12}），并将这个顶点加入队列中（行{13}），这样当其从队列中出列的时候，我们可以完成对其的探索。
当完成探索该顶点和其相邻顶点后，我们将该顶点标注为已探索过的（颜色设置为black——行{14}）。
我们实现的这个bfs方法也接受一个回调（我们在第8章中遍历树时使用了一个相似的方法）。这个参数是可选的，如果我们传递了回调函数（行{15}），会用到它。
让我们执行下面这段代码来测试一下这个算法：
function printNode(value){ //{16} console.log('Visited vertex: ' + value); //{17}}graph.bfs(myVertices[0], printNode); //{18} 首先，我们声明了一个回调函数（行{16}），它仅仅在浏览器控制台上输出已经被完全探索过的顶点的名字。接着，我们会调用bfs方法，给它传递第一个顶点（A——从本章开头声明的myVertices数组）和回调函数。当我们执行这段代码时，该算法会在浏览器控制台输出下示的结果：
Visited vertex: AVisited vertex: BVisited vertex: CVisited vertex: DVisited vertex: EVisited vertex: FVisited vertex: GVisited vertex: HVisited vertex: I 如你所见，顶点被访问的顺序和本节开头的示意图中所展示的一致。
使用BFS寻找最短路径
到目前为止，我们只展示了BFS算法的工作原理。我们可以用该算法做更多事情，而不只是输出被访问顶点的顺序。例如，考虑如何来解决下面这个问题。
给定一个图G 和源顶点v，找出对每个顶点u，u和v之间最短路径的距离（以边的数量计）。
对于给定顶点v，广度优先算法会访问所有与其距离为1的顶点，接着是距离为2的顶点，以此类推。所以，可以用广度优先算法来解这个问题。我们可以修改
bfs方法以返回给我们一些信息：从v 到u 的距离d[u]；
前溯点pred[u]，用来推导出从v 到其他每个顶点u 的最短路径。
让我们来看看改进过的广度优先方法的实现：
this.BFS = function(v){ var color = initializeColor, queue = new Queue, d = , //{1} pred = ; //{2} queue.enqueue(v); for (var i=0; i<vertices.length; i++){ //{3} d[vertices[i]] = 0; //{4} pred[vertices[i]] = null; //{5} } while (!queue.isEmpty){ var u = queue.dequeue, neighbors = adjList.get(u); color[u] = 'grey'; for (i=0; i<neighbors.length; i++){ var w = neighbors[i]; if (color[w] === 'white'){ color[w] = 'grey'; d[w] = d[u] + 1; //{6} pred[w] = u; //{7} queue.enqueue(w); } } color[u] = 'black'; } return { //{8} distances: d, predecessors: pred };};这个版本的
BFS方法有些什么改变？本章源代码中包含两个
bfs方法：bfs（第一个）和BFS（改进版）。我们还需要声明数组
d（行{1}）来表示距离，以及pred数组来表示前溯点。下一步则是对图中的每一个顶点，用0来初始化数组d（行{4}），用null来初始化数组pred。当我们发现顶点
u的邻点w时，则设置w的前溯点值为u（行{7}）。我们还通过给d[u]加1来设置v和w之间的距离（u是w的前溯点，d[u]的值已经有了）。方法最后返回了一个包含
d和pred的对象（行{8}）。现在，我们可以再次执行
BFS方法，并将其返回值存在一个变量中：var shortestPathA = graph.BFS(myVertices[0]);console.log(shortestPathA);对顶点
A执行BFS方法，以下将会是输出：distances: [A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2 , I: 3],predecessors: [A: null, B: "A", C: "A", D: "A", E: "B", F: "B", G: "C", H: "D", I: "E"]这意味着顶点
A与顶点B、C和D的距离为1；与顶点E、F、G和H的距离为2；与顶点I的距离为3。通过前溯点数组，我们可以用下面这段代码来构建从顶点
A到其他顶点的路径：var fromVertex = myVertices[0]; //{9}for (var i=1; i<myVertices.length; i++){ //{10} var toVertex = myVertices[i], //{11} path = new Stack; //{12} for (var v=toVertex; v!== fromVertex; v=shortestPathA.predecessors[v]) { //{13} path.push(v); //{14} } path.push(fromVertex); //{15} var s = path.pop; //{16} while (!path.isEmpty){ //{17} s += ' - ' + path.pop; //{18} } console.log(s); //{19}}我们用顶点
A作为源顶点（行{9}）。对于每个其他顶点（除了顶点A——行{10}），我们会计算顶点A到它的路径。我们从顶点数组得到toVertex（行{11}），然后会创建一个栈来存储路径值（行{12}）。接着，我们追溯
toVertex到fromVertex的路径（行{13}）。变量v被赋值为其前溯点的值，这样我们能够反向追溯这条路径。将变量v添加到栈中（行{14}）。最后，源顶点也会被添加到栈中，以得到完整路径。这之后，我们创建了一个
s字符串，并将源顶点赋值给它（它是最后一个加入栈中的，所以它是第一个被弹出的项 ——行{16}）。当栈是非空的，我们就从栈中移出一个项并将其拼接到字符串s的后面（行{18}）。最后（行{19}）在控制台上输出路径。执行该代码段，我们会得到如下输出：
A - BA - CA - DA - B - EA - B - FA - C - GA - D - HA - B - E - I这里，我们得到了从顶点
A到图中其他顶点的最短路径（衡量标准是边的数量）。深入学习最短路径算法
本章中的图不是加权图。如果要计算加权图中的最短路径（例如，城市A和城市B之间的最短路径——GPS和Google Maps中用到的算法），广度优先搜索未必合适。
举些例子，Dijkstra算法解决了单源最短路径问题。Bellman-Ford算法解决了边权值为负的单源最短路径问题。A*搜索算法解决了求仅一对顶点间的最短路径问题，它用经验法则来加速搜索过程。Floyd-Warshall算法解决了求所有顶点对间的最短路径这一问题。
如本章开头提到的，图是一个广泛的主题，对最短路径问题及其变种问题，我们有很多的解决方案。但在开始学习这些其他解决方案前，我们需要掌握好图的基本概念，这是本章涵盖的内容。而这些其他解决方案则不会在本章讲述，但你可以自行探索图的奇妙世界。
9.4.2 深度优先搜索
深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点，如下图所示：
深度优先搜索算法不需要一个源顶点。在深度优先搜索算法中，若图中顶点v 未访问，则访问该顶点v。
要访问顶点v，照如下步骤做。
(1) 标注v为被发现的（灰色）。
(2) 对于v 的所有未访问的邻点w，访问顶点w，标注v为已被探索的（黑色）。
如你所见，深度优先搜索的步骤是递归的，这意味着深度优先搜索算法使用栈来存储函数调用（由递归调用所创建的栈）。
让我们来实现一下深度优先算法：
this.dfs = function(callback){ var color = initializeColor; //{1} for (var i=0; i<vertices.length; i++){ //{2} if (color[vertices[i]] === 'white'){ //{3} dfsVisit(vertices[i], color, callback); //{4} } }};var dfsVisit = function(u, color, callback){ color[u] = 'grey'; //{5} if (callback) { //{6} callback(u); } var neighbors = adjList.get(u); //{7} for (var i=0; i<neighbors.length; i++){ //{8} var w = neighbors[i]; //{9} if (color[w] === 'white'){ //{10} dfsVisit(w, color, callback); //{11} } } color[u] = 'black'; //{12}}; 首先，我们创建颜色数组（行{1}），并用值white为图中的每个顶点对其做初始化，广度优先搜索也这么做的。接着，对于图实例中每一个未被访问过的顶点（行{2}和{3}），我们调用私有的递归函数dfsVisit，传递的参数为顶点、颜色数组以及回调函数（行{4}）。
当访问u顶点时，我们标注其为被发现的（grey——行{5}）。如果有callback函数的话（行{6}），则执行该函数输出已访问过的顶点。接下来一步是取得包含顶点u所有邻点的列表（行{7}）。对于顶点u的每一个未被访问过（颜色为white——行{10}和行{8}）的邻点w（行{9}），我们将调用dfsVisit函数，传递w和其他参数（行{11}——添加顶点w入栈，这样接下来就能访问它）。最后，在该顶点和邻点按深度访问之后，我们回退，意思是该顶点已被完全探索，并将其标注为black（行{12}）。
让我们执行下面的代码段来测试一下dfs方法：
graph.dfs(printNode); 输出如下：
Visited vertex: AVisited vertex: BVisited vertex: EVisited vertex: IVisited vertex: FVisited vertex: CVisited vertex: DVisited vertex: GVisited vertex: H 这个顺序和本节开头处示意图所展示的一致。下面这个示意图展示了该算法每一步的执行过程：
在我们示例所用的图中，行{4}只会被执行一次，因为所有其他的顶点都有路径到第一个调用dfsVisit函数的顶点（顶点A）。如果顶点B第一个调用函数，则行{4}将会为其他顶点再执行一次（比如顶点A）。
探索深度优先算法
到目前为止，我们只是展示了深度优先搜索算法的工作原理。我们可以用该算法做更多的事情，而不只是输出被访问顶点的顺序。
对于给定的图G，我们希望深度优先搜索算法遍历图G的所有节点，构建“森林”（有根树的一个集合）以及一组源顶点（根），并输出两个数组：发现时间和完成探索时间。我们可以修改
dfs方法来返回给我们一些信息：顶点u 的发现时间d[u]；
当顶点u 被标注为黑色时，u 的完成探索时间f [u]；
顶点u 的前溯点p[u]。
让我们来看看改进了的
DFS方法的实现：var time = 0; //{1}this.DFS = function{ var color = initializeColor, //{2} d = , f = , p = ; time = 0; for (var i=0; i<vertices.length; i++){ //{3} f[vertices[i]] = 0; d[vertices[i]] = 0; p[vertices[i]] = null; } for (i=0; i<vertices.length; i++){ if (color[vertices[i]] === 'white'){ DFSVisit(vertices[i], color, d, f, p); } } return { //{4} discovery: d, finished: f, predecessors: p };}; var DFSVisit = function(u, color, d, f, p){ console.log('discovered ' + u); color[u] = 'grey'; d[u] = ++time; //{5} var neighbors = adjList.get(u); for (var i=0; i<neighbors.length; i++){ var w = neighbors[i]; if (color[w] === 'white'){ p[w] = u; // {6} DFSVisit(w,color, d, f, p); } } color[u] = 'black'; f[u] = ++time; //{7} console.log('explored ' + u);};我们需要一个变量来要追踪发现时间和完成探索时间（行
{1}）。时间变量不能被作为参数传递，因为非对象的变量不能作为引用传递给其他JavaScript方法（将变量作为引用传递的意思是如果该变量在其他方法内部被修改，新值会在原始变量中反映出来）。接下来，我们声明数组d、f和p（行{2}）。我们需要为图的每一个顶点来初始化这些数组（行{3}）。在这个方法结尾处返回这些值（行{4}），之后我们要用到它们。当一个顶点第一次被发现时，我们追踪其发现时间（行
{5}）。当它是由引自顶点u的边而被发现的，我们追踪它的前溯点（行{6}）。最后，当这个顶点被完全探索后，我们追踪其完成时间（行{7}）。深度优先算法背后的思想是什么？边是从最近发现的顶点u 处被向外探索的。只有连接到未发现的顶点的边被探索了。当u 所有的边都被探索了，该算法回退到u 被发现的地方去探索其他的边。这个过程持续到我们发现了所有从原始顶点能够触及的顶点。如果还留有任何其他未被发现的顶点，我们对新源顶点重复这个过程。重复该算法，直到图中所有的顶点都被探索了。
对于改进过的深度优先搜索，有两点需要我们注意：
时间（
time）变量值的范围只可能在图顶点数量的一倍到两倍之间；对于所有的顶点
u，d[u]<f[u]（意味着，发现时间的值比完成时间的值小，完成时间意思是所有顶点都已经被探索过了）。
在这两个假设下，我们有如下的规则：
1 ≤ d[u] < f[u] ≤ 2|V|
如果对同一个图再跑一遍新的深度优先搜索方法，对图中每个顶点，我们会得到如下的发现/完成时间：
但我们能用这些新信息来做什么呢？来看下一节。
拓扑排序——使用深度优先搜索
给定下图，假定每个顶点都是一个我们需要去执行的任务：
这是一个有向图，意味着任务的执行是有顺序的。例如，任务F 不能在任务A之前执行。注意这个图没有环，意味着这是一个无环图。所以，我们可以说该图是一个有向无环图（DAG）。
当我们需要编排一些任务或步骤的执行顺序时，这称为拓扑排序（topological sorting，英文亦写作topsort或是toposort）。在日常生活中，这个问题在不同情形下都会出现。例如，当我们开始学习一门计算机科学课程，在学习某些知识之前得按顺序完成一些知识储备（你不可以在上算法I前先上算法II）。当我们在开发一个项目时，需要按顺序执行一些步骤，例如，首先我们得从客户那里得到需求，接着开发客户要求的东西，最后交付项目。你不能先交付项目再去收集需求。
拓扑排序只能应用于DAG。那么，如何使用深度优先搜索来实现拓扑排序呢？让我们在本节开头的示意图上执行一下深度优先搜索。
graph = new Graph;myVertices = ['A','B','C','D','E','F'];for (i=0; i<myVertices.length; i++){ graph.addVertex(myVertices[i]);}graph.addEdge('A', 'C');graph.addEdge('A', 'D');graph.addEdge('B', 'D');graph.addEdge('B', 'E');graph.addEdge('C', 'F');graph.addEdge('F', 'E');var result = graph.DFS;这段代码将创建图，添加边，执行改进版本的深度优先搜索算法，并将结果保存到
result变量。下图展示了深度优先搜索算法执行后，该图的发现和完成时间。现在要做的仅仅是以倒序来排序完成时间数组，这便得出了该图的拓扑排序：
B - A - D - C - F - E注意之前的拓扑排序结果仅是多种可能性之一。如果我们稍微修改一下算法，就会有不同的结果，比如下面这个结果也是众多其他可能性中的一个：
A - B - C - D - F - E这也是一个可以接受的结果。