数据结构与JS也可以成为CP（十）Graph图
我们先来看看图是什么吧～图由边和顶点的集合组成，
名词解释
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）拓扑排序
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读