GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python-3/graphs/articulation_points.py at master · https-github-com-nzysoft/Python-3 Expand file tree/ Copy patharticulation_points.pyMore file actions 55 lines (48 loc) · 1.31 KB / Copy patharticulation_points.pyFile metadata and controls55 lines (48 loc) · 1.31 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 # Finding Articulation Points in Undirected Graph def compute_ap(l): # noqa: E741 n = len(l) out_edge_count = 0 low = [0] * n visited = [False] * n is_art = [False] * n def dfs(root, at, parent, out_edge_count): if parent == root: out_edge_count += 1 visited[at] = True low[at] = at for to in l[at]: if to == parent: pass elif not visited[to]: out_edge_count = dfs(root, to, at, out_edge_count) low[at] = min(low[at], low[to]) # AP found via bridge if at < low[to]: is_art[at] = True # AP found via cycle if at == low[to]: is_art[at] = True else: low[at] = min(low[at], to) return out_edge_count for i in range(n): if not visited[i]: out_edge_count = 0 out_edge_count = dfs(i, i, -1, out_edge_count) is_art[i] = out_edge_count > 1 for x in range(len(is_art)): if is_art[x] is True: print(x) # Adjacency list of graph data = { 0: [1, 2], 1: [0, 2], 2: [0, 1, 3, 5], 3: [2, 4], 4: [3], 5: [2, 6, 8], 6: [5, 7], 7: [6, 8], 8: [5, 7], } compute_ap(data) |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |