Алгоритм 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");
    }
}

Пошук спочатку в глибину (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')