[ leetcode 문제풀이 ] Graph Valid Tree

 

https://leetcode.com/problems/graph-valid-tree/

(Graph Valid Tee 문제는 LeetCode Premium 문제로 위 링크 혹은 LintCode를 통해 풀어보실 수 있습니다.)

 

 

 

< Graph Valid Tee 문제 설명 >

 

Graph Valid Tree 문제는 다음과 같다. 

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1]
is the same as [1, 0] and thus will not appear together in edges.

 

주어진 0에서 n-1로 이름 붙여진 nodes와 무방향 edges(각 edge는 node쌍으로 구성)의 배열에 대해, 이 edges가 valid tree를 구성하는지 확인하는 함수를 작성하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

 

---

< Graph Valid Tee 문제 접근(1) >

 

Graph가 Valid Tree가 되기 위한 조건은 두 가지이다:

1) 모든 vertices가 연결되어 있다.

2) Graph의 모든 edges는 cycle을 형성하지 않는다.

 

먼저 graph의 탐색으로 이를 확인할 수 있다. edges로 구성된 그래프가 valid tree라면 임의의 node에서 출발해 DFS를 하면(BFS로도 구현할 수 있음) 모든 nodes를 단 한번만 탐색(최소 1번은 탐색하되 중복해서 탐색하지는 않음) 할 수 있다.

 

이 DFS를 응용한 알고리즘을 코드로 나타내면 다음과 같다. (Cpp 사용)

 

#include <algorithm>
#include <list>

struct Node{
    vector<list<int>> connected;
    vector<bool> visited;
    Node(int n) : connected(n), visited(n, false){};

    void DFS(int vertexNum, bool& isTree){
        visited[vertexNum] = true;

        while(!connected[vertexNum].empty()){
            int there = connected[vertexNum].front();
            if(!visited[there]){
                auto it = find(connected[there].begin(), connected[there].end(), vertexNum);
                connected[there].erase(it);
                DFS(there, isTree);
            }
            else isTree = false;

            if(!isTree) break;
            connected[vertexNum].pop_front();
        }
    } // connected의 삭제가 빈번하므로 list container 사용
};

bool validTree(int n, vector<vector<int>> &edges) {
    if(n==1) return true; // n=1인 경우는 무조건 valid tree 임

    Node Vertices(n);
    // Make Graph
    for(auto edge : edges){
        Vertices.connected[edge[0]].push_back(edge[1]);
        Vertices.connected[edge[1]].push_back(edge[0]);
    }

    // DFS
    bool isTree = true;
    Vertices.DFS(0, isTree);
       
    if(!isTree) return false; // 탐색이 중복된다는 것은 cycle이 존재한다는 뜻임
    for(int i=0;i<n;i++)
        if(!Vertices.visited[i]) // nodes가 두 부분으로 나뉜 경우(forest인 경우)
            return false;
    return true;
} // runtime : 711 ms, memory usage : 5.67 MB (by LintCode)

 

complexity analysis: 시간복잡도: O(n) , 공간복잡도: O(n)

 

→ 0 node에서 시작해 연결된 모든 node를 1번씩 탐색하게 되므로 O(n)의 시간복잡도를 가지고, extra memory usage는 Node.connected와 Node.visited이며 이들은 모두 node의 개수 n 만큼의 크기를 가지므로 공간복잡도는 O(n)이다.

 

 

 

---

< Graph Valid Tee 문제 접근(2) >

 

한편 Union-Find data structure으로도 알 수 있다. 

 

Union-Find data structure의 활용(This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. - from Wikipedia)에서 cycle 판별에 이 자료구조를 적용할 수 있다 하였기 때문..!

 

union-find를 이용해 작성한 알고리즘은 다음과 같다. (Cpp 사용)

 

struct Node{
    vector<int> parent;
    vector<int> rank;
    vector<bool> isConnected;
    Node(int n) : parent(n), rank(n,0), isConnected(n){
        for(int i=0;i<n;i++) parent[i] = i;
    }
        
    // this can be decreased to a constant amount memory
    // by performing both passes in the same direction
    // two passes - once to find the root, once to update pointers.
    int Find(int x){
        int root = x;
        while(parent[root] != root)
            root = parent[root];
            
        while(parent[x] != root){
            int temp = parent[x];
            parent[x] = root;
            x = temp;
        }
        return root;            
    }
        
    // union by rank - ensure that trees do not become too deep
    void Union(int x, int y, bool& isTree){
        isConnected[x] = isConnected[y] = true;

        x = Find(x);
        y = Find(y);
           
        if(x == y){
            isTree = false;
            return;
        }

        if(rank[x] < rank[y])
            swap(x,y);
            
        parent[y] = x;
        if(rank[x] == rank[y])
            rank[x]++;
    }
};

bool validTree(int n, vector<vector<int>> &edges) {
    if(n==1) return true; // n=1인 경우는 무조건 valid tree 임
    Node Set(n);

    bool isTree = true;
    for(auto edge : edges){
        Set.Union(edge[0], edge[1], isTree);
        if(!isTree) return isTree;
    }
		
    int rootNode = Set.Find(0);
    for(int i=0;i<n;i++)
        if(!Set.isConnected[i] || rootNode != Set.Find(i)) 
            return isTree = false; // vertices가 연결되어 있지 않으면 valid tree 불가

return isTree;        
} // runtime : 729 ms, memory usage : 5.52 MB (by LintCode)

 

일반적인 Node, Union 함수의 구조에서 vertex가 연결되었는지를 판별하는 bool isConnected를 정의하고, Union함수가 불렸을 때 Node x, y는 연결되므로 isConnected를 true로 할당하도록 하였다.

 

또한, 출력하는 bool값 isTree에 대해 Union함수에서 Node x,y의 root Node가 일치하는 경우 이미 연결되어 있는 두 Node를 연결하는 추가적인 edge가 존재하는 것이므로 이는 곧 cycle을 형성한다는 의미이기에 isTree = false로 할당하였다.

 

complexity analysis: 시간복잡도: O(n) , 공간복잡도: O(n)

 

→ edge에 대한 for loop는 cycle을 형성하지 않는 최대 edge의 개수 + 1인  n만큼 반복될 수 있으며 valid tree임을 점검하는 for loop는 node의 개수 n만큼 반복되므로 O(n)의 시간복잡도를 가지며, extra memory usage는 Node.parent, Node.rank, Node.isConnected이며 이들은 모두 node의 개수 n 만큼의 크기를 가지므로 O(n)의 공간복잡도를 갖는다.