基于DFS的无向图环与死端节点分类打印代码补全问题
扩展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代码,可实现图中环存在性的判断,但尚未实现环内节点、死端节点的正确打印输出功能,分类逻辑存在缺陷,输出结果不符合作业要求。
现有代码内容:
# 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") '''
内容的提问来源于stack exchange,提问作者bhamam
相关产品推荐
相关产品推荐

