我们先来看看图是什么吧~图由边和顶点的集合组成,
名词解释
1)有向图:一个图的顶点对是有序的。
2)无序图:图是无序的。
3)简单图:没有重复边、重复顶点的圈。
4)强连通:两个顶点之间有路径。
图的实现
下面看看图怎么实现吧!图是由顶点和边组成的,我们首先要实现顶点,然后实现边。
function Graph(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
this.adj[i].push("");
}
this.addEdge = addEdge;
this.showGraph = showGraph;
}
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
function showGraph() {
for (var i = 0; i < this.vertices; ++i) {
putstr(i + " -> ");
for (var j = 0; j < this.vertices; ++j ) {
if (this.adj[i][j] != undefined) {
putstr(this.adj[i][j] + ' ');
}
}
print();
}
}
图的搜索
图的搜索包括深度优先搜索和广度优先搜索。
1)深度优先搜索算法比较简单:访问一个没有访问过的顶点,将它标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。
function dfs(v) {
this.marked[v] = true;
for (var w in this.adj[v]) {
if (!this.marked[w]) {
this.dfs(w);
}
}
}
2)广度优先搜索从第一个顶点开始,尝试访问尽可能靠近它的顶点。本质上,这种搜索在图上是逐层移动的,首先检查最靠近第一个顶点的层,再逐渐向下移动到离起始顶点最远的层。
function bfs(s) {
var queue = []; this.marked[s] = true; queue.push(s); // 添加到队尾
while (queue.length > 0) {
var v = queue.shift(); // 从队首移除 if (v == undefined) {
}
for (var w in this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
图的应用
说了这么多,图能够用在哪里呢?
1)查找最短路径
2)拓扑排序