Реализации алгоритмов/Поиск в глубину

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

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 добраться невозможно
}