Алгоритм DFS («Depth-first search» или «Поиск в глубину»)

Tree, Дерево, Алгоритм

Обход означает посещение всех узлов графа. «Обход в глубину» или «Поиск в глубину» - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье, с помощью приведенных ниже примеров, вы узнаете: алгоритм DFS, псевдокод DFS и код алгоритма «поиска в глубину» с реализацией в программах на C ++, C, Java и Python.

Алгоритм DFS

Стандартная реализация DFS помещает каждую вершину графа в одну из двух категорий:

  1. Посещенные.
  2. Не посещенные.

Цель алгоритма - пометить каждую вершину, как посещенную, избегая циклов.

Алгоритм DFS работает следующим образом:

  1. Начните с размещения любой вершины графа на вершине стека.
  2. Возьмите верхний элемент стека и добавьте его в список посещенных.
  3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в начало стека.
  4. Продолжайте повторять шаги 2 и 3, пока стек не станет пустым.

Пример DFS

Давайте посмотрим, как алгоритм «поиска в глубину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начинаем с вершины 0, алгоритм DFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в верхней части стека, то есть 1, и переходим к смежным узлам. Так как 0 мы уже посетили, вместо этого посещаем 2.

У вершины 2 есть не посещенная смежная вершина 4, поэтому мы добавляем ее в верхнюю часть стека и посещаем.

После того, как мы посетим последний элемент 3, у него нет не посещенных смежных узлов. На этом мы завершим первый «обход в глубину» графа.

Псевдокод DFS (рекурсивная реализация)

Псевдокод для DFS показан ниже. Обратите внимание, что в функции init() мы запускаем функцию DFS на каждом узле. Это связано с тем, что граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм DFS на каждом узле.

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)

init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

Код DFS

Код для алгоритма «поиска в глубину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.

DFS в C

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int vertex;
    struct node* next;
};

struct node* createNode(int v);

struct Graph
{
    int numVertices;
    int* visited;
    struct node** adjLists; // we need int** to store a two dimensional array. Similary, we need struct node** to store an array of Linked lists
};

struct Graph* createGraph(int);
void addEdge(struct Graph*, int, int);
void printGraph(struct Graph*);
void DFS(struct Graph*, int);


int main()
{

    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    DFS(graph, 2);

    return 0;
}

void DFS(struct Graph* graph, int vertex) {
        struct node* adjList = graph->adjLists[vertex];
        struct node* temp = adjList;

        graph->visited[vertex] = 1;
        printf("Visited %d \n", vertex);

        while(temp!=NULL) {
            int connectedVertex = temp->vertex;

            if(graph->visited[connectedVertex] == 0) {
                DFS(graph, connectedVertex);
            }
            temp = temp->next;
        }       
}


struct node* createNode(int v)
{
    struct node* newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices)
{
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct node*));

    graph->visited = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest)
{
    // Add edge from src to dest
    struct node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

Depth First Search (DFS) в C++

#include <iostream>
#include <list>
using namespace std;

class Graph
{
    int numVertices;
    list *adjLists;
    bool *visited;

public:
    Graph(int V);
    void addEdge(int src, int dest);
    void DFS(int vertex);
};

Graph::Graph(int vertices)
{
    numVertices = vertices;
    adjLists = new list[vertices];
    visited = new bool[vertices];
}

void Graph::addEdge(int src, int dest)
{
    adjLists[src].push_front(dest);
}

void Graph::DFS(int vertex)
{

    visited[vertex] = true;
    list adjList = adjLists[vertex];

    cout << vertex << " ";

    list::iterator i;
    for(i = adjList.begin(); i != adjList.end(); ++i)
        if(!visited[*i])
            DFS(*i);
}

int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    g.DFS(2);

    return 0;
}

DFS Java код (Java code)

import java.io.*;
import java.util.*;


class Graph
{
    private int numVertices;
    private LinkedList<Integer> adjLists[];
    private boolean visited[];

    Graph(int vertices)
    {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<Integer>();
    }

    void addEdge(int src, int dest)
    {
        adjLists[src].add(dest);
    }

    void DFS(int vertex)
    {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        Iterator ite = adjLists[vertex].listIterator();
        while (ite.hasNext())
        {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj);
        }
    }


    public static void main(String args[])
    {
        Graph g = new Graph(4);

         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 3);

        System.out.println("Following is Depth First Traversal");

        g.DFS(2);
    }
}

DFS в Python

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

СВ
23 октября 2019 г. 1:00
Семен Волох

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:70баллов,
  • Очки рейтинга1
SS
22 октября 2019 г. 14:31
Samantha Smith

Qt - Тест 001. Сигналы и слоты

  • Результат:52баллов,
  • Очки рейтинга-4
МБ
21 октября 2019 г. 1:25
Михаил Булатов

C++ - Тест 002. Константы

  • Результат:16баллов,
  • Очки рейтинга-10
Последние комментарии
17 октября 2019 г. 2:17
Евгений Легоцкой

Используем, там где требуется :)
MP
17 октября 2019 г. 2:15
Mikhail Petrov

Совет: подключайте ресурсы динамически. Используйте Resource Compiler: https://doc.qt.io/qt-5/rcc.html
16 октября 2019 г. 6:45
Евгений Легоцкой

Если это не чистой воды спам, а по делу, то без проблем. Но в таком случае лучше создавайте отдельный вопрос на форуме . При создании вопроса есть поле, в котором можно указать статью…
КК
16 октября 2019 г. 6:39
Кирилл Кирилыч

А тут можно ссылки на сторонний ресурс показывать? Нашёл на habr похожую статью, только там чуток отличается код и про локальный сервер написано, нужно чтоб кто то понимающий посмотрел и своё …
Сейчас обсуждают на форуме
23 октября 2019 г. 4:06
Евгений Легоцкой

Ну если после обновления начало появляться, то тогда откатить драйвера. А вообще, если это жить не мешает и код работает как и раньше, то просто проигнорировать эти сообщения.
22 октября 2019 г. 2:42
Pavel K.

Всем привет , Пытаюсь реализовать класс для работы с блютуз (Bluetooth Handler) для мобилки , с использование QBluetoothDeviceInfo и QBluetoothDeviceDiscoveryAgent . Может у кого е…
22 октября 2019 г. 2:16
Pavel K.

попробуй сделать через свой собственный компонет , те возьми контрол Component, например , переорпедели как свой , в нем что нить типо проперти type : disk1, disk2 (сделай метод в структуре …
Е
22 октября 2019 г. 0:03
Евгений_Канусовский@1981

Этот алгоритм предназначен для того чтобы исключить из обработки строки содержащие буквенные символы. Если Вам не трудно опишите пожалуйста как бы Вы написали этот алгоритм, желательно в коде?
MP
21 октября 2019 г. 7:03
Mikhail Petrov

Зависит от вашей задачи. Можете обратить внимание на этот пример: https://doc.qt.io/qt-5/qtqml-referenceexamples-properties-example.html QQmlListProperty используется мною достаточно ч…
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB