Реализации алгоритмов/Поиск в глубину
Внешний вид
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
Java
[править]С++
[править]Go
[править]package main
const (
// Start - стартовая вершина
Start = 3
// Vert - кол-во вершин
Vert = 7
)
var (
used = make(map[int]bool)
graph = [Vert][]int{
{1, 2},
{0, 2},
{0, 1, 3, 4, 5},
{2},
{2, 6},
{2, 6},
{4, 5},
}
)
func main() {
dfs(Start)
}
func dfs(start int) {
used[start] = true
for _, n := range graph {
for _, v := range n {
if _, ok := used[v]; !ok {
dfs(v)
}
}
}
}
Pascal
[править]const
MAX_N = 10;
var
graph: array [1..MAX_N, 1..MAX_N] of boolean; // массив для определения графа
visited: array [1..MAX_N] of boolean;
procedure dfs(v: integer);
var
i: integer;
begin
visited[v] := true;
for i := 1 to MAX_N do
if graph[v, i] and not visited[i] then
dfs(i);
end;
Python
[править]# 1. Матрица связности.
matrix_of_coherence = [[0, 1, 0], # матрица связности
[1, 0, 0],
[0, 0, 0]]
ex = set() # множество посещенных вершин
def dfs(node): # start - начальная вершина
ex.add(node)
for coherence in range(len(matrix_of_coherence)):
if matrix_of_coherence[node][coherence] == 1 and coherence not in ex:
print(coherence)
dfs(coherence)
# 2. Список смежности.'''Полужирное начертание'''
list_of_adjacencies = [[1, 3], [0], [3], [2, 0], []]
vladimir = [False for enotu in range(len(list_of_adjacencies))]
def dfs(vovanissimo):
vladimir[vovanissimo] = True
for vovochka in list_of_adjacencies[vovanissimo]:
if not vladimir[vovochka]:
dfs(vovochka)
for cotiki in range(len(list_of_adjacencies)):
if not vladimir[cotiki]:
dfs(cotiki)
# Так и не смог исправить. Функции перекрывают друг друга. Исправил только названия переменных которые понял.
PHP
[править]$graph = array( 'A' => array('B','C','D','Z'),
'B' => array('A','E'),
'C' => array('A','F','G'),
'D' => array('A','I'),
'E' => array('B' ,'H'),
'F' => array('C','J'),
'G' => array('C'),
'H' => array('E','Z'),
'I' => array('D'),
'J' => array('J'),
'Z' => array('A','H'));
function dfs( $graph , $startNode = 'A' )
{
global $visited;
$visited[] = $startNode;
foreach($graph[$startNode] as $index => $vertex)
{
if( !in_array( $vertex , $visited ) )
dfs( $graph , $vertex );
}
}
Scala
[править]object DFS extends App {
val graph = Map(
1 -> List(2, 3),
2 -> List(3, 4, 8),
3 -> List(4),
4 -> List(5, 6),
5 -> List(6, 7, 9),
8 -> List(10))
type Graph[T] = Map[T, List[T]]
//Рекурсивный обход, возвращаюший множество вершин графа
def dfsTraverseRec[T, R](startNode: T, g: Graph[T], visited: Set[T])(process: T => R): Set[T] = { //R
if (visited.contains(startNode)) visited //Если узел посещен, то ничего не добавляем во множество обойденных
else {
process(startNode)
g.getOrElse(startNode, Nil).foldLeft(visited + startNode)((allVisited, n) =>
visited ++ dfsTraverseRec(n, g, allVisited)(process))
}
}
val edges = dfsTraverseRec(graph.keys.min, graph, Set.empty)(x => println(s"processed vertex: $x"))
//edges -> Все обойденные узлы
//Итеративный Обход через стэк, не возвращает ничего
def dfsTraverseIter[T, R](startNode: T, g: Graph[T])(process: T => R): Unit = {
Stream.iterate((List(startNode), Set[T](startNode))) {
case (s, visited) =>
val vertex = s.head
val newStack = g.getOrElse(vertex, Nil).filterNot(visited.contains) ++ s.tail
val newVisited = g.getOrElse(vertex, Nil).toSet ++ visited
(newStack, newVisited)
}
.takeWhile(_._1.nonEmpty)
.foreach(x => process(x._1.head))
}
dfsTraverseIter(graph.keys.min, graph)(x => println(s"processed vertex: $x"))
//Оба алгоритма обходят один и тот же граф в глубину, но в разном порядке
}
JavaScript
[править]// A
// / \
// B C
// / \ / \
// D E F G
let graph = {}
graph["A"] = ['B', 'C']
graph["B"] = ['D', 'E']
graph["C"] = ['F', 'G']
graph["D"] = []
graph["E"] = []
graph["F"] = []
graph["G"] = []
function dfs(graph, s, t) {
if(s === t) return true // Достигли пункта назнаения
if(s.visited) return true // Уже посещали вершину
s.visited = true // помечаем узел как посещенный
for(i of graph[s]) { // исследуем всех соседей (ближайшие соседние вершины) s
if(!i.visited) { // если сосед ещё не посещался
if(dfs(graph, i, t)) // двигаемся по пути и проверяем, не достигли ли мы пункта назначения
return true // достигли пункт назначения
}
}
return false // если от s до t добраться невозможно
}