개념
=> Disjoint Set(서로소 집합) 자료구조를 표현할때 사용하는 알고리즘.
=> 여러 노드가 존재할 때, 두개의 노드를 선택해서 두개의 노드가 하나의 집합에 포함되어 있는지 판별하는 알고리즘
=> Kruskal 알고리즘의 사이클 체크에 사용된다.
=> 다양한 자료구조를 사용해 구현할수 있지만, 가장 편한 트리의 개념을 통해 구현한다.

연산
init()
=> 각 노드를 독립노드로 초기화한다.

find(x)
=> x가 어떤 집합에 포함되어있는지 알려준다.

union(x, y)
=> x가 속한 집합과, y가 속한 집합을 합친다.

if (find(x) == find(y))
std::cout << "같은 집합에 속해있다.";
else
std::cout << "다른 집합에 속해있다";

구현
=>배열의 개념을 통해 구현(각 노드의 대표번호)
//Union Find
#include <iostream>
#include <vector>
#define NUM 7
using namespace std;
vector<int> root;
void Init(int n){
root.resize(n);
for (int i = 1; i < n; i++)
root[i] = i;
}
int Find(int x){
return root[x];
}
void Union(int x, int y){//y를 대표번호로 하는 모든 노드의 대표번호를 모두 x로 설정
int tmp = root[y];
for (int& i : root){
if (i == tmp)
i = root[x];
}
}
int main(){
Init(NUM + 1);
Union(2, 3);
Union(2, 4);
Union(4, 7);
Union(1, 2);
if (Find(1) == Find(7))
cout << "같은 집합에 속해있다." << endl;
else
cout << "다른 집합에 속해있다." << endl;
}



=> 트리의 개념을 통해 구현(각 노드의 루트노드)
//Union Find
#include <iostream>
#include <vector>
#define NUM 7
using namespace std;
vector<int> root;
void Init(int n){
root.resize(n);
for (int i = 1; i < n; i++)
root[i] = i;
}
int Find(int x){//모든 자식노드의 루트를 x로 설정하면서 찾기
if (x == root[x])
return x;
else
return root[x] = Find(root[x]);//경로압축 최적화
}
void Union(int x, int y){
root[Find(y)] = Find(x);//x노드의 자식노드로 y노드를 추가
}
int main(){
Init(NUM + 1);
Union(2, 3);
Union(2, 4);
Union(4, 7);
Union(1, 2);
if (Find(1) == Find(7))
cout << "같은 집합에 속해있다." << endl;
else
cout << "다른 집합에 속해있다." << endl;
}


저작자표시

'알고리즘' 카테고리의 다른 글

BFS(Breadth first search)  (0) 2019.03.08
DFS(Depth First Search)  (0) 2019.03.08
Pseudo code

BFS(v)
    for(i=0;i<n;i++)
        visited[i] = false
    Queue = creaetQueue()
    Visited[v]  = true
    v 방문
    while(not isEmpty(Queue))
        While(visited[v의 인접정점 w] == false)
            Visited[w] = true
            W 방문
            Queue.push(w)
        v = q.pop()



//BFS(인접리스트) 내가 구현한 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
/*7 7 1
1 2
1 3
2 4
2 5
3 6
3 7
6 7
*/
class graph{
public:
int vertex;//정점의 갯수
vector<vector<int>> edge;//간선 목록
vector<bool> visited;//방문 여부
queue<int> q;
graph(int n){
vertex = n;
edge.resize(n + 1);
visited.resize(n + 1, false);
}
void bfs(int v){
cout << v << " ";
visited[v] = true;
q.push(v);
while (!q.empty()){
v = q.front();
for (auto i : edge[v]){
if (!visited[i]){
cout << i << " ";
visited[i] = true;
q.push(i);
}
}
q.pop();
}
}
};
int main(){
int n, m, v, i, a, b;
graph *g;
cin >> n >> m >> v;
g = new graph(n);
for (i = 0; i < m; i++){
cin >> a >> b;
g->edge[a].push_back(b);
g->edge[b].push_back(a);
}
for (i = 1; i <= n; i++)
sort(g->edge[i].begin(), g->edge[i].end());
g->bfs(v);
}


저작자표시

'알고리즘' 카테고리의 다른 글

Union - Find  (0) 2019.03.08
DFS(Depth First Search)  (0) 2019.03.08
Pseudo code

DFS(v)
    for(i=0;i<n;i++)
        visited[i] = false
    Stack = creaetStack()
    Visited[v]  = true
    v 방문
    while(not isEmpty(stack))
        If(visited[v의 인접정점 w] == false)
            push(stack, v)
            visited[w] = true
            w 방문
            v = w
        Else
            v = pop(stack)



인접 리스트(재귀)


