图的存储结构（JS实现）

1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图，一个一维数组存储图中的顶点信息，一个二维数组存储图中的边或弧的信息。

在无向图中，二维矩阵是对称的，而在有向图中，则不是。若边上有权值，那么我们将矩阵值定义为：

//有向图的邻接矩阵存储方式
class Graph{
	constructor(v,vr){
		let len = v.length
		this.vexs = [].slice.apply(v);    //顶点数组
		let arcs = [];
		for (let i=0;i<len;i++){    //初始化矩阵
			arcs[i] = new Array(len);
			for (let j=0;j<len;j++){
				arcs[i][j] = i===j ? 0 : 65535;
			}
		}
		for (let arc of vr){ 
			let v1 = v.indexOf(arc[0]);
			let v2 = v.indexOf(arc[1]);
			arcs[v1][v2] = arc[2] || 1;   //若为无向表，则赋值arcs[v1][v2]
		}
		this.arcs = arcs;
	}

}

let a = new Graph([1,2,3,4],[[1,2,10],[3,4,100],[2,3,-16]]);
console.log(a);

2 邻接表

对于边数相对顶点较少的图，邻接矩阵会造成存储空间的极大浪费，因此我们考虑一种由数组与链表相结合的存储方式，即邻接表。邻接表由两部分组成，其中顶点由一个一维数组存储，每个顶点的所有邻接点用一个链表存储。其中firstedge域指向顶点的第一个邻接点，next域指向下一个邻接点。

在有向图中，很容易知道每个顶点的出度，但是对于入度，则需要遍历整个邻接表，因此还有一种逆邻接表，方便统计每个顶点的入度值。

//有向图的邻接表存储结构
class vex{          //存储顶点
	constructor(value){
		this.data = value;
		this.firstEdge = null;
	}

}

class adjvex{       //链表节点
	constructor(node,weight){
		this.node = node;
		this.weight = weight;
		this.next = null;
	}
}

class Graph{    
	constructor(v,vr){
		let len = v.length;
		let vexs = new Array(len);
		for (let i=0;i<len;i++){
			vexs[i] = new vex(v[i]);
		}
		for (let arc of vr){
			let v1 = v.indexOf(arc[0]);
			let v2 = v.indexOf(arc[1]);
			let adj = vexs[v1].firstEdge;
			if (!adj){    //尾插法
				vexs[v1].firstEdge = new adjvex(v2,arc[2]);   //若为无向表，还需考虑vexs[v2]
			}else{
				while(adj.next){
					if (adj.node === v2){     //若重复定义同一条边，则覆盖权值
						adj.weight = arc[2];
						break;
					}
					adj = adj.next;
				}
				if (adj.node !== v2)
				adj.next = new adjvex(v2,arc[2]);
			}
		}
		this.adjList = vexs;
	}
}

let a = new Graph([1,2,3,4],[[1,2,10],[3,4,100],[2,3,-16],[3,1,8]]);
console.log(a);

3 十字链表

在邻接表中，获取每个节点的入度较麻烦，而在逆邻接表中，获取每个节点的出度则较麻烦，那么我们综合两种表不就完美了？这就是十字链表。十字链表同样由两部分组成，其中顶点由一维数组存储，而边表则为链表。其中，firstin指向当前顶点入边表中第一条入边，firstout指向当前顶点入边表中第一条出边，tailvex为弧尾，taillink指向弧尾相同的边，headvex为弧头，headlink指向弧头相同的边。

class vex{
	constructor(value){
		this.data = value;
		this.firstIn = null;
		this.firstOut = null;
	}

}

class adjvex{
	constructor(tailvex,headvex,weight){
		this.tailvex = tailvex;
		this.headvex = headvex;
		this.weight = weight;
		this.taillink = null;
		this.headlink = null;
	}
}

class Graph{
	constructor(v,vr){
		let len = v.length;
		let vexs = new Array(len);
		let v1 = 0,v2 = 0;
		let adjout = null;
		let adjin = null;
		for (let i=0;i<len;i++){
			vexs[i] = new vex(v[i]);
		}
		for (let arc of vr){
			v1 = v.indexOf(arc[0]);
			v2 = v.indexOf(arc[1]);

			adjout = vexs[v1].firstOut;   //构造邻接表，尾插法
			if (!vexs[v1].firstOut){
				vexs[v1].firstOut = new adjvex(v1,v2,arc[2]);
				adjout = vexs[v1].firstOut;
			}else{
				while(adjout.taillink){
					adjout = adjout.taillink;
				}
				adjout.taillink = new adjvex(v1,v2,arc[2]);
				adjout = adjout.taillink;
			}

			adjin = vexs[v2].firstIn;   //构造逆邻接表，尾插法
			if (!vexs[v2].firstIn){
				vexs[v2].firstIn = adjout;
			}else{
				while(adjin.headlink){
					adjin = adjin.headlink;
				}
				adjin.headlink = adjout;
			}
		}
		this.xList = vexs;	
	}
}

let a = new Graph([1,2,3,4],[[1,2,10],[3,4,100],[2,3,-16],[3,1,8],[1,4,5],[4,3,9]]);
console.log(a);

4 邻接多重表

对于邻接表存储形式的无向图，若删除一条边，则需要对两个顶点进行操作，显得很麻烦。邻接多重表与十字链表结构相似，但是其在边表中每条边都由一个节点表示，该节点具有边弧的头尾顶点以及指向下一条依附于头尾顶点的边。其中firstedge指向依附于当前顶点的第一条边，ivex和jvex为边的两个顶点，ilink指向依附于ivex的边，jlink指向依附于jvex的边。

class vex{
	constructor(value){
		this.data = value;
		this.firstEdge = null;
	}
}

class adjvex{
	constructor(ivex,jvex,weight){
		this.ivex = ivex;
		this.jvex = jvex;
		this.ilink = null;
		this.jlink = null;
		this.weight = weight;
	}
}

class Graph{
	constructor(v,vr){
		let len = v.length;
		let vexs = new Array(len);
		let newvex = null;
		let v1=0,v2=0;
		for (let i=0;i<len;i++){
			vexs[i] = new vex(v[i]);
		}
		for (let arc of vr){
			v1 = v.indexOf(arc[0]);
			v2 = v.indexOf(arc[1]);
			newvex = new adjvex(v1,v2,arc[2]);
			newvex.ilink = vexs[v1].firstEdge;  //这里使用头插法，更简洁
			newvex.jlink = vexs[v2].firstEdge;
			vexs[v1].firstEdge = newvex;
			vexs[v2].firstEdge = newvex;
		}
		this.adjMultiList = vexs;
	}
}

let a = new Graph([1,2,3,4],[[1,2,10],[3,4,100],[2,3,-16],[3,1,8]]);
console.log(a);