Graph (BFS,DFS, MST algorithms)

Hyunwoo Lee

7 min readFeb 18, 2024

Definition

A graph G = (V,E) consists of a set of vertices, V and set of edges E.
Each edge is a pair of (u,v), where u,v ∈ V.
Vertex u is adjacent to v if and only if (u,v) ∈ E.

Directed Acyclic Graph (DAG) : edge with directions + no cycle

Complete graph : a graph in there is an edge between every pair of vertices.

Breadth First Search (BFS)

탐색하지않은 vertices를 균등하게 탐색하는 방식
큐에서 하나씩 노드를 dequeue하고 인접한 노드들중에서 방문하지 않은 노드들을 enque.
모든 vertex는 한번 enqueue, dequeue해야함 => O(V)
모든 vertex에서 인접노드들은 모두 한번씩 체크해야함 => O(E)
BFS에 소요되는 시간복잡도 => O(V+E)

Depth First Search (DFS)

더이상 다음노드가 없을때까지 탐색하는 방식
재귀함수로 구현
BFS와 같이 각 노드에 방문하고 인접노드도 모두 방문하기 때문에 O(V+E)

Topological Sort

모든 노드를 기존의 순서대로 정렬하는 방법.
graph G가 edge(u,v)를 포함할때, u는 v전에 나타난다.
만약 cycle이 존재하면 linear ordering이 불가.
DFS하면서 Vertex 끝나면 stack에 push한다(dfs의 역수) => O(V+E)

Minimum Spanning Trees

spanning tree : a tree that connects all vertices in a graph.

Kruskal’s Algorithm: edge weight 작은 순서대로 정렬. 작은 순서대로 가서 합치되, 이미 Set에 있으면 vertex를 합치지않는다. 모든 노드 들어갈때까지 반복한다. 항상 최선의 수를 선택하는 Greedy 알고리즘의 일종.

남은 edge중에서 cost가 가장 낮은 edge를 고른다. A={(A,D),(C,E)}

남은 edge중에서 cost가 가장 낮은 edge를 고른다. A={(A,D),(C,E),(D,F)}

남은 edge중에서 cost가 가장 낮은 edge를 고른다. A={(A,D),(C,E),(D,F),(A,B)}

남은 edge중에서 cost가 가장 낮은 edge를 고른다. A={(A,D),(C,E),(D,F),(A,B),(B,E)}

낮은 edge는 BC가 있지만 EF를 선택한다 (cycle 생기는지 유무)

function KruskalMST(graph):
    A = ∅                         // A는 최소 스패닝 트리를 구성할 간선의 집합
    for each vertex v in graph:
        MakeSet(v)                // 각 정점을 독립적인 집합으로 초기화 // O(V)

    EdgeList = sort edges of graph by increasing order of weight // O(ElogE)
    for each edge (u, v) in EdgeList:
        if FindSet(u) ≠ FindSet(v):   // u와 v가 서로 다른 집합에 속해있으면, 즉 사이클을 형성하지 않으면 // O(E)
            A = A ∪ {(u, v)}          // A에 현재 간선을 추가
            Union(u, v)               // u와 v를 포함하는 집합을 합침 // O(V)

    return A

최종 시간복잡도는 O(ElogE)+O(Eα(V))인데 E가 주요한 값으로 O(ElogE)로 볼수 있다.

2. Prim’s Algorithm : kruskal에서 edge를 기반으로 하나씩 추가했다면 여기서는 vertex를 기준으로 가장 minimal한 weight를 가지는 vertex를 하나씩추가하는 방식.

Prim algorithm에서 cycle 체크가 필요없는 이유는?

=> edge가 아니라 vertex를 기준으로 포함되지 않은 vertex를 포함하기 때문.

function PrimMST(graph):
    Initialize a priority queue Q with all vertices in graph, where
    the keys are the weights to the vertices (initially set to infinity
    except for the start vertex, which is set to 0)
    
    parent = array of size |V| to store the MST structure
    for each vertex v in graph: // O(V)
        parent[v] = NIL              // 초기 부모 설정
        if v is the start vertex:
            key[v] = 0               // 시작 정점의 키 값을 0으로 설정
        else:
            key[v] = ∞               // 나머지 정점의 키 값을 무한대로 설정
        Q.insert(v, key[v])          // 각 정점을 우선순위 큐에 삽입

    while Q is not empty: 
        u = Q.extractMin()           // 키 값이 가장 작은 정점 u를 추출 // O(VlogV)
        for each vertex v adjacent to u:
            if v ∈ Q and weight(u, v) < key[v]:
                parent[v] = u         // u를 v의 부모로 설정
                key[v] = weight(u, v) // v의 키 값을 업데이트
                Q.decreaseKey(v, key[v])  // 우선순위 큐에서 v의 키 값을 업데이트 // O(ElogV)

    return parent                     // MST를 구성하는 간선들을 반환

최종 시간복잡도는 O((E+V)logV)= O(ElogV)이다. (binary heap으로 구현)

Graph (BFS,DFS, MST algorithms)

Written by Hyunwoo Lee