You need to enable JavaScript to run this app. 基于DFS的无向图环与死端节点分类打印代码补全问题
优惠活动
大模型
产品
解决方案
定价
更多

基于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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.21 15:15:10