图的javascript实现

发表于 更新于 分类于

图的概念

图：关于图的概念就大概说一下基本的，图分成有向和无向。图由若干顶点构成，顶点相连成边，边由顶点对组成，(假设有v1，v2两顶点，(v1,v2)即为一条边)每个顶点有权重，对于图的概念可以自行Google，本文着重对图的实现，上两张“图”的例子：

有向图：

无向图：

图的存储

  • 使用邻接表：
    以顶点值为下标，构建数组，元素为与该顶点相连的顶点值，下面例子就是用邻接表存储。假设有顶点v1、v2、v3，且有边(v1, v2)、(v1, v3)、(v2, v3)

    1
    2
    3
    4
    var edges = [];
    edges[v1] = [v2, v3];
    edges[v2] = [v1, v3];
    edges[v3] = [v1, v2];

  • 使用邻接矩阵：
    临界矩阵，简单说是个二维数组，假设有顶点v1、v2，并且v1、v2有边相连，则用邻接矩阵表示为：

    1
    2
    3
    4
    var edges = [];
    edges[v1][v2] = 1;
    // 若无边相连则为
    edges[v1][v2] = 0;

图的javascript实现

下面以上文中的无向图为例

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
function Graph() {
  this.edges = 0;
  this.vertices = [];
}

// 初始化顶点
Graph.prototype.initVertices = function(list) {
  if(toString.call(list) !== '[object Array]') {
    throw new TypeError('please init adj with Array');
  }
  for(item in list) {
    this.vertices[list[item]] = [];
  }
};

// 添加顶点的连结（边）
Graph.prototype.addEdge = function(v1, v2) {
  if(!this.vertices[v1] || !this.vertices[v2]) {
    throw new TypeError('vertex that does not exist！');
  }
  this.vertices[v1].push(v2);
  this.vertices[v2].push(v1);
  this.edges++; 
};


// 输出存储图的邻接表
Graph.prototype.showGraph = function() {
  for(item in this.vertices) {
    console.log(item+': ', this.vertices[item].join(','));
  }
};

var list = [1,2,3,4,5,6];
var graph = new Graph();
graph.initVertices(list);
graph.addEdge(1, 2);
graph.addEdge(1, 4);
graph.addEdge(1, 5);

graph.addEdge(2, 3);
graph.addEdge(2, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 6);

graph.addEdge(3, 5);
graph.addEdge(3, 6);

graph.addEdge(4, 5);

graph.addEdge(5, 6);

graph.showGraph();

PS：图当然是没有那么简单的啦，想了解图自己去看书吧