//DFS(인접리스트) 내가 구현한 코드 [재귀]
#include <iostream>
#include <vector>
using namespace std;
/*7 7 1
1 2
1 3
2 4
2 5
3 6
3 7
6 7
*/
class graph{
    public:
        int vertex;              //정점의 갯수
        vector<vector<int>> edge; //간선 목록
        vector<bool> visited;    //방문 여부
        graph(int n){
            vertex = n;
            edge.resize(n + 1);
            visited.resize(n + 1, false);
        }
        void dfs(int v){
            cout << v << " ";
            visited[v] = true;
            for (auto i : edge[v]){
                if (!visited[i])
                    dfs(i);
            }
        }
};
int main(){
    int n, m, v, i, a, b;
    graph* g;
    cin >> n >> m >> v;
    g = new graph(n);
    for (i = 0; i < m; i++){
        cin >> a >> b;
        g->edge[a].push_back(b);
        g->edge[b].push_back(a);
    }
    g->dfs(v);
}




인접리스트(스택)


//DFS(인접리스트) 내가 구현한 코드
//O(v+e)
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
/*
7 7 1
1 2
1 3
2 4
2 5
3 6
3 7
6 7
*/
class graph{
    public:
        int size;                //vertex 갯수
        vector<vector<int>> head; //각 vertex에 연결된 vertex들이 저장된 배열 (인접리스트)
        vector<int> visited;     //방문했는지
        graph(int size);
};
graph::graph(int size){
    this->size = size;
    this->head.resize(size + 1);
    this->visited.resize(size + 1, false);
}
void printGraph(graph* g){
    for (int i = 1; i <= g->size; i++){
        cout << i << " : ";
        for (auto j : g->head[i])
            cout << j << " ";
        cout << endl;
    }
}
void dfs(graph* g, int v){
    stack<int> s;
    bool flag;
    s.push(v);
    cout << v << " ";
    g->visited[v] = true;
    while (1){
        flag = true;
        for (auto i : g->head[v]){
            if (!g->visited[i]){ //해당 vertex를 방문 안했다면
                s.push(i);
                cout << i << " ";
                g->visited[i] = true;
                v = i; //해당 vertex의 head에서부터 다시 탐색하겠다는 의미
                flag = false;
                break;
            }
        }
        if (flag){ //flag가 true가 되는경우는 해당 vertex에 연결된 vertex들을 모두 방문했을때 stack에서 pop
            if (!s.empty()){
                v = s.top();
                s.pop();
            }
            else
                break;
        }
    }
    cout << endl;
}
int main(){
    int i, n, m, v, a, b;
    graph* g;
    cin >> n >> m >> v;
    g = new graph(n);
    for (i = 1; i <= m; i++){
        cin >> a >> b;
        g->head[a].push_back(b);
        g->head[b].push_back(a); //방향 연결리스트시 삭제
    }
    for (i = 1; i <= m; i++)
        sort(g->head[i].begin(), g->head[i].end()); //탐색시 오름차순으로 탐색할때 정렬해야함
    printGraph(g);
    dfs(g, v);
}




인접행렬(스택)


//DFS(인접행렬) 내가 구현한 코드
//O(v^2)
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/*
7 7 1
1 2
1 3
2 4
2 5
3 6
3 7
6 7
*/
class graph{
public:
int v;//vertex의 갯수
int **adjArr;//인접 행렬
graph(int v);
};
graph::graph(int v){
this->v = v;
this->adjArr = new int *[v + 1];
for (int i = 0; i < v + 1; i++){
this->adjArr[i] = new int[v + 1];
memset(this->adjArr[i], 0, v + 1);
}
}
void dfs(graph* g, int v){
int i;
stack<int> s;
vector<bool> check;
check.resize(g->v + 1, false);
s.push(v);
check[v] = true;
cout << v << " ";
while (!s.empty()){
v = s.top();
for (i = 1; i < g->v + 1; i++){//방문한 vertex의 모든 vertex을 탐색
if (g->adjArr[v][i] == 1){//방문한 vertex에 연결된 vertex일때
if (check[i] == false){//연결된 vertex가 방문되지 않았을때
s.push(i);
check[i] = true;
cout << i << " ";
v = i; //해당 vertex를 탐색
break;
}
}
}
if (i == g->v + 1)s.pop();//stack의 top에 있는 vertex부터 다시 탐색
}
}
int main(){
int n, m, v, i, a, b;
cin >> n >> m >> v;
graph* g = new graph(n);
for (i = 0; i < m; i++){
cin >> a >> b;
g->adjArr[a][b] = 1;
g->adjArr[b][a] = 1;
}
dfs(g, v);
}


저작자표시

'알고리즘' 카테고리의 다른 글

Union - Find  (0) 2019.03.08
BFS(Breadth first search)  (0) 2019.03.08

+ Recent posts

티스토리툴바