Bipartite Graph

Bipartite Graph

1. 이분그래프 정의

이분 그래프란 모든Edge(간선)이 U(위쪽의 Vertex)와 V(아래의 Vertex)사이를 잇는 형태의 그래프 이다.

위의 그림과같이 V->V , U->U 로 가는 Edge가 없는 그래프를 말한다.

위의 그림과 같이, 두가지 색만으로 그래프를 색칠 할려고 할때, 같은 Edge 를 사이에둔 Vertex 는 서로 다른색으로 색칠이 가능하다면 이분 그래프임을 알 수 있다.

2. 이분그래프 판별 알고리즘

앞선 정의를 이용해 이분그래프를 판별하는 알고리즘을 프로그래밍 해보았다.

방법은 간단하다. DFS(Depth First Search)를 이용해서 그래프를 탐색하면서 색을 칠해준다.(아래의 코드에서는 1,-1로 색을 칠하였다.)

색을 칠해야하는 Vertex의 Color 가 자신과 같은색깔로 칠해져있으면 false 를 반환한다.

만약 색이 칠해져 있지않다면, 반대색 (현재색을 c 로가졍하였을때 -c)를 칠해준다.

정상적으로 색이 다칠해지고 true 를 반환하면 이분그래프임을 확인할수 있다.

#define MAXV 20001      //MAX_VERTEX_COUNT

vector<int> Graph[MAXV];  //Graph
int Color[MAXV];            //Color
bool DFS(int v, int c) {
    Color[v] = c;
    for (int i = 0; i < G[v].size(); i++){
        if (Color[Graph[v][i]] == c){
            return false;
        }
        if (Color[Graph[v][i]] == 0 && !DFS(Graph[v][i], (~c)+1)){
            return false;
        }
    }
    return true;
}
void isBipartiteGraph() {
    int V, E;           //Vertex, Edge
    bool isBipartite = true;
    for (int i = 0; i < V; i++){
        if (C[i] == 0){
            if (!DFS(i, 1)){
                isBipartite = false;
                break;
            }
        }
    }
        if (isBipartite == true){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
}

아래의 사이트는 이분그래프를 판별하는 문제이다.

https://www.acmicpc.net/problem/1707

Copyright (C) 2016 (DaeHyun, Hwang) all rights reserved.

hava

Add Comment

Graph

2016년 4월 30일 토요일

Share

Like

G+

Tweet

Tweet

Related Posts

• Dijkstra Algorithm Dijkstra Algorithm 앞서 소개한 벨만포드보다 향상된 기법(?)의 다익스트라 알고리즘에대해 알아보자. 1. 다익스트라 알고리즘 소개 먼저 다익스트라 알고
• Graph Basic Theory Graph Basic Theory 1.그래프의 정의 그래프란 vertex와 edge로 구성되어 있다. vertex(정점)은 node(노드)와 비슷한 의미이며 보통의
• Bellman-Ford Algorithm Bellman Ford Algoritm 그래프에서 최단경로 탐색 문제에 대한 3가지 알고리즘이있다. Bellman-Ford Algoritm (벨만-포드 알고리즘) Di
• topological sort topological sort 위상정렬(topological sort)이란 일반적인 정렬과는 다르다. 위상정렬은 Graph에서 쓰이는 정렬 기법중 하나이다. 선행 조건