<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title>Graphs</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<style>
canvas{
border: solid 1px;
}
</style>
</head>
<body>
<h1>
绘制 图
</h1>
<canvas id="ca1" width="300" height="300">
your browser isn't support the Html5
</canvas>
<script>
// this file aimes to draw a graph directly within a Canvas in HTML5
// use adjencentMatrix to store the Graph
const kinds = {
DG: 0,
DN: 1,
UDG: 2,
UDN: 3
}
function GraphM(name){
// data structure of Graph
this.name = name;
this.graphKind = "";
this.vertexType = "";
this.edgeType = "";
this.vexnum = "";
this.arcnum = "";
this.location = ""; // 为了画图，多加的字段
this.adjVex = function(v){
var index = this.vertexType.indexOf(v);
var result = [];
if (index != -1){
// scan the adjcent vertex
for (let i=0; i<this.vexnum; i++){
if (this.edgeType[index][i] !== Infinity){
result.push(i);
};
}
}else{
console.log("not in");
}
return result;
};
}
function findIndegree(g){
// 求所有顶点的入度
// ------ 邻接矩阵存储 ---------
result = Array(g.vexnum);
for(let i=0; i<g.vexnum; i++){
var temp = 0;
for (let j=0; j<g.vexnum; j++){
if (g.edgeType[j][i] !== Infinity){
temp++;
}
}
result[i] = temp;
}
return result;
};
function topologicalOrder(g){
// 求图的拓扑路径
// ------ 邻接矩阵存储 ---------
var indegree = findIndegree(g); // 得到图的入度情况
var s = []; // 初始化栈以存储入度为0的点
const result = [];
for (let i=0; i<g.vexnum; i++){
if (indegree[i] == 0){
s.push(i);
}
}
var count = 0; // 记录已经输出的点数
while (s.length != 0){
var j = s.pop();
count++;
console.log(g.vertexType[j]); // 输出顶点i
result.push(j);
var adjVexs = g.adjVex(g.vertexType[j]);
for (let i=0; i<adjVexs.length; i++){
if (!(--indegree[adjVexs[i]])){
s.push(adjVexs[i]);
}
}
}
if (count < g.vexnum){
return false;
}else{
return result;
}
};
function criticalPath(g){
// 求图的关键路径
// ------ 邻接矩阵存储 ---------
var result = topologicalOrder(g);
if (!result){
throw Error("图中存在回路，不能求关键路径");
}
var ve = Array(g.vexnum); // vertex early time
var vl = Array(g.vexnum); // vertex late time
// first to solve ve[] and define ve[0] = 0
for (let i=0; i<ve.length;i++){
ve[i] = 0;
}
for (let i=0; i<g.vexnum-1; ++i){
var adjVexs = g.adjVex(g.vertexType[i]);
for (let j=0; j<adjVexs.length; j++){
var k = adjVexs[j];
if (ve[i] + g.edgeType[i][adjVexs[j]]>ve[k]){
ve[k] = ve[i] + g.edgeType[i][adjVexs[j]];
}
}
}
// then initial vl[0 ... n-1] = ve[n-1] and solve the value of each vl
for (let i=0; i<vl.length;++i){
vl[i] = ve[ve.length-1];
}
while (result.length !== 0){
var i = result.pop();
var adjVexs = g.adjVex(g.vertexType[i]);
for (let j=0; j<adjVexs.length; ++j){
var k = adjVexs[j];
if (vl[k] - g.edgeType[i][adjVexs[j]] < vl[i]){
vl[i] = vl[k] - g.edgeType[i][adjVexs[j]];
}
}
}
// 输出关键活动
for (let i=0; i<g.vexnum; i++){
var adjVexs = g.adjVex(g.vertexType[i]);
for (let j of adjVexs){
var dur = g.edgeType[i][j];
var ee = ve[i];
var el = vl[j] - dur;
var tag = (ee == el) ? "*": "";
console.log(`${i} ${j} ${dur} ${ee} ${el} ${tag}`);
}
}
console.log(`ve[] is ${ve}`);
console.log(`vl[] is ${vl}`);
};
function DFS(g){
// 深度优先搜索
// ------ 邻接矩阵存储 ---------
}
var example = new GraphM("example1");
example.graphKind = kinds.DN;
example.vertexType = ["V1", "V2", "V3", "V4", "V5", "V6"];
example.edgeType = [[Infinity, 5, Infinity, 7, Infinity, Infinity],
[Infinity,Infinity,4,Infinity,Infinity,Infinity],
[8,Infinity,Infinity,Infinity,Infinity,9],
[Infinity,Infinity,5,Infinity,Infinity,8],
[Infinity,Infinity,Infinity,5,Infinity,Infinity],
[3,Infinity,Infinity,Infinity,1,Infinity]];
example.vexnum = 6;
example.arcnum = 10;
//example for 拓扑排序
var example2 = new GraphM("example2");
example2.graphKind = kinds.DN;
example2.vertexType = ["V1", "V2", "V3", "V4", "V5"];
example2.edgeType = [[Infinity, 1, Infinity, 1, Infinity],
[Infinity,Infinity,1,1,Infinity],
[Infinity,Infinity,Infinity,Infinity,1],
[Infinity,Infinity,1,Infinity,1],
[Infinity,Infinity,Infinity,Infinity,Infinity]];
example2.vexnum = 5;
example2.arcnum = 7;
// example for 关键路径
var example3 = new GraphM("example3");
example3.graphKind = kinds.DN;
example3.vertexType = ["V1", "V2", "V3", "V4", "V5", "V6"];
example3.edgeType = [[Infinity, 3, 2, Infinity, Infinity, Infinity],
[Infinity,Infinity,Infinity,2,3,Infinity],
[Infinity,Infinity,Infinity,4,Infinity,3],
[Infinity,Infinity,Infinity,Infinity,Infinity,2],
[Infinity,Infinity,Infinity,Infinity,Infinity,1],
[Infinity,Infinity,Infinity,Infinity,Infinity,Infinity]];
example3.vexnum = 6;
example3.arcnum = 8;
// all data perpare...
console.log(example);
// paint
var canvas = document.getElementById("ca1");
var ctx = canvas.getContext("2d"); // 用来获得渲染上下文和它的绘画功能
// ctx.moveTo(150,150);
ctx.strokeStyle = "black";
ctx.beginPath();
ctx.arc(150,150, 30, 0, Math.PI*2, false);
ctx.stroke();
ctx.strokeStyle = "blue";
ctx.beginPath();
ctx.arc(150,150, 100, 0, Math.PI*2, false);
ctx.stroke();
// test 拓扑排序
// if (topologicalOrder(example2)){
// console.log("图中不存在回路。");
// }else{
// console.log("图中存在回路。");
// }
// test criticalPath
criticalPath(example3);
</script>
</body>
</html>
JS操作实现无向网的Prim算法
'use strict';
// MST Prim
const kinds = {
DG: 0,
DN: 1,
UDG: 2,
UDN: 3
}
function GraphM(name){
// data structure of Graph
this.name = name;
this.graphKind = "";
this.vertexType = "";
this.edgeType = "";
this.vexnum = "";
this.arcnum = "";
this.location = ""; // 为了画图，多加的字段
this.adjVex = function(v){
var index = this.vertexType.indexOf(v);
var result = [];
if (index != -1){
// scan the adjcent vertex
for (let i=0; i<this.vexnum; i++){
if (this.edgeType[index][i] !== Infinity){
result.push(i);
};
}
}else{
console.log("not in");
}
return result;
};
}
// example for MST
var example4 = new GraphM("example4");
example4.graphKind = kinds.UDN;
example4.vertexType = ["V1", "V2", "V3", "V4", "V5", "V6"];
example4.edgeType = [[Infinity, 6, 1, 5, Infinity, Infinity],
[6,Infinity,5,Infinity,3,Infinity],
[1,5,Infinity,5,6,4],
[5,Infinity,5,Infinity,Infinity,2],
[Infinity,3,6,Infinity,Infinity,6],
[Infinity,Infinity,4,2,6,Infinity]];
example4.vexnum = 6;
example4.arcnum = 10;
function Prim(g, v){
// 对图G的v顶点开始使用Prim算法得到最小生成树
function data(adjVex, lowcost){
this.adjVex = adjVex;
this.lowcost = lowcost;
}
// 求closedge中权值不为0的最小的序号
function minimum(closedge){
var target = 0;
var low = Infinity;
for (let i=0; i<closedge.length;++i){
if (closedge[i].lowcost !== 0 && closedge[i].lowcost < low){
low = closedge[i].lowcost;
target = i;
}
}
return target;
}
// 初始化closedge
var closedge = new Array(g.vexnum);
for (let i=0; i<closedge.length; ++i){
var temp = new data("", Infinity);
closedge[i] = temp;
}
// 使初始点的closedge[v] = 0;
closedge[v].lowcost = 0;
// first init closedge
for (let i=0; i<g.vexnum; ++i){
var cost = g.edgeType[v][i];
if (cost < closedge[i].lowcost){
closedge[i].lowcost = cost;
closedge[i].adjVex = g.vertexType[v];
}
}
for (let i=1; i<g.vexnum; i++){
var v = minimum(closedge); // new vertex in the set
// print the edge of chosen
console.log(`(${closedge[v].adjVex}, ${g.vertexType[v]})`);
// update the lowcost
closedge[v].lowcost = 0;
for (let i=0; i<g.vexnum; i++){
// update
var cost = g.edgeType[v][i];
if (cost < closedge[i].lowcost){
closedge[i].lowcost = cost;
closedge[i].adjVex = g.vertexType[v];
}
}
}
}
Prim(example4, 0);
最后输出结果如下：
PS C:\Users\Administrator\Desktop> node .\mst.js
(V1, V3)
(V3, V6)
(V6, V4)
(V3, V2)
(V2, V5)
其中例子中的图如下：
图片发自简书App
JavaScript实现Dijkstra算法
'use strict';
const kinds = {
DG: 0,
DN: 1,
UDG: 2,
UDN: 3
}
function GraphM(name){
// data structure of Graph
this.name = name;
this.graphKind = "";
this.vertexType = "";
this.edgeType = "";
this.vexnum = "";
this.arcnum = "";
this.location = ""; // 为了画图，多加的字段
this.adjVex = function(v){
var index = this.vertexType.indexOf(v);
var result = [];
if (index != -1){
// scan the adjcent vertex
for (let i=0; i<this.vexnum; i++){
if (this.edgeType[index][i] !== Infinity){
result.push(i);
};
}
}else{
console.log("not in");
}
return result;
};
}
// example for Dijkstra
var example = new GraphM("example");
example.graphKind = kinds.DN;
example.vertexType = ["V0", "V1", "V2", "V3", "V4", "V5"];
example.edgeType = [[Infinity, Infinity, 10, 30, 100, Infinity],
[Infinity,Infinity,5,Infinity,Infinity,Infinity],
[Infinity,Infinity,Infinity,50,Infinity,Infinity],
[Infinity,Infinity,Infinity,Infinity,Infinity,10],
[Infinity,Infinity,Infinity,20,Infinity,60],
[Infinity,Infinity,Infinity,Infinity,Infinity,Infinity]];
example.vexnum = 6;
example.arcnum = 8;
function dijkstra(g, v0){
// 迪杰斯特拉算法
var distance = new Array(g.vexnum);
var final = new Array(g.vexnum);
var pathMatrix = [];
for (let i=0; i<g.vexnum; i++){
pathMatrix.push(new Array(g.vexnum));
}
for (let v=0; v<g.vexnum; v++){
final[v] = false;
distance[v] = g.edgeType[v0][v];
for (let w=0; w<g.vexnum; w++){
try{
pathMatrix[v][w] = false;
}catch (e) {
console.log(`Error: v is ${v} , w is ${w}`);
}
}
if (distance[v] < Infinity){
pathMatrix[v][v0] = true;
pathMatrix[v][v] = true;
}
}
// console.log(distance);
// console.log(pathMatrix);
// main loop
distance[v0] = 0;
final[v0] = true;
for (let i=1; i<g.vexnum; ++i){
var min = Infinity;
for (let w=0; w<g.vexnum; w++){
if (!final[w]){
if (distance[w] < min){
var v = w;
min = distance[w];
}
}
}
final[v] = true;
for (let w=0; w<g.vexnum; ++w){
if (!final[w] && (min + g.edgeType[v][w]<distance[w])){
distance[w] = min + g.edgeType[v][w];
pathMatrix[w] = pathMatrix[v];
pathMatrix[w][w] = true;
}
}
}
console.log(pathMatrix);
}
function floyd(g){
}
dijkstra(example, 0);
