<script type="text/javascript">
//图的构建
function vnode() {
this.visited = 0;
this.vertex = 0;
this.arcs = new Array();
}
function G() {
this.adjlist = new Array();
}
//0 1 2 3 4 5
var a = [[0, 7, 8, 0, 0, 9], //
[0, 0, 0, 2, 5, 0], //
[0, 0, 0, 5, 0, 6], //
[0, 0, 0, 0, 9, 0], //
[0, 0, 0, 0, 0, 7], //
[0, 0, 0, 0, 0, 0]]; //
function creategraph() {
var g = new G();
for (i = 0; i < 6; i++) {
g.adjlist[i] = new vnode();
g.adjlist[i].vertex = i;
g.adjlist[i].arcs = (function () {
var b = new Array();
for (j = 0; j < 6; j++)
if (a[i][j]) { b.push(new Number(j)); b[b.length - 1].weight = a[i][j]; }
return b;
})();
}
return g;
}
var s = new Array();
var arcs = new Array();
var e = new Array();
var g = creategraph();
for (i = 0; i < 6; i++) {
for (j = 0; j < g.adjlist[i].arcs.length; j++) {
var b = {};
b.a = i;
b.b = g.adjlist[i].arcs[j];
b.c = g.adjlist[i].arcs[j].weight;
arcs.push(b);
}
}
arcs.sort(function (a, b) {
return a.c - b.c;
})
//for(i=0;i<arcs.length;i++)alert(arcs[i].a+"---"+arcs[i].b);
s.push(g.adjlist[0]);
var flag = 0; var flag1 = 0;
alert(s.length + "---" + g.adjlist.length);
while (s.length < g.adjlist.length) {
flag1 = 0;
for (i = 0; i < arcs.length; i++) {
flag = 0;
if (flag1) break;
for (j = 0; j < s.length; j++) {
if (flag) break;
if (arcs[i].a == s[j].vertex)
for (k = 0; k < s.length; k++) {
if (arcs[i].b == s[k].vertex) { flag = 1; break; }
if (k == (s.length - 1)) {
alert(arcs[i].a + "---" + arcs[i].b);
s.push(g.adjlist[arcs[i].b]);
e.push(arcs[i]); arcs.splice(i, 1);
flag1 = 1;
flag = 1;
break;
}
}
else if (arcs[i].b == s[j].vertex)
for (k = 0; k < s.length; k++) {
if (arcs[i].a == s[k].vertex) { flag = 1; break; }
if (k == (s.length - 1)) {
alert(arcs[i].a + "---" + arcs[i].b);
s.push(g.adjlist[arcs[i].a]);
e.push(arcs[i]); arcs.splice(i, 1);
flag1 = 1;
flag = 1;
break;
}
}
}
}
}
</script>
