Блог

У меня есть упражнение для университета, где я должен написать расширенный алгоритм DFS. На основе DFS я должен указать процедуру, которая пересекает неориентированный непрерывный граф, классифицируя каждый узел в соответствии с тем, является ли он частью цикла или тупиком, и печатать узлы, которые находятся в цикле или в тупике. Эта процедура должна быть применена к графам, показанным с помощью начального узла S. Нарисованный граф

У меня есть следующий список смежности:

 'S' : ['A']
'A' : ['B','F']
'B' : ['C','H']
'C' : ['D','B']
'D' : ['C','E','G']
'E' : ['D','F']
'F' : ['A','E']
'G' : ['D']
'H' : ['B','I']
'I' : ['H']
  

Я сопоставил каждый узел со следующими номерами:

 0: S
1: A
2: B
3: C
4: D
5: E
6: F
7: G
8: H
9: I
  

Вот код, который я написал до сих пор для обнаружения цикла в графе (отредактированный):

 
# Python Program to detect cycle in an undirected graph 
from collections import defaultdict

visitedList = list()
nodes = set()
s = ''


# This class represents a undirected graph using adjacency list representation
class Graph:

    def __init__(self, vertexCount):
        self.V = vertexCount  # No. of vertices
        self.graph = defaultdict(list)  # default dictionary to store graph

    # function to add an edge to graph
    def addEdge(self, v, w):
        self.graph[v].append(w)  # Add w to v_s list
        self.graph[w].append(v)  # Add v to w_s list
        nodes.add(v)
        nodes.add(w)
        # print(self.graph)

    # A recursive function that uses visited[] and parent to detect
    # cycle in subgraph reachable from vertex v.
    def isCyclicUtil(self, v, visited, parent, cycle=list()):
        global s
        visited[v] = True
        visitedList.append(v)
        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            # If the node is not visited then recurse on it
            if not visited[i]:
                cycle.append(i)
                if self.isCyclicUtil(i, visited, v, cycle):
                    return
            # If an adjacent vertex is visited and not parent of current vertex,
            # then there is a cycle
            elif parent != i:
                s = 'Nodes in a cycle: '
                s  = ' '.join(str(v) for v in cycle)
                s  = 'nNodes in a dead end: '
                s  = ' '.join(str(v) for v in Diff(nodes, cycle))
                #return
                return True
        return cycle

    # Returns true if the graph contains a cycle, else false.
    def isCyclic(self):
        # Mark all the vertices as not visited
        visited = [False] * (self.V)
        cycle = list()
        # Call the recursive helper function to detect cycle in different 
        # DFS trees
        for i in range(self.V):
            if not visited[i]:  # Don't recur for u if it is already visited
                if self.isCyclicUtil(i, visited, -1, cycle):
                    return True
        return False


def Diff(li1, li2):
    return list(list(set(li1) - set(li2))   list(set(li2) - set(li1)))


# Driver code
# Create a graph with given adjacency list
S = 0
A = 1
B = 2
C = 3
D = 4
E = 5
F = 6
G = 7
H = 8
I = 9

g = Graph(10)

g.addEdge(S, A)
g.addEdge(A, B)
g.addEdge(B, C)
g.addEdge(B, H)
g.addEdge(C, D)
g.addEdge(D, E)
g.addEdge(D, G)
g.addEdge(E, F)
g.addEdge(F, A)
g.addEdge(H, I)


if g.isCyclic():
    print("Graph contains cycle")
    print(s)
else:
    print("Graph does not contain cycle")

'''
g = Graph(6)

g.addEdge(0, 1)
g.addEdge(1, 3)
g.addEdge(1, 2)
g.addEdge(1, 4)
g.addEdge(4, 5)

if g.isCyclic():
    print("Graph contains cycle")
    print(s)
else:
    print("Graph does not contain cycle")
'''
  

Чего здесь еще не хватает, так это печатать узлы, которые находятся в цикле или в тупике.