사용자 도구

사이트 도구


ps:teflib:graph

graph.py

imports and globals

minimum_spanning_tree

코드

# N minimum_spanning_tree
# I {"version": "1.01", "import": ["operator"], "func": ["disjointset.DisjointSet"], "const": ["INF", "EdgeWGraph"]}
def minimum_spanning_tree(graph_edges: EdgeWGraph,
                          node_count: int) -> EdgeWGraph:
    """Returns the minimum spanning tree of given graph."""
    dsu = disjointset.DisjointSet(node_count)
    component_count, mst_edges = node_count, []
    for e in sorted(graph_edges, key=operator.itemgetter(2)):
        u, v, _ = e
        if dsu.union_if_disjoint(u, v):
            mst_edges.append(e)
            component_count -= 1
            if component_count == 1:
                return mst_edges
    raise ValueError('Graph is not connected')

설명

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ1647도시 분할 계획골드 4
BOJ1922네트워크 연결골드 4
BOJ2887행성 터널플래티넘 5
BOJ6497전력난골드 4
BOJ7044Bad Cowtractors골드 4

minimum_spanning_tree_dense

코드

# N minimum_spanning_tree_dense
# I {"version": "1.1", "import": ["operator"], "const": ["EdgeWGraph", "MatGraph", "INF"]}
def minimum_spanning_tree_dense(mat_graph) -> EdgeWGraph:
    """Returns MST of given complete undirected graph.

    Implementation is based on Prim's algorithm, running in O(V^2)."""
    weights = {x: INF for x in range(1, len(mat_graph))}
    par = [None] * len(mat_graph)
    min_weight_node = 0
    mst_edges = []
    for _ in range(len(mat_graph) - 1):
        p = min_weight_node
        weights_from_p = mat_graph[p]
        min_weight = INF
        for v, weight_v in weights.items():
            if (w := weights_from_p[v]) < weight_v:
                par[v], weights[v], weight_v = p, w, w
            if weight_v < min_weight:
                min_weight_node, min_weight = v, weight_v
        mst_edges.append((par[min_weight_node], min_weight_node, min_weight))
        del weights[min_weight_node]
    return sorted(mst_edges, key=operator.itemgetter(2))

설명

이 코드를 사용하는 문제

토론

댓글을 입력하세요:
G L M Y D
 
ps/teflib/graph.txt · 마지막으로 수정됨: 2022/10/04 14:30 저자 teferi