BFS를 사용한 그래프 채색 - 탐욕스러운 채색?

Question

BFS를 사용하여 그래프 색상을 구현할 수 있다고 생각하면 아래에 설명 된 접근 방법을 생각해 냈습니다.

그래도 탐욕스러운 알고리즘처럼 보일 지 모르지만 그게 맞는지 나는 잘 모르겠다. 어떤 전문가의 의견?

colors[MAX_COLORS]; 
colorsUsedSoFar[] = NIL; 
like BFS, color first node u with colors[0] i.e color[u] = colors[0]; 
colorsUsedSoFar[] += colors[0]; 

for each node v adjacent to u{ 
    (if v not already colored){ 
    color[v] = color from the colorsUsedSoFar[] but NotUsedByItsAdjacents 
    If all the colors in colorsUsedSoFar[] are used by adjacents, assign a new color to v) 
    } 
} 

'BFS와 마찬가지로'는 대기열을 사용하고 대기열이 소모 될 때까지 처리하는 것이 었습니다.

Answer 1

이것은 greedy coloring algorithm의 예입니다.

너비가 큰 첫 번째 검색 (BFS)은 암시 적으로 순서를 선택합니다.

알고리즘은 정확하지만 항상 최적의 색상 (예 : 사용되는 색상 수가 가장 적음)을 제공하지는 않습니다.

더 일반적인 순서는 Welsh–Powell algorithm으로 알려진 정도에 따라 꼭지점을 정렬하는 것입니다.

Answer 2

만약 당신이 알고리즘을 BFS 순서로 그래프에 색칠하고 싶다면 for 루프 내부에 색을 칠한 후에 노드를 큐에 추가하지 않았다는 것을 제외하고는 알고리즘이 완벽하게 괜찮다고 생각합니다. 그리고 그것은 또한 욕심 많은 접근법의 한 종류입니다. 당신은 탐욕스럽게 레벨에 따라 첫 번째 노드를 선택합니다. 욕심이 많지는 않지만 좀 그렇습니다.