mafulechka
mafulechkaМаусым 17, 2019, 1:45 Т.Ж.

DFS алгоритмі («Тереңдік-бірінші іздеу» немесе «тереңдік-бірінші іздеу»)

Саяхат графиктің барлық түйіндеріне баруды білдіреді. Тереңдікке өту немесе Тереңдік бойынша бірінші іздеу — графиктің немесе ағаш деректер құрылымының барлық шыңдарын табуға арналған рекурсивті алгоритм. Бұл мақалада төмендегі мысалдардың көмегімен сіз мыналарды білесіз: DFS алгоритмі, DFS псевдокоды және C++, C, Java және Python бағдарламаларында іске асырылатын DFS алгоритм коды.


DFS алгоритмі

DFS стандартты орындалуы әрбір график шыңын екі санаттың біріне қояды:

  1. Барды.
  2. Бармаған.

Алгоритмнің мақсаты циклдарды болдырмай, әрбір шыңды барған деп белгілеу.

DFS алгоритмі келесідей жұмыс істейді:

  1. Графиктің кез келген шыңын стектің үстіне қоюдан бастаңыз.
  2. Стектің жоғарғы элементін алыңыз және оны кірген тізімге қосыңыз.
  3. Осы төбенің көршілес түйіндерінің тізімін жасаңыз. Барғандар тізімінде жоқтарды стектің жоғарғы жағына қосыңыз.
  4. Бума бос болғанша 2 және 3-қадамдарды қайталауды жалғастырыңыз.

DFS мысалы

Мысал арқылы бірінші тереңдік іздеу алгоритмі қалай жұмыс істейтінін көрейік. Біз 5 төбесі бар бағытталмаған графикті қолданамыз.

Біз 0 түйінінен бастаймыз, DFS алгоритмі оны кірген тізімге орналастырудан және барлық көрші түйіндерді стекке орналастырудан басталады.

Содан кейін біз стектің жоғарғы жағындағы элементке, яғни 1-ге кіріп, көрші түйіндерге көшеміз. Біз 0-ге кіргендіктен, оның орнына 2-ге кіреміз.

Vertex 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 алгоритмінің коды көрсетілген. Код жеңілдетілген, сондықтан біз басқа мәліметтерге емес, алгоритмге назар аудара аламыз.

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 коды

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

Python тіліндегі DFS

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 хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

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

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

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

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

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

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз