Здравствуйте, необходимо составить алгоритм поиска всех путей из одной вершины в другую. Каким образом это сделать? Создаю массив $mass($kto,$kuda), где $kto,$kuda тоже массивы. Заполняю матрицу нужными мне элементами. Но как найти все пути из одной, заданной точки, в другую заданную точку?

P.S. уже довольно долго бьюсь над этим вопросом, надеюсь на вашу помощь как в качестве самих идей алгоритмов, так и кода.

kronos1026

как правило выбор алгоритма обхода графа диктуется его приложением. например связи графа могут имет "направление", а могут и не иметь, обязательно ли нужно найти "все пути" или нужно найти "самый короткий", каков ориентировочный размер графа, какое среднее (минимально, максимальное) количество связей может быть у одного узла, важна ли скорость алгоритма или нет и т.п. и т.д.

в самом общем случае поиск "всех путей" - обычный рекурсивный обход с неким ограничивающим доп. условием, исключающим "хождение по кругу". думаю городить сложные массивы вовсе не нужно.

и да, как представлен сам граф? массивом $mass($kto,$kuda), где $kto,$kuda тоже массивы?
проще представить его 2-мя массивами - один - только описание узлов, а второй - только описание всех связей.

Простите, совсем забыл сказать: Граф направленный.

Необходимо найти все пути между двумя вершинами.

Размер графа варьируется (он строится исходя из БД) в данный момент его размерность 20*20

Количество связей между вершинами такое:
1) если есть ребро из 1 в 2, то оно только одино
2) ребер из 1 может быть любое количество в другие вершины, т.е. 1->2 1->3 1->4 и т.д.

Скорость алгоритма не важна.

в таких ограничениях - обычный рекурсивный обход с прерыванием ветки рекурсии, если вдруг достигнута исходная вершина и фиксацией ветки рекурсии в качестве "найденного пути", если достигнута целевая вершина.

можно подробнее со ссылкой или промером кода на данный способ.

достаточно немного допилить вот это

http://ru.wikipedia.org/wiki/%CF%EE%E8%F1%...%F3%E1%E8%ED%F3

хм... в какую сторону дорабатывать данный алгоритм? он ищет путь из вершины в другую вершину (только один)

в процессе написания поста появилась идея, если все получится завтра-послезавтра выложу код. =)

да ладно, че уж :) ушло 40 минут на написание:

имеем например граф: см. внизу

для теста делаем поиск путей от индекса 0 - Маша, до индекса 9 - Стас
Красными стрелками показаны связи, учавствующие в путях (для визуальной проверки).

запускаем:

<?php

$nodes = array (

	0 => 'Маша', 
	1 => 'Петя', 
	2 => 'Ваня', 
	3 => 'Федя', 
	4 => 'Таня', 
	5 => 'Гоша', 
	6 => 'Аня', 
	7 => 'Лида', 
	8 => 'Вова', 
	9 => 'Стас'

);

$links = array (
	
	0 => array (0,1),
	1 => array (0,2),
	2 => array (0,3),
	3 => array (0,4),
	4 => array (0,5),
	5 => array (0,7),
	6 => array (0,8),
	7 => array (0,9),
	8 => array (1,2),
	9 => array (2,3),
	10 => array (2,5),
	11 => array (3,4),
	12 => array (3,7),
	13 => array (4,5),
	14 => array (4,9),
	15 => array (5,9),
	16 => array (6,0),
	17 => array (7,6),
	18 => array (8,5),
	19 => array (8,7),
	20 => array (9,8)

);


$startIndex = 0; //Маша
$finishIndex = 9; //Стас

$way = array();
$wayIndex = -1;

function outWay($type) {
	
	global $nodes, $way, $wayIndex;
	
	$w = $type . ': ';
	
	for ($i = 0; $i <= $wayIndex; $i++) {
		
		if ($i > 0) $arrow = ' -> '; else $arrow = '';
		
		$w .= $arrow . $nodes[ $way[$i] ];
		
	}
	
	echo $w . '<br>';
}

function step($nodeIndex) {
	global $nodes, $links, $way, $wayIndex, $startIndex, $finishIndex;
	
	$wayIndex++;
	$way[$wayIndex] = $nodeIndex;
	
	if ($nodeIndex == $finishIndex) {
	
		outWay('Путь');
		
	} elseif (($nodeIndex != $startIndex) OR ($wayIndex == 0)) {

	
		for ($i = 0; $i < count($links); $i++) {
	
			if ($links[$i][0] == $nodeIndex) {
		
				step($links[$i][1]);
			
			}
		
		}
		
	} else {
		
		outWay('Замыкание');
		
	}
	
	$wayIndex--;

}

step($startIndex);

echo '<br>Выполнено';

?>

результаты: