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

Материал из Викиучебника — открытых книг для открытого мира
Перейти к: навигация, поиск

Поиск в глубину (англ. 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 (const 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. Матрица связности.
g = [[0,1,0],  # матрица связности
     [1,1,0],
     [0,0,1]]

ex = set()       # множество посещенных вершин
def dfs(node):   # start - начальная вершина
    ex.add(node)
    for i in range(len(g)):
        if g[node][i] == 1 and i not in ex:
            print(i)
            dfs(i)

# 2. Список смежности.
list_of_adjacency = [[1,3], [0], [3], [2,0], []]
visited = [False for i in range(len(list_of_adjacency ))]

def dfs(v):
    visited[v] = True
    for vertex in list_of_adjacency[v]:
        if not visited[vertex]:
            dfs(vertex)

for c in range(len(list_of_adjacency )):
    if not visited[c]:
        dfs(c)

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 );
  }
}