Рубрики

Программа Python для обнаружения цикла в ориентированном графе

По заданному ориентированному графу проверьте, содержит ли граф цикл или нет. Ваша функция должна возвращать true, если данный граф содержит хотя бы один цикл, иначе возвращает false. Например, следующий график содержит три цикла 0-> 2-> 0, 0-> 1-> 2-> 0 и 3-> 3, поэтому ваша функция должна возвращать true.

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

  

from collections import defaultdict

  

class Graph():

    def __init__(self, vertices):

        self.graph = defaultdict(list)

        self.V = vertices

  

    def addEdge(self, u, v):

        self.graph[u].append(v)

  

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

  

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

        # добавляет в стек рекурсии

        visited[v] = True

        recStack[v] = True

  

        # Повтор для всех соседей

        # если любой сосед посещен и в

        # recStack, то график циклический

        for neighbour in self.graph[v]:

            if visited[neighbour] == False:

                if self.isCyclicUtil(neighbour, visited, recStack) == True:

                    return True

            elif recStack[neighbour] == True:

                return True

  

        # Узел должен быть извлечен из

        # стек рекурсии до завершения функции

        recStack[v] = False

        return False

  

    # Возвращает true, если график циклический, иначе false

    def isCyclic(self):

        visited = [False] * self.V

        recStack = [False] * self.V

        for node in range(self.V):

            if visited[node] == False:

                if self.isCyclicUtil(node, visited, recStack) == True:

                    return True

        return False

  

g = 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)

if g.isCyclic() == 1:

    print "Graph has a cycle"

else:

    print "Graph has no cycle"

  
# Спасибо Divyanshu Mehta за предоставленный код

Выход:

Graph has a cycle

Пожалуйста, обратитесь к полной статье об Обнаружении Цикла в Направленном Графе для более подробной информации!

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

Программа Python для обнаружения цикла в ориентированном графе

0.00 (0%) 0 votes