Может быть, это может вам как-то помочь, я нашел этот сайт, где описаны цветные dfs для ориентированного графа. Так что вы можете исправить перевод dfs на php, который я здесь представляю.
То, что я добавил, это часть для создания леса и другая часть для поиска всех циклов. Поэтому, пожалуйста, примите во внимание, что эти две части моего кода небезопасно считать правильными.
Тот, кто обладает знаниями по теории графов, может быть в состоянии проверить наверняка. В части dfs нет комментариев, потому что это описано уже на ссылочном сайте. Я предлагаю вам взять пример с более чем одним деревом и нарисовать лес (нужно 4 цвета) на бумаге, чтобы лучше понять.
Это код:
<?php
//define the graph
$g = Array(
1 => Array(1,2,3,4,5),
2 => Array(1,2,3,4,5),
3 => Array(1,2,3,4,5),
4 => Array(1,2,3,4,5),
5 => Array(1,2,3,4,5)
);
//add needed attributes on the graph
$G = Array();
foreach($g as $name => $children)
{
$child = Array();
foreach($children as $child_name)//attaching a v letter is not needed, just a preference
$child['v'.$child_name] = null;
$G['v'.$name] =
Array('child'=>$child,
'color'=>'WHITE',//is used in dfs to make visit
'discover_time'=>null,//is used in dfs to classify edges
'finish_time'=>null,//is used in dfs to classify edges
'father'=>null,//is used to walk backward to the start of a cycle
'back_edge'=>null//can be omited, this information can be found with in_array(info, child_array)
);
}
new test($G);
class test
{
private $G = Array();//graph
private $C = Array();//cycles
private $F = Array();//forest
private $L = Array();//loops
private $time_counter = 0;
public function __construct($G)
{
$this->G = $G;
foreach($this->G as $node_name => $foo)
{
if($this->G[$node_name]['color'] === 'WHITE')
$this->DFS_Visit($node_name);
}
$tree =array();
foreach($this->G as $node_name => $data)
{
if($data['father'] === null)//new tree found
{
$this->F[] = $tree;//at first an empty array is inserted
$tree = Array();
$tree[$node_name] = $data;
}
else
$tree[$node_name] = $data;
}
array_shift($this->F);//remove the empty array
$this->F[] = $tree;//add the last tree
$this->find_all_elementary_cycles();
file_put_contents('dump.log', count($this->L)." Loops found: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->L,true)."\n", FILE_APPEND);
file_put_contents('dump.log', count($this->C)." Cycles found: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->C,true)."\n", FILE_APPEND);
file_put_contents('dump.log', count($this->F)." trees found in the Forest: \n", FILE_APPEND);
file_put_contents('dump.log', print_r($this->F,true)."\n", FILE_APPEND);
}
public function find_all_elementary_cycles()
{
/*** For each tree of the forest ***/
foreach($this->F as $tree)
{
/*** Foreach node in the tree ***/
foreach($tree as $node_name => $node)
{
/*** If this tree node connects to some child with backedge
(we hope to avoid some loops with this if) ***/
if ( $node['back_edge'] === true )
/*** Then for every child ***/
foreach ( $node['child'] as $child_name => $edge_classification)
if($edge_classification === 'BACK_EDGE')
$this->back_edge_exploit($node_name, $child_name, $tree);
}
}
}
private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
/*** The input of this function is a back edge, a back edge is defined as follows
-a sender node: which stands lower in the tree and a reciever node which of course stands higher
***/
/*** We want to get rid of loops, so check for a loop ***/
if($back_edge_sender == $back_edge_receiver)
return $this->L[] = $back_edge_sender;//we need to return cause no there is no cycle in a loop
/*** For this backedge sender node the backedge reciever might send a direct edge to the sender ***/
if( isset($this->G[$back_edge_receiver]['child'][$back_edge_sender]) > 0 )
/*** This edge that the reciever sends could be a tree edge, this will happen
-in the case that: the backedge reciever is a father, but it can be a forward edge
-in this case: for the forward edge to exist the backedge reciever does not have to be
-a father onlly: it can also be an ancestore. Whatever of both cases, we have a cycle
***/
if( $this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'TREE_EDGE' or
$this->G[$back_edge_receiver]['child'][$back_edge_sender] === 'FORWARD_EDGE')
$this->C[md5(serialize(Array($back_edge_receiver,$back_edge_sender)))]
= Array($back_edge_receiver,$back_edge_sender);
/*** Until now we have covered, loops, cycles of the kind father->child which occur from one tree edge
- and one: back edge combination, and also we have covered cycles of the kind ancestore->descendant
-which: occur from the combination of one forward edge and one backedge (of course might happen that
-a father: can send to the child both forward and tree edge, all these are covered already).
-what are left: are the cycles of the combination of more than one tree edges and one backedge ***/
$cycle = Array();
attach_node://loops must be handled before this, otherwise goto will loop continously
$cycle[] = $back_edge_sender; //enter the backedge sender
$back_edge_sender = $tree[$back_edge_sender]['father']; //backedge sender becomes his father
if($back_edge_sender !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
goto attach_node;//the loop again
$cycle[] = $back_edge_receiver;
$cycle = array_reverse($cycle);
$this->C[md5(serialize($cycle))] = $cycle;
}
private function DFS_Visit($node_name)
{
$this->G[$node_name]['color'] = 'GRAY';
$this->G[$node_name]['discover_time'] = $this->time_counter++;
foreach($this->G[$node_name]['child'] as $child_name => $foo)
{
if($this->G[$child_name]['color'] === 'BLACK') {#child black
if( $this->G[$node_name]['discover_time'] <
$this->G[$child_name]['discover_time'] ){#time of father smaller
$this->G[$node_name]['child'][$child_name] = 'FORWARD_EDGE';
}
else{#time of child smaller
$this->G[$node_name]['child'][$child_name] = 'CROSS_EDGE';
}
}
elseif($this->G[$child_name]['color'] === 'WHITE'){#child white
$this->G[$node_name]['child'][$child_name] = 'TREE_EDGE';
$this->G[$child_name]['father'] = $node_name;#father in the tree
$this->DFS_Visit($child_name);
}#child discovered but not explored (and father discovered)
elseif($this->G[$child_name]['color'] === 'GRAY'){#child gray
$this->G[$node_name]['child'][$child_name] = 'BACK_EDGE';
$this->G[$node_name]['back_edge'] = true;
}
}//for
$this->G[$node_name]['color'] = 'BLACK';//fully explored
$this->G[$node_name]['finish_time'] = $this->time_counter++;
}
}
?>
И это вывод:
5 Loops found: Array (
[0] => v1
[1] => v2
[2] => v3
[3] => v4
[4] => v5 )
16 Cycles found: Array (
[336adbca89b3389a6f9640047d07f24a] => Array
(
[0] => v1
[1] => v2
)
[d68df8cdbc98d846a591937e9dd9cd70] => Array
(
[0] => v1
[1] => v3
)
[cad6b68c862d3a00a35670db31b76b67] => Array
(
[0] => v1
[1] => v2
[2] => v3
)
[1478f02ce1faa31e122a61a88af498e4] => Array
(
[0] => v2
[1] => v3
)
[0fba8cccc8dceda9fe84c3c93c20d057] => Array
(
[0] => v1
[1] => v4
)
[c995c93b92f8fe8003ea77617760a0c9] => Array
(
[0] => v1
[1] => v2
[2] => v3
[3] => v4
)
[8eae017bc12f0990ab42196af0a1f6a8] => Array
(
[0] => v2
[1] => v4
)
[57c0cc445b506ba6d51dc3c2f06fd926] => Array
(
[0] => v2
[1] => v3
[2] => v4
)
[18cef1bbe850dca5d2d7b6bfea795a23] => Array
(
[0] => v3
[1] => v4
)
[e0bd0c51bfa4df20e4ad922f57f6fe0d] => Array
(
[0] => v1
[1] => v5
)
[6a8b7681b160e28dd86f3f8316bfa16e] => Array
(
[0] => v1
[1] => v2
[2] => v3
[3] => v4
[4] => v5
)
[85e95d3e4dc97e066ec89752946ccf0c] => Array
(
[0] => v2
[1] => v5
)
[633c7cf8df43df75a24c104d9de09ece] => Array
(
[0] => v2
[1] => v3
[2] => v4
[3] => v5
)
[769f8ebc0695f46b5cc3cd444be2938a] => Array
(
[0] => v3
[1] => v5
)
[87028339e63fd6c2687dc5488ba0818c] => Array
(
[0] => v3
[1] => v4
[2] => v5
)
[c2b28cdcef48362ceb0d8fb36a142254] => Array
(
[0] => v4
[1] => v5
)
)
1 trees found in the Forest: Array (
[0] => Array
(
[v1] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => TREE_EDGE
[v3] => FORWARD_EDGE
[v4] => FORWARD_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 0
[finish_time] => 9
[father] =>
[back_edge] => 1
)
[v2] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => TREE_EDGE
[v4] => FORWARD_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 1
[finish_time] => 8
[father] => v1
[back_edge] => 1
)
[v3] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => TREE_EDGE
[v5] => FORWARD_EDGE
)
[color] => BLACK
[discover_time] => 2
[finish_time] => 7
[father] => v2
[back_edge] => 1
)
[v4] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => BACK_EDGE
[v5] => TREE_EDGE
)
[color] => BLACK
[discover_time] => 3
[finish_time] => 6
[father] => v3
[back_edge] => 1
)
[v5] => Array
(
[child] => Array
(
[v1] => BACK_EDGE
[v2] => BACK_EDGE
[v3] => BACK_EDGE
[v4] => BACK_EDGE
[v5] => BACK_EDGE
)
[color] => BLACK
[discover_time] => 4
[finish_time] => 5
[father] => v4
[back_edge] => 1
)
)
)
РЕДАКТИРОВАТЬ 1:
back_edge_exploit метод может быть заменен этой версией:
![private function back_edge_exploit ($back_edge_sender, $back_edge_receiver, $tree)
{
/*** The input of this function is a back edge, a back edge is defined as follows
-a sender node: which stands lower in the tree and a reciever node which of course stands higher
***/
/*** We want to get rid of loops, so check for a loop ***/
if($back_edge_sender == $back_edge_receiver)
return $this->L\[\] = $back_edge_sender;//we need to return cause no there is no cycle in a loop
$cycle = Array();//There is always a cycle which is a combination of tree edges and on backedge
$edges_count = 0; //If the cycle has more than 2 nodes we need to check for forward edge
$backward_runner = $back_edge_sender;//this walks backward up to the start of cycle
attach_node://loops must be handled before this, otherwise goto will loop continously
$edges_count++;
$cycle\[\] = $backward_runner; //enter the backedge sender
$backward_runner = $tree\[$backward_runner\]\['father'\]; //backedge sender becomes his father
if($backward_runner !== $back_edge_receiver) //if backedge sender has not become backedge reciever yet
goto attach_node;//the loop again
else
$cycle\[\] = $backward_runner;
if($edges_count>1 and $this->G\[$back_edge_receiver\]\['child'\]\[$back_edge_sender\] === 'FORWARD_EDGE' )
$this->C\[\] = Array($back_edge_receiver,$back_edge_sender);
$this->C\[\] = array_reverse($cycle); //store the tree edge->back_edge cycle
}][2]
РЕДАКТИРОВАТЬ 2:
Я должен сказать, что я обнаружил, что back_edge_exploit недостаточно, он найдет только циклы, которые сделаны с ребрами дерева и одним задним ребром.
**** Редактировать 3: ****
Хотя это решение считается неполным, оно содержит некоторую полезную информацию, даже сама по себе недостаточность является частью информации, поэтому я думаю, что было бы полезно сохранить ее. Но главная причина, по которой я отредактировал свой ответ, заключается в том, что я нашел другое решение, которое я собираюсь представить ниже.
Но до того, как можно было сделать другое замечание о приближении dfs, существуют циклы, которые могут происходить при прохождении любой допустимой комбинации по всему кресту, вперед, дереву, заднему краю. Таким образом, нахождение фактических циклов, основанных на информации dfs, не является тривиальным (требует дополнительного кода), рассмотрим
этот пример:
Что касается нового решения, оно описано в старой статье 1970 г. Джеймсом К. Тирнаном ( Check this link ) как эффективный алгоритм для нахождения всех элементарных циклов в ориентированном графе. , Также есть современная реализация этого без goto Смотрите здесь
Моя реализация алгоритма элементарного цикла (это название) написана на php и максимально приближена к оригиналу. Я уже проверил это, и это работает. Речь идет о ориентированных графах, если вы объявите свой граф таким образом, что существует направленный цикл v1-> v2-> v3 и другой v2-> v3-> v1, то будут найдены оба цикла, что логично, поскольку он работает с направленным графики.
Что касается неориентированных графов, автор предлагает другие алгоритмы, которые дают лучшее решение, чем модификация алгоритмов, однако это можно сделать, изменив определение графа и добавив дополнительную проверку для циклов длины 2, которые рассматриваются как неориентированные ребра. В частности, ненаправленный цикл из трех узлов будет определен дважды в определении, по одному на ориентацию, например: v1-> v2-> v3 и v3-> v2-> v1. Затем алгоритм найдет его дважды, один раз для каждой ориентации, тогда модификация одной строки в EC3_Circuit_Confirmation может обрезать лишнюю.
Узлы определяются последовательно, можно изменить константу first и список смежности, чтобы первый узел считал от нуля до единицы.
Это код php для алгоритма EC Tiernan:
<?php
define(first,1); //Define how to start counting, from 0 or 1
//nodes are considered to be sequential
$G[first] = Array(2); $G[] = Array(1,3); $G[] = Array(4); $G[] = Array(1);
$N=key(array_slice($G, -1, 1, TRUE));//last key of g
$H=Array(Array());
$P = Array();
$P[first] = first;
$k = first;
$C = Array();//cycles
$L = Array();//loops
########################## ALGORITHM START #############################
#[Path Extension]
EC2_Path_Extension:
//scan adjacency list
foreach($G[$P[$k]] as $j => $adj_node)
//if there is an adjacent node bigger than P[1] and this nodes does not belong in P
if( ($adj_node > $P[first]) and (in_array($adj_node, $P))===false and
(count($H[$P[$k]])>0 and in_array($adj_node, $H[$P[$k]]))===false)
{
$k++;
$P[$k] = $G[$P[$k-1]][$j];
goto EC2_Path_Extension;
}
#[EC3 Circuit Confirmation]
EC3_Circuit_Confirmation:
if(!in_array($P[first], $G[$P[$k]]))
goto EC4_Vertex_Closure;
//otherwise
if (count($P)===1)
$L[] = current($P);
else
$C[] = implode($P);
#[EC4 Vertex Closure]
EC4_Vertex_Closure:
if($k===first)
goto EC5_Advance_Initial_Vertex;
$H[$P[$k]] = Array();
$H[$P[$k-1]][] = $P[$k];
unset($P[$k]);
$k--;
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[first] === $N)
goto EC6_Terminate;
$P[first]++;
$k=first;
//Reset H
$H=Array(Array());
goto EC2_Path_Extension;
EC6_Terminate:
########################### ALGORITHM END ##################################
echo "\n\n".count($L)."$count loops found: ".implode(", ",$L)."\n\n";
echo count($C)." cycles found!\n".implode("\n",$C)."\n";
/*** Original graph found in the paper ***/
//$G[first] = Array(2); $G[] = Array(2,3,4);
//$G[] = Array(5); $G[] = Array(3); $G[] = Array(1);
?>