Рубрики

Поиск в глубину или DFS для графика

Глубина первого обхода (или поиска) для графика аналогична глубине первого обхода дерева . Единственный улов здесь, в отличие от деревьев, графы могут содержать циклы, поэтому мы можем снова прийти к одному и тому же узлу. Чтобы избежать обработки узла более одного раза, мы используем логический массив посещений.

Например, на следующем графике мы начинаем обход с вершины 2. Когда мы подходим к вершине 0, мы ищем все смежные ее вершины. 2 также является смежной вершиной 0. Если мы не пометим посещенные вершины, то 2 будет обработан снова, и он станет непрерывным процессом. Первый проход по глубине следующего графика — 2, 0, 1, 3.

См. Этот пост для всех приложений Глубина Первый обход.
Ниже приведены реализации простого обхода глубины. Реализация C ++ использует представление списка смежности графов. Контейнер списка STL используется для хранения списков соседних узлов.

C ++

// C ++ программа для печати обхода DFS из
// данная вершина в данном графе
#include<iostream>
#include<list>

using namespace std;

  
// Графовый класс представляет ориентированный граф
// используя представление списка смежности

class Graph

{

    int V;    // Количество вершин

  

    // Указатель на массив, содержащий

    // списки смежности

    list<int> *adj;

  

    // Рекурсивная функция, используемая DFS

    void DFSUtil(int v, bool visited[]);

public:

    Graph(int V);   // Конструктор

  

    // функция для добавления ребра на график

    void addEdge(int v, int w);

  

    // DFS обход вершин

    // достижим от v

    void DFS(int v);

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

  

void Graph::DFSUtil(int v, bool visited[])

{

    // Пометить текущий узел как посещенный и

    // распечатать

    visited[v] = true;

    cout << v << " ";

  

    // Повтор для всех смежных вершин

    // к этой вершине

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            DFSUtil(*i, visited);

}

  
// Обход DFS вершин, достижимых из v.
// Использует рекурсивный DFSUtil ()

void Graph::DFS(int v)

{

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

  

    // Вызов рекурсивной вспомогательной функции

    // напечатать обход DFS

    DFSUtil(v, visited);

}

  
// Код драйвера

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

  

    cout << "Following is Depth First Traversal"

            " (starting from vertex 2) \n";

    g.DFS(2);

  

    return 0;

}

Джава

// Java-программа для печати обхода DFS из заданного графа

import java.io.*;

import java.util.*;

  
// Этот класс представляет ориентированный граф, используя список смежности
// представление

class Graph

{

    private int V;   // Количество вершин

  

    // Массив списков для представления списка смежности

    private LinkedList<Integer> adj[];

  

    // Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v, int w)

    {

        adj[v].add(w);  // Добавить w в список v.

    }

  

    // Функция, используемая DFS

    void DFSUtil(int v,boolean visited[])

    {

        // Пометить текущий узел как посещенный и распечатать его

        visited[v] = true;

        System.out.print(v+" ");

  

        // Повторение для всех вершин, смежных с этой вершиной

        Iterator<Integer> i = adj[v].listIterator();

        while (i.hasNext())

        {

            int n = i.next();

            if (!visited[n])

                DFSUtil(n, visited);

        }

    }

  

    // Функция для обхода DFS. Он использует рекурсивный DFSUtil ()

    void DFS(int v)

    {

        // Пометить все вершины как не посещенные (установить как

        // false по умолчанию в Java)

        boolean visited[] = new boolean[V];

  

        // Вызываем рекурсивную вспомогательную функцию для печати обхода DFS

        DFSUtil(v, visited);

    }

  

    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, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

  

        System.out.println("Following is Depth First Traversal "+

                           "(starting from vertex 2)");

  

        g.DFS(2);

    }

}
// Этот код предоставлен Aakash Hasija

python3

# Python3 программа для печати обхода DFS
# из данного данного графика

from collections import defaultdict

  
# Этот класс представляет ориентированный граф, используя
# представление списка смежности

class Graph:

  

    # Конструктор

    def __init__(self):

  

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list)

  

    # функция для добавления ребра на график

    def addEdge(self, u, v):

        self.graph[u].append(v)

  

    # Функция, используемая DFS

    def DFSUtil(self, v, visited):

  

        # Отметить текущий узел как посещенный

        # и распечатать

        visited[v] = True

        print(v, end = ' ')

  

        # Повторить для всех вершин

        # рядом с этой вершиной

        for i in self.graph[v]:

            if visited[i] == False:

                self.DFSUtil(i, visited)

  

    # Функция для обхода DFS. Оно использует

    # рекурсивный DFSUtil ()

    def DFS(self, v):

  

        # Отметить все вершины как не посещенные

        visited = [False] * (len(self.graph))

  

        # Вызовите рекурсивную вспомогательную функцию

        # для печати обхода DFS

        self.DFSUtil(v, visited)

  
# Код драйвера

  
# Создать график с учетом
# на диаграмме выше

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

  

