JavaScript数据结构13——邻接矩阵与邻接表

图的表示方法有很多种
以下是用邻接矩阵表示图

//图的邻接矩阵表示法
//顶点
function Vertex(name) {
  this.name =name;
}
//邻接矩阵
//maxvex:顶点数
//arcnum:边数
function arc(maxvex,arcnum){
  this.maxvex = maxvex;
  this.arcnum = arcnum;
  this.data = new Array(maxvex);
  for (var i = 0; i < this.data.length; i++) {
    this.data[i] = new Array(maxvex);
    for (var j = 0; j < this.data[i].length; j++) {
      this.data[i][j] = Infinity;
      if(i==j){
        this.data[i][j] = 0;
      }
    }
  }
}
//图
function Mgraph(maxvex,arcnum,vertexs){
  this.arc = new arc(maxvex,arcnum);
  this.vertexs = vertexs;
}
//添加边
Mgraph.prototype.addArc = function(start,end,length){
  var i = this.vertexs.indexOf(start);
  var j = this.vertexs.indexOf(end);
  this.arc.data[i][j] = length;
}
//建造一个
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var v5 = new Vertex('V5');
var vertexs = [v1,v2,v3,v4,v5];
var mgraph = new Mgraph(5,6,vertexs);
 mgraph.addArc(v2,v1,9);
 mgraph.addArc(v2,v3,3);
 mgraph.addArc(v3,v4,5);
 mgraph.addArc(v4,v5,1);
 mgraph.addArc(v1,v5,6);
 mgraph.addArc(v3,v1,2);
 console.info(mgraph);
 console.info(mgraph.arc);

打印

Mgraph {
arc:
arc {
maxvex: 5,
arcnum: 6,
data: [ [Object], [Object], [Object], [Object], [Object] ] },
vertexs:
[ Vertex { name: 'V1' },
Vertex { name: 'V2' },
Vertex { name: 'V3' },
Vertex { name: 'V4' },
Vertex { name: 'V5' } ] }
arc {
maxvex: 5,
arcnum: 6,
data:
[ [ 0, Infinity, Infinity, Infinity, 6 ],
[ 9, 0, 3, Infinity, Infinity ],
[ 2, Infinity, 0, 5, Infinity ],
[ Infinity, Infinity, Infinity, 0, 1 ],
[ Infinity, Infinity, Infinity, Infinity, 0 ] ] }
[Finished in 0.1s]

邻接表的表示方法

//图的邻接表
//顶点
function Vertex(name) {
  this.name =name;
}
//边
function EdgeNode(weight,adjVex){
  this.weight = weight;
  this.adjVex = adjVex;
}
//图
function Graph(vertexs){
  this.vertexs = vertexs;
}
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var edge1 = new EdgeNode(6,v4);
var edge2 = new EdgeNode(9,v0);
var edge3 = new EdgeNode(2,v0);
var edge4 = new EdgeNode(4,v1);
var edge5 = new EdgeNode(3,v2);
var edge6 = new EdgeNode(5,v3);
v0.firstEdge = edge1;
v1.firstEdge = edge2;
v2.firstEdge = edge3;
v3.firstEdge = edge4;
edge2.next = edge5;
edge3.next = edge6;
var vertexs = [v0,v1,v2,v3,v4];
var g = new Graph(vertexs);
console.info(g.vertexs);

输出

[ Vertex {
name: 'V0',
firstEdge: EdgeNode { weight: 6, adjVex: [Object] } },
Vertex {
name: 'V1',
firstEdge: EdgeNode { weight: 9, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V2',
firstEdge: EdgeNode { weight: 2, adjVex: [Object], next: [Object] } },
Vertex {
name: 'V3',
firstEdge: EdgeNode { weight: 4, adjVex: [Object] } },
Vertex { name: 'V4' } ]
[Finished in 0.2s]

十字链表表示

//图的十字链表表示方法
//顶点
function Vertex(name) {
  this.name =name;
}
//边
function EdgeNode(tailVex,headVex){
  this.tailVex = tailVex;
  this.headVex = headVex;
}
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var e1 = new EdgeNode(v0,v3);
var e2 = new EdgeNode(v1,v0);
var e3 = new EdgeNode(v2,v0);
var e4 = new EdgeNode(v1,v2);
var e5 = new EdgeNode(v2,v1);
v0.firstIn = e2;
v0.firseOut = e1;
v1.firstIn = e5;
v1.firseOut = e2;
v2.firstIn = e4;
v2.firseOut = e3;
v3.firstIn = e1;
e2.headLink = e3;
e2.tailLink = e4;
e3.tailLink = e5;
console.info('输出关于V0的所有入边');
console.info(v0.firstIn);

输出

输出关于V0的所有入边
EdgeNode {
tailVex:
Vertex {
name: 'V1',
firstIn: EdgeNode { tailVex: [Object], headVex: [Circular] },
firseOut: [Circular] },
headVex:
Vertex {
name: 'V0',
firstIn: [Circular],
firseOut: EdgeNode { tailVex: [Circular], headVex: [Object] } },
headLink:
EdgeNode {
tailVex: Vertex { name: 'V2', firstIn: [Object], firseOut: [Circular] },
headVex: Vertex { name: 'V0', firstIn: [Circular], firseOut: [Object] },
tailLink: EdgeNode { tailVex: [Object], headVex: [Object] } },
tailLink:
EdgeNode {
tailVex: Vertex { name: 'V1', firstIn: [Object], firseOut: [Circular] },
headVex: Vertex { name: 'V2', firstIn: [Circular], firseOut: [Object] } } }
[Finished in 0.2s]