Рубрики

Проверьте, является ли данный граф деревом или нет

Графы, Деревья

Напишите функцию, которая возвращает true, если заданный неориентированный граф является деревом, и false в противном случае. Например, следующий график является деревом.

Но следующий граф не является деревом.

Ненаправленный граф является деревом, если он имеет следующие свойства.
1) Цикла нет.
2) График связан.

Для неориентированного графа мы можем использовать BFS или DFS, чтобы обнаружить два вышеуказанных свойства.

Как обнаружить цикл в неориентированном графе?
Мы можем использовать BFS или DFS. Для каждой посещенной вершины v, если есть соседняя u, такая, что u уже посещена, и u не является родителем v, то в графе есть цикл. Если мы не найдем такого смежного объекта для какой-либо вершины, мы говорим, что цикла нет (см. Цикл «Обнаружение цикла» для более подробной информации).

Как проверить подключение?
Поскольку граф не является ненаправленным, мы можем запустить BFS или DFS из любой вершины и проверить, все ли вершины достижимы или нет. Если все вершины достижимы, то граф связен, иначе нет.

C ++

// Программа на C ++ для проверки, является ли граф древовидным или нет
#include<iostream>
#include <list>
#include <limits.h>

using namespace std;

  
// Класс для неориентированного графа

class Graph

{

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

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

    bool isCyclicUtil(int v, bool visited[], int parent);

public:

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

    void addEdge(int v, int w);   // добавить ребро на график

    bool isTree();   // возвращает true, если граф является деревом

};

  

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.

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

}

  
// Рекурсивная функция, которая использует visit [] и parent для
// обнаружение цикла в подграфе, достижимом из вершины v.

bool Graph::isCyclicUtil(int v, bool visited[], int parent)

{

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

    visited[v] = true;

  

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

    list<int>::iterator i;

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

    {

        // Если соседний не посещен, то повторять

        // это смежно

        if (!visited[*i])

        {

           if (isCyclicUtil(*i, visited, v))

              return true;

        }

  

        // Если соседний посещен и не является родителем текущего

        // вершина, то есть цикл.

        else if (*i != parent)

           return true;

    }

    return false;

}

  
// Возвращает true, если граф является деревом, иначе false.

bool Graph::isTree()

{

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

    // стек рекурсии

    bool *visited = new bool[V];

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

        visited[i] = false;

  

    // Вызов isCyclicUtil служит нескольким целям.

    // Возвращает true, если граф достижим из вершины 0

    // цикличен Он также отмечает все доступные вершины

    // с 0.

    if (isCyclicUtil(0, visited, -1))

             return false;

  

    // Если мы найдем вершину, которая недостижима от 0

    // (не помечено isCyclicUtil (), тогда мы возвращаем false

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

        if (!visited[u])

           return false;

  

    return true;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    Graph g1(5);

    g1.addEdge(1, 0);

    g1.addEdge(0, 2);

    g1.addEdge(0, 3);

    g1.addEdge(3, 4);

    g1.isTree()? cout << "Graph is Tree\n":

                 cout << "Graph is not Tree\n";

  

    Graph g2(5);

    g2.addEdge(1, 0);

    g2.addEdge(0, 2);

    g2.addEdge(2, 1);

    g2.addEdge(0, 3);

    g2.addEdge(3, 4);

    g2.isTree()? cout << "Graph is Tree\n":

                 cout << "Graph is not Tree\n";

  

    return 0;

}

Джава