print("Following is DFS from (starting from vertex 2)")

g.DFS(2)

  
# Этот код предоставлен Neelam Yadav


Выход:

Following is Depth First Traversal (starting from vertex 2)
2 0 1 3

Иллюстрация для неориентированного графа:







Как работать с отключенным графом?

Приведенный выше код пересекает только вершины, доступные из заданной исходной вершины. Все вершины могут быть недоступны из данной вершины (например, отключенный граф). Чтобы выполнить полный DFS-обход таких графов, мы должны вызвать DFSUtil () для каждой вершины. Кроме того, перед вызовом DFSUtil () мы должны проверить, напечатано ли оно каким-либо другим вызовом DFSUtil (). Следующая реализация выполняет полный обход графа, даже если узлы недоступны. Отличия от приведенного выше кода выделены в приведенном ниже коде.

C ++

// C ++ программа для печати обхода DFS для данного заданного графа
#include<iostream>
#include         <list>

using namespace std;

  

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;    // Указатель на массив, содержащий списки смежности

    void DFSUtil(int v, bool visited[]);  // Функция, используемая DFS

public:

    Graph(int V);   // Конструктор

    void addEdge(int v, int w);   // функция для добавления ребра на график

    void DFS();    // печатает обход DFS полного графа

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

  

void Graph::DFSUtil(int v, bool visited[])

{

    // Пометить текущий узел как посещенный и распечатать его

    visited[v] = true;

    cout << v << " ";

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

    for(i = adj[v].begin(); i != adj[v].end(); ++i)

        if(!visited[*i])

            DFSUtil(*i, visited);

}

  
// Функция для обхода DFS. Он использует рекурсивный DFSUtil ()

void Graph::DFS()

{

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

  

    // Вызываем рекурсивную вспомогательную функцию для печати обхода DFS

    // начиная со всех вершин по одной

    for (int i = 0; i < V; i++)

        if (visited[i] == false)

            DFSUtil(i, visited);

}

  

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

  

    cout << "Following is Depth First Traversaln";

    g.DFS();

  

    return 0;

}

Джава

// Java-программа для печати обхода DFS из заданного графа

import java.io.*;

import java.util.*;

  
// Этот класс представляет ориентированный граф, используя список смежности
// представление

class Graph

{

    private int V;   // Количество вершин

  

    // Массив списков для представления списка смежности

    private LinkedList<Integer> adj[];

  

    // Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v, int w)

    {

        adj[v].add(w);    // Добавить w в список v.

    }

  

    // Функция, используемая DFS

    void DFSUtil(int v,boolean visited[])

    {

        // Пометить текущий узел как посещенный и распечатать его

        visited[v] = true;

        System.out.print(v+" ");

  

        // Повторение для всех вершин, смежных с этой вершиной

        Iterator<Integer> i = adj[v].listIterator();

        while (i.hasNext())

        {

            int n = i.next();

            if (!visited[n])

                DFSUtil(n,visited);

        }

    }

  

    // Функция для обхода DFS. Он использует рекурсивный DFSUtil ()

    void DFS()

    {

        // Пометить все вершины как не посещенные (установить как

        // false по умолчанию в Java)

        boolean visited[] = new boolean[V];

  

        // Вызываем рекурсивную вспомогательную функцию для печати обхода DFS

        // начиная со всех вершин по одной

        for (int i=0; i<V; ++i)

            if (visited[i] == false)

                DFSUtil(i, visited);

    }

  

    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, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

  

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

  

        g.DFS();

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Программа Python для печати обхода DFS для полного графика

from collections import defaultdict

  
# Этот класс представляет ориентированный граф с использованием смежности
# представление списка

class Graph:

  

    # Конструктор

    def __init__(self):

  

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list)

  

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

  

    # Функция, используемая DFS

    def DFSUtil(self, v, visited):

  

        # Отметить текущий узел как посещенный и распечатать его

        visited[v]= True

        print v,

  

        # Повторить для всех вершин, смежных с

        # эта вершина

        for i in self.graph[v]:

            if visited[i] == False:

                self.DFSUtil(i, visited)

  

  

    # Функция для обхода DFS. Оно использует

    # рекурсивный DFSUtil ()

    def DFS(self):

        V = len(self.graph)  # итоговые вершины

  

        # Отметить все вершины как не посещенные

        visited =[False]*(V)

  

        # Вызовите рекурсивную вспомогательную функцию для печати

        # Обход DFS, начиная со всех вершин один

        # одним

        for i in range(V):

            if visited[i] == False:

                self.DFSUtil(i, visited)

  

  
# Код драйвера
# Создайте график, приведенный на диаграмме выше

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

  

print "Following is Depth First Traversal"

g.DFS()

  
# Этот код предоставлен Neelam Yadav


Выход:

Following is Depth First Traversal
0 1 2 3

Сложность времени: O (V + E), где V — количество вершин в графе, а E — количество ребер в графе.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поиск в глубину или DFS для графика

0.00 (0%) 0 votes