Javascript-форум - Вопрос с графами

JeSa,
Благодаря этой теме я углубился в вопрос и узнал что такое система непересекающихся множеств. Спасибо. :)
<body>
<input type="button" value="Ещё!" onclick="generate();"><br>
<canvas id="canvas" width="800" height="600"></canvas>
<script type="text/javascript">

function rand ( min, max ) { return Math.random() * ( max - min ) + min; }
function byId ( id ) { return document.getElementById( id ); }

function Graph () {

	this.verts = [];
	this.edges = [];
}

Graph.prototype.insertVert = function ( x, y ) {

	this.verts.push({
		x : x,
		y : y
	});
}

Graph.prototype.insertEdge = function ( vert1Id, vert2Id ) {

	var vert1 = this.verts[ vert1Id ];
	var vert2 = this.verts[ vert2Id ];

	var dx = vert1.x - vert2.x;
	var dy = vert1.y - vert2.y;

	var edge = {
		vert1 : vert1,
		vert2 : vert2,
		weight : Math.sqrt( dx * dx + dy * dy )
	};

	this.edges.push( edge );
}

Graph.prototype.minSpanningTree = function () {

	var edges = [].concat( this.edges );
	var stack = [];

	edges.sort( function ( a, b ) {
		return a.weight - b.weight;
	});

	for ( var i = 0; i < edges.length; i++ ) {

		var vert1 = edges[ i ].vert1;
		var vert2 = edges[ i ].vert2;

		if ( !vert1.hasOwnProperty( 'superset' ) ) {
			vert1.superset = null;
			vert1.rank = 0;
		}
		else {
			while ( vert1.superset ) {
				stack.push( vert1 );
				vert1 = vert1.superset;
			}
			stack.pop();
			while ( stack.length && ( stack.pop().superset = vert1 ) ) {}
		}

		if ( !vert2.hasOwnProperty( 'superset' ) ) {
			vert2.superset = null;
			vert2.rank = 0;
		}
		else {
			while ( vert2.superset ) {
				stack.push( vert2 );
				vert2 = vert2.superset;
			}
			stack.pop();
			while ( stack.length && ( stack.pop().superset = vert2 ) ) {}
		}

		if ( vert1 === vert2 ) {
			edges.splice( i--, 1 );
		}
		else if ( vert1.rank > vert2.rank ) {
			vert2.superset = vert1;
		}
		else {
			vert1.superset = vert2;
			if ( vert1.rank == vert2.rank ) {
				vert2.rank++;
			}
		}
	}

	var verts = this.verts;

	for ( var i = 0; i < verts.length; i++ ) {
		delete verts[ i ].superset;
		delete verts[ i ].rank;
	}

	return edges;
}

function generatePlaneGraph ( width, height, cellSize ) {

	var graph = new Graph();
	var verts = graph.verts;
	var edges = graph.edges;

	var jitter = cellSize * 0.1;

	var cellW = cellSize;
	var cellH = Math.sqrt( 3 ) / 2 * cellSize;

	var hCells = Math.floor( ( width - jitter * 2 ) / cellW );
	var vCells = Math.floor( ( height - jitter * 2 ) / cellH );

	if ( hCells < 1 || vCells < 1 ) {
		return graph;
	}

	var hOffset = ( width - hCells * cellW ) / 2;
	var vOffset = ( height - vCells * cellH ) / 2;

	var rowCells, rowShift;

	for ( var i = 0; i < vCells + 1; i++ ) {

		if ( i % 2 == 0 ) {
			rowCells = hCells;
			rowShift = 0;
		}
		else {
			rowCells = hCells - 1;
			rowShift = cellW * 0.5;
		}

		for ( var j = 0; j < rowCells + 1; j++ ) {
			graph.insertVert(
				hOffset + j * cellW + rand( -jitter, jitter ) + rowShift,
				vOffset + i * cellH + rand( -jitter, jitter )
			);
		}

		for ( var j = 0; j < rowCells; j++ ) {
			graph.insertEdge(
				verts.length - rowCells + j - 1,
				verts.length - rowCells + j
			);
		}

		if ( i > 0 ) {

			if ( i % 2 == 0 ) {

				for ( var j = 0; j < hCells; j++ ) {
					graph.insertEdge(
						verts.length - hCells * 2 + j - 1,
						verts.length - hCells + j - 1
					);
					graph.insertEdge(
						verts.length - hCells * 2 + j - 1,
						verts.length - hCells + j
					);
				}
			}

			else {

				for ( var j = 0; j < hCells; j++ ) {
					graph.insertEdge(
						verts.length - hCells * 2 + j - 1,
						verts.length - hCells + j
					);
					graph.insertEdge(
						verts.length - hCells * 2 + j,
						verts.length - hCells + j
					);
				}
			}
		}
	}

	return graph;
}

function render ( canvas, graph, mstEdges ) {

	var ctx = canvas.getContext( '2d' );
	var verts = graph.verts;
	var edges = graph.edges;

	ctx.clearRect( 0, 0, canvas.width, canvas.height );
	ctx.save();

	ctx.translate( 5, 5 );

	// --------------------------------- graph edges

	ctx.lineWidth = 0.5;
	ctx.strokeStyle = '#ddd';
	ctx.beginPath();

	for ( var i = 0; i < edges.length; i++ ) {

		var edge = edges[ i ];

		ctx.moveTo( edge.vert1.x, edge.vert1.y );
		ctx.lineTo( edge.vert2.x, edge.vert2.y );
	}

	ctx.stroke();

	// --------------------------------- minimum spanning tree edges

	ctx.lineWidth = 1.25;
	ctx.strokeStyle = '#f00';
	ctx.beginPath();

	for ( var i = 0; i < mstEdges.length; i++ ) {

		var edge = mstEdges[ i ];

		ctx.moveTo( edge.vert1.x, edge.vert1.y );
		ctx.lineTo( edge.vert2.x, edge.vert2.y );
	}

	ctx.stroke();

	// --------------------------------- graph vertices phase #1

	ctx.fillStyle = '#fff';
	ctx.beginPath();

	for ( var i = 0; i < verts.length; i++ ) {

		var vert = verts[ i ];

		ctx.moveTo( vert.x + 2.5, vert.y );
		ctx.arc( vert.x, vert.y, 2.5, 0, Math.PI * 2, true );
	}

	ctx.fill();

	// --------------------------------- graph vertices phase #2

	ctx.lineWidth = 1.25;
	ctx.strokeStyle = '#000';
	ctx.stroke();

	ctx.restore();
}

function generate () {

	var canvas = byId( 'canvas' );
	var graph = generatePlaneGraph( canvas.width - 10, canvas.height - 10, 50 );
	var mstEdges = graph.minSpanningTree();

	render( canvas, graph, mstEdges );
};

generate();

</script>
</body>