백트래킹 -(2) Graph Coloring

The m-coloring problem

adjacent(인접한) 두 vertice가 같은 색이 되지 않도록

최대 m의 다른 색을 사용하여 undirected graph를 색칠하는 모든 방법을 찾는 문제

 

* 지도 문제로 적용될 수 있다.

 

 

public static void m_coloring(index i)
{
    int color ;
    if (promising(i))
        if (i==n)
        	system.out.print( vcolor[1] .. vcolor[n] )
    else
        for (color=1; color<= m; color++) {
            vcolor[i+1] = color;
            m_coloring(i+1) ;
        }
}


public static boolean promising(index i)
{
    index j ; bool switch ;
    switch= true;
    j= 1 ;
    while ( j < i&& switch ) {
        if ( W[i][j] && vcolor[i] == vcolor[j] )
            switch= false ;
        j++ ;
	}
    return switch;
}