Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 10.01.2013, 01:36
Новичок на форуме
Отправить личное сообщение для JeSa Посмотреть профиль Найти все сообщения от JeSa
 
Регистрация: 02.11.2012
Сообщений: 4

Вопрос с графами
Делаю алгоритм Краскала. Вкратце, я отсортировал все ребра в массиве MAS, в массиве REZ у меня содержатся "цвета" (0..4), по идее, я шагаю по всем элементам MAS, если нахожу в моей матрице такую же длину ребра, как и в MAS, я сравниваю их цвета, и если цвета разные, то включаю это ребро в граф, и меняю цвета. Все должно работать, но блин уже 3 дня сижу, и все равно в некоторых ситуациях он рисует циклы, может кто подскажет?
for(k=0,t=0;k<10;k++)
	{
		for(i=0;i<(N-1);i++) 
				{
					for(j=i+1;j<N;j++) 
					{
						if(D[i][j]==MAS[k])
						{
							if((REZ[i]!=REZ[j])&&(t!=4))
							{
								ctx.moveTo(circles[i].x, circles[i].y);
								ctx.lineTo(circles[j].x,circles[j].y);
								t++;
								for(c=0;c<N;c++)
									{
										if(REZ[c]==REZ[j])
										{
											REZ[c]=REZ[i];
										}
										alert(REZ[c]);
									}
									
								
								
							}
							
						}
						
					}
					
				} 
				
	}
Изображения:
Тип файла: jpg Безымянный.JPG (48.9 Кб, 15 просмотров)
Ответить с цитированием
  #2 (permalink)  
Старый 12.01.2013, 04:37
Новичок на форуме
Отправить личное сообщение для JeSa Посмотреть профиль Найти все сообщения от JeSa
 
Регистрация: 02.11.2012
Сообщений: 4

Все сделал, спасибо за моральную поддержку)
Ответить с цитированием
  #3 (permalink)  
Старый 13.01.2013, 10:29
Аватар для Дзен-трансгуманист
√₋̅₁̅
Отправить личное сообщение для Дзен-трансгуманист Посмотреть профиль Найти все сообщения от Дзен-трансгуманист
 
Регистрация: 18.06.2012
Сообщений: 385

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>
__________________

Гейзенберг, возможно, читал этот тред.

Последний раз редактировалось Дзен-трансгуманист, 13.01.2013 в 10:35.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вопрос по each() и перебору строк таблицы battrack jQuery 1 09.02.2012 13:30
вопрос про возможности JS для рисования и анимации macdack Библиотеки/Тулкиты/Фреймворки 3 15.07.2011 00:13
Вопрос по замыканиям Goodfella Общие вопросы Javascript 20 09.03.2011 01:21
Теоретический вопрос. gods33 (X)HTML/CSS 10 16.12.2010 23:49
Вопрос о циклических ссылках (JavaScript -> Dom -> JavaScipt) BlueIce Events/DOM/Window 10 17.02.2010 21:58