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

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

JavaПравить

List<Integer>[] graph = readGraph();
boolean[] used = new boolean[graph.length];

public static void dfs(int pos) {
    used[pos] = true;
    System.out.println(pos);
    for (int next : graph[pos]){
        if (!used[next]){
            dfs(next);
        }
    }
}

С++Править

vector<vector<int>> graph;

vector<bool> used;

void dfs(int node_index)
{
    used[node_index] = true;
    for (auto i : graph[node_index])
    {
        if (!used[i])
            dfs(i);
    }
}

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)
            start(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"))
  //Оба алгоритма обходят один и тот же граф в глубину, но в разном порядке
}