图和图算法(二)

查找最短路径

图最常见的操作之一就是寻找从一个顶点到另一个顶点的最短路径。

广度优先搜索对应的最短路径

在执行广度优先搜索时，会自动查找从一个顶点到另一个相连顶点的最短路径。例如，要查找从顶点 A 到顶点 D 的最短路径，我们首先会查找从 A 到 D 是否有任何一条单边路径，接着查找两条边的路径，以此类推。这正是广度优先搜索的搜索过程，因此我们可以轻松地修改广度优先搜索算法，找出最短路径。

确定路径

要查找最短路径，需要修改广度优先搜索算法来记录从一个顶点到另一个顶点的路径。这需要对 Graph 类做一些修改。

首先，需要一个数组来保存从一个顶点到下一个顶点的所有边。将这个数组命名为edgeTo 。因为从始至终使用的都是广度优先搜索函数，所以每次都会遇到一个没有标记的顶点，除了对它进行标记外，还会从邻接列表中我们正在探索的那个顶点添加一条边到这个顶点。这是新的 bfs()函数，以及需要添加到 Graph 类的代码：

// 将这行添加到 Graph 类
this.edgeTo = [];

function bfs(s) {
	var queue = [];
	this.marked[s] = true;
	queue.push(s); // 添加到队尾
	while (queue.length > 0) {
	var v = queue.shift(); // 从队首移除
	if (v == undefined) {
		document.write("Visisted vertex: " + v);
	}
		for each(var w in this.adj[v]) {
			if (!this.marked[w]) {
				this.edgeTo[w] = v;
				this.marked[w] = true;
				queue.push(w);
			}
		}
	}
}

其次，现在需要一个函数，用于展示图中连接到不同顶点的路径。函数 pathTo() 创建了一个栈，用来存储与指定顶点有共同边的所有顶点。以下是 pathTo() 函数的代码，以及一个简单的辅助函数：

// 将这两行添加到 Graph 类
this.pathTo = pathTo;
this.hasPathTo = hashPathTo;

function pathTo(v) {
	var source = 0;
	if (!this.hasPathTo(v)) {
		return undefined;
	}

	var path = [];
	for (var i = v; i != source; i = this.edgeTo[i]) {
		path.push(i);
	}

	path.push(s);
	return path;
}

function hashPathTo(v) {
	return this.marked[v];
}

拓扑排序

拓扑排序会对有向图的所有顶点进行排序，使有向边从前面的顶点指向后面的顶点。

拓扑排序算法

拓扑排序算法与深度优先搜索类似。不同的是，拓扑排序算法不会立即输出已访问的顶点，而是访问当前顶点邻接表中的所有相邻顶点，直到这个列表穷尽时，才将当前顶点压入栈中。

拓扑排序算法被拆分为两个函数。第一个函数 topSort() ，会设置排序进程并调用一个辅助函数 topSortHelper() ，然后显示排序好的顶点列表。

主要工作是在递归函数 topSortHelper() 中完成的。这个函数会将当前顶点标记为已访问，然后递归访问当前顶点邻接表中的每个相邻顶点，标记这些顶点为已访问。最后，将当前顶点压入栈。

function topSort() {
	var stack = [];
	var visited = [];
	for (var i = 0; i < this.vertices; i++) {
		visited[i] = false;
	}
	for (var i = 0; i < this.vertices; i++) {
		if (visited[i] == false) {
			this.topSortHelper(i, visited, stack);
		}
	}
	for (var i = 0; i < stack.length; i++) {
		if (stack[i] != undefined && stack[i] != false) {
			document.write(this.vertexList[stack[i]]);
		}
	}
}

function topSortHelper(v, visited, stack) {
	visited[v] = true;
	for each(var w in this.adj[v]) {
		if (!visited[w]) {
			this.topSortHelper(visited[w], visited, stack);
		}
	}
	stack.push(v);
}

最终的Graph类

function Graph(v) {
	this.vertices = v;
	this.vertexList = [];
	this.edges = 0;
	this.adj = [];
	for (var i = 0; i < this.vertices; ++i) {
		this.adj[i] = [];
		this.ajd[i].push("");
	}
	this.addEdge = addEdge;
	this.showGraph = showGraph;
	this.dfs = dfs;
	this.marked = [];
	for (var i = 0; i < this.vertices; ++i) {
		this.marked[i] = false;
	}
	this.bfs = bfs;
	this.edgeTo = [];
	this.hasPathTo = hasPathTo;
	this.topSortHelper = topSortHelper;
	this.topSort = topSort;
}