// Java-программа для проверки, является ли граф деревом

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

        adj[w].add(v);

    }

  

    // Рекурсивная функция, которая использует visit [] и parent

    // обнаружение цикла в подграфе, достижимом из вершины v.

    Boolean isCyclicUtil(int v, Boolean visited[], int parent)

    {

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

        visited[v] = true;

        Integer i;

  

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

        Iterator<Integer> it = adj[v].iterator();

        while (it.hasNext())

        {

            i = it.next();

  

            // Если соседний не посещен, то повторять

            // это смежно

            if (!visited[i])

            {

                if (isCyclicUtil(i, visited, v))

                    return true;

            }

  

            // Если соседний посещен и не является родителем

            // текущая вершина, то есть цикл.

            else if (i != parent)

               return true;

        }

        return false;

    }

  

    // Возвращает true, если граф является деревом, иначе false.

    Boolean isTree()

    {

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

        // рекурсивного стека

        Boolean visited[] = new Boolean[V];

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

            visited[i] = false;

  

        // Вызов isCyclicUtil служит нескольким целям

        // Возвращает true, если граф достижим из вершины 0

        // цикличен Он также отмечает все доступные вершины

        // с 0.

        if (isCyclicUtil(0, visited, -1))

            return false;

  

        // Если мы найдем вершину, которая недостижима от 0

        // (не помечено isCyclicUtil (), тогда мы возвращаем false

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

            if (!visited[u])

                return false;

  

        return true;

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

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

        Graph g1 = new Graph(5);

        g1.addEdge(1, 0);

        g1.addEdge(0, 2);

        g1.addEdge(0, 3);

        g1.addEdge(3, 4);

        if (g1.isTree())

            System.out.println("Graph is Tree");

        else

            System.out.println("Graph is not Tree");

  

        Graph g2 = new Graph(5);

        g2.addEdge(1, 0);

        g2.addEdge(0, 2);

        g2.addEdge(2, 1);

        g2.addEdge(0, 3);

        g2.addEdge(3, 4);

  

        if (g2.isTree())

            System.out.println("Graph is Tree");

        else

            System.out.println("Graph is not Tree");

  

    }

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

питон

# Программа Python для проверки
# граф дерево или нет

  

from collections import defaultdict

  

class Graph():

  

    def __init__(self, V):

        self.V = V

        self.graph  = defaultdict(list)

  

    def addEdge(self, v, w):

        # Добавить w к v ist.

        self.graph[v].append(w) 

        # Добавить v в список w.

        self.graph[w].append(v) 

  

    # Рекурсивная функция, которая использует посещения []

    # и родитель для определения цикла в подграфе

    # достижимо из вершины v.

    def isCyclicUtil(self, v, visited, parent):

  

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

        visited[v] = True

  

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

        # для этой вершины

        for i in self.graph[v]:

            # Если соседний не посещен,

            # затем повторить для этого смежного

            if visited[i] == False:

                if self.isCyclicUtil(i, visited, v) == True:

                    return True

  

            # Если соседний посещен, а не

            # родитель текущей вершины, то есть

            # это цикл.

            elif i != parent:

                return True

  

        return False

  

    # Возвращает true, если граф является деревом,

    # еще ложь.

    def isTree(self):

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

        # а не часть стека рекурсии

        visited = [False] * self.V

  

        # Вызов isCyclicUtil обслуживает несколько

        # цели. Возвращает true, если график достижим

        # из вершины 0 цикличен. Это также отмечает

        # все вершины достижимы от 0.

        if self.isCyclicUtil(0, visited, -1) == True:

            return False

  

        # Если мы найдем вершину, которая недоступна

        # из 0 (не помечено isCyclicUtil (),

        # тогда мы возвращаем false

        for i in range(self.V):

            if visited[i] == False:

                return False

  

        return True

  
# Драйверная программа для проверки вышеуказанных функций

g1 = Graph(5)

g1.addEdge(1, 0)

g1.addEdge(0, 2)

g1.addEdge(0, 3)

g1.addEdge(3, 4)

print "Graph is a Tree" if g1.isTree() == True \

                          else "Graph is a not a Tree"

  

g2 = Graph(5)

g2.addEdge(1, 0)

g2.addEdge(0, 2)

g2.addEdge(2, 1)

g2.addEdge(0, 3)

g2.addEdge(3, 4)

print "Graph is a Tree" if g2.isTree() == True \

                          else "Graph is a not a Tree"

                            
# Этот код предоставлен Divyanshu Mehta


Выход:

Graph is Tree
Graph is not Tree

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

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

Проверьте, является ли данный граф деревом или нет

0.00 (0%) 0 votes