iframe-proxy | Sunbelt Computer Software

42 lines (38 loc) · 976 Bytes

# Finding Bridges in Undirected Graph
def computeBridges(graph):
    n = len(graph)  # No of vertices in graph
    low = [0] * n
    visited = [False] * n
    def dfs(at, parent, bridges, id):
        visited[at] = True
        low[at] = id
        id += 1
        for to in graph[at]:
            if to == parent:
            elif not visited[to]:
                dfs(to, at, bridges, id)
                low[at] = min(low[at], low[to])
                if at < low[to]:
                    bridges.append([at, to])
            else:
                # This edge is a back edge and cannot be a bridge
                low[at] = min(low[at], to)
    bridges = []
    for i in range(n):
        if not visited[i]:
            dfs(i, -1, bridges, id)
    print(bridges)
    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],
computeBridges(graph)

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

finding_bridges.py

Latest commit

History

finding_bridges.py

File metadata and controls