这一篇介绍图这一数据结构,之后也会放上leetcode的题。
基础代码实现
基础类的定义
顶点类的定义
1 2 3
| function Vertex(label) { this.label = label; }
|
图类的定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| function Graph(v) { this.number_vertice = v; this.number_edge = 0; this.edgeTo = []; this.adj = []; for (var i = 0; i < this.number_vertice; i++) { this.adj[i] = []; this.adj[i].push(""); } this.marked = []; for (var i = 0; i < this.number_vertice; i++) { this.marked[i] = false; } this.addEdge = addEdge; this.showGraph = showGraph; this.depthFirstSearch = depthFirstSearch; this.breadthFirstSearch = breadthFirstSearch; }
|
方法的实现
增加边
1 2 3 4 5
| function addEdge(v, w) { this.adj[v].push(w); this.adj[w].push(v); this.number_edge++; }
|
将图以邻接矩阵的形式进行输出
1 2 3 4 5 6 7 8 9 10 11 12
| function showGraph() { var str = ""; for (var i = 0; i < this.number_vertice; i++) { str = i + "->"; for (var j = 0; j < this.number_vertice; j++) { if (this.adj[i][j] != undefined) { str += this.adj[i][j] + " "; } } debug(str); } }
|
深度优先搜索
1 2 3 4 5 6 7 8 9 10 11
| function depthFirstSearch(v) { this.marked[v] = true; if (this.adj[v] != undefined) { debug("Vertex Visted:" + v); for (var i = 0; i < this.adj[v].length; i++) { if (!this.marked[this.adj[v][i]]) { this.depthFirstSearch(this.adj[v][i]); } } } }
|
广度优先搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| function breadthFirstSearch(vertex) { var queue = []; this.marked[vertex] = true; queue.push(vertex); while (queue.length > 0) { var top = queue.shift(); if (this.adj[top] != undefined) { debug("Vertex Visited:" + top); for (var i = 0; i < this.adj[top].length; i++) { if (!this.marked[this.adj[top][i]]) { this.marked[this.adj[top][i]] = true; queue.push(this.adj[top][i]); } } } } }
|