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

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

Content

Обход означает посещение всех узлов графа. «Обход в глубину» или «Поиск в глубину» - это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье, с помощью приведенных ниже примеров, вы узнаете: алгоритм 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')
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
s
June 3, 2020, 1:56 a.m.
silo1995

C++ - Тест 003. Условия и циклы

  • Result:35points,
  • Rating points-10
AP
June 2, 2020, 9:11 p.m.
Aleksej Pikenin

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
June 2, 2020, 1:04 p.m.
Daniil Chizhevskij

C++ - Test 001. The first program and data types

  • Result:86points,
  • Rating points6
Last comments
June 4, 2020, 11:10 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Полностью скопировал пример - всё правильно работает. Значит, где-то у меня ошибки в тестовом проекте. Буду разбираться. Извините за беспокойство. :)
June 4, 2020, 7:08 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Во все колонки установили? Нужно на все колонки устанавливать.
June 4, 2020, 6:59 a.m.
IscanderChe

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Код делегата полностью скопировал в свой тестовый проект, но окрашивается не вся строка целиком, а только ячейка, на которую указывает курсор.
June 4, 2020, 6:12 a.m.
Evgenij Legotskoj

Qt/C++ - Tutorial 091. How to write a custom delegate controlling the highlighting of a row in a table

Добрый день. Удобства ради. В больших проектах удобнее вызывать BaseClass, чем постоянно смотреть, от чего конкретно наследован текущий класс. Экономит время.
Now discuss on the forum
MA
June 4, 2020, 2:46 a.m.
Mihail A

Qt- C++ QTableView подсветить строку

Спасибо.
f
June 3, 2020, 1:49 a.m.
fryn3

Можно ли сделать в QML таблицу как в Excel?

edi-tableview - нашел пока такое выглядит коряво, посмотрим что можно сделать
June 2, 2020, 2:46 a.m.
Evgenij Legotskoj

Медиа файлы Google Firebase

Картинки можете попробовать сжимать через QPixmap, там есть возможность установки scaleFactor, через него можете устанавливать нужные параметры. А что касается конвертации видео, то лучше п…
June 2, 2020, 2:01 a.m.
Evgenij Legotskoj

Перехват обращения к локальным файлам QWebEngineView

В вашем случае вполне адекватное решение. Так сказать меньше зло. В противном случае пришлось бы очень много переписывать и перепиливать.
a
June 1, 2020, 10:26 a.m.
alekseyttrv

SSL на Android

у меня стоит версия Qt 5.14.2. В настройках android поставил openssl из коробки, и этот прроект автоматически стянулся. Достаточно было только добавить в .pro-файл строку после этого и все …
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB