S001 · implies
操作前
full carrier Fin(7);raw undirected edges=[[0, 2], [0, 5], [1, 4], [2, 4], [2, 5], [3, 4], [3, 5]]
操作後
canonical simple edges=[[0, 2], [0, 5], [1, 4], [2, 4], [2, 5], [3, 4], [3, 5]];full adjacency rows=[[2, 5], [4], [0, 4, 5], [4, 5], [1, 2, 3], [0, 2, 3], []]
條件:無
用完整載體建立鄰接表,拒絕loop與重複無向邊;沒出現在邊中的頂點仍保留空鄰接列,不切換有向連通語義。
步驟識別與依賴
規則:component_full_undirected_graph_includes_isolates · 依賴:G001
S002 · implies
操作前
selected vertex:start vertex=6;complete adjacency=[[2, 5], [4], [0, 4, 5], [4, 5], [1, 2, 3], [0, 2, 3], []]
操作後
initial visited=[6];path to start=[6];edge length0
條件:無
起點以長度0路徑到自己,孤立點也必須納入,不能因沒有邊而漏掉。
步驟識別與依賴
規則:component_zero_length_reflexive_path · 依賴:G001, S001
S003 · implies
操作前
selected vertex:layer=0;frontier=[6];all frontier neighbors=[]
操作後
previously seen=[6];new vertices=[]
條件:無
每層遍歷該層所有頂點的所有鄰居,去重後只加入未訪者;不提前停止於看起來足夠的子圖。
步驟識別與依賴
規則:component_complete_frontier_expansion · 依賴:G001, S002
S004 · implies
操作前
selected vertex:final visited=[6];all [vertex,neighbors,outside neighbors] rows=[[6, [], []]]
操作後
no edge leaves visited;every visited vertex has a path;visited equals full reachable set
條件:無
路徑見證給已訪⊆可達;搜尋完後無邊離開已訪集合,任一路徑若到外面必有第一條離開邊,矛盾,因此可達⊆已訪。兩方向才是完整分量,不是遍歷順序。
步驟識別與依賴
規則:component_reachable_and_closed_set_completeness · 依賴:G001, S003