DFSのプログラムの問題
解決したいこと
DFSのプログラムの問題を解いています。
問題は3つのパートに別れており、2つ目のパートにエラーがあると考えられます。
何度もやり直したり別のコードを試しましたが、1ヶ月以上スタックしており、手がかりがありません。
回答についてアイデアをいただけないでしょうか。
Part1(正解)
Part2(エラーが出ている箇所)
プログラムは以下です。
#your code here 以下を記載しています。 2つ目のスクリーンショットは固定なので、1枚目が問題と考えています。
発生している問題・エラー
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-4-6adafcd6964a> in <module>
8 g.add_edge(3,4)
9
---> 10 assert num_connected_components(g) == 1, f' Test A failed: g must have 1 connected component. Your code returns {num_connected_components(g)}'
11
12
AssertionError: Test A failed: g must have 1 connected component. Your code returns None
該当するソースコード
def num_connected_components(g): # g is an UndirectedGraph class
# your code here
#UnidirectedGraph Class
class UndirectedGraph():
#init function to declare class variables and declare number of vertices
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
# method to add an undirected edge add_edge function
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
def dfs_traverse_graph(g, temp, v, visited):
#Mark the current vertex as visited
visited[v] = True
#Store the vertex to list
temp.append(v)
# Repeat for all vertices adjacent to this vertex v
for i in g.adj[v]:
if visited[i] == False:
temp = dfs_traverse_graph(g, temp, i, visited)
return temp
#Method to retrieve connected components in an undirected graph
def num_connected_components(g):
visited = []
cc = []
for i in range(g.V):
visited.append(False)
for v in range(g.V):
if visited[v] == False:
temp = []
cc.append(dfs_traverse_graph(g, temp, v, visited))
return len(cc)
Part３ (こちらはエラーが出ていますが、上記のコードを記載しない状態だと正常に動作します。)
正解の場合
0
