이것은 인터뷰에서 묻는 질문입니다.방향이 지정되지 않은 그래프를 빨간색 또는 검정색으로 색칠 할 수 있는지 여부를 결정하는 방법
면접관은 내 솔루션이 올바른지 주장 나를 원하고 내가 단순히 동결
O(|V| + |E|)에서 실행됩니다.
이 간단하지 왜 같이보다 구체적으로, 고려 다음 subquestions :
어떤 상황에서, 대답은 우리가 할 수없는, 아니 될 것입니다.
선호되는 BFS 또는 DFS는 무엇입니까?
그래프가 흐트러지지 않습니까? 내가 앞뒤로 여행 할 수 있기 때문에, 심지어 짝수 노드의주기가 있다면, 우리는 그렇게 할 수없는 것 같습니다, IMO.
이 속성이있는 그래프는 bipartite graph라고하고 그래프가 양자 인 경우 테스트하는 데 사용할 수있는 좋은 알고리즘의 몇 가지 있습니다.
두 부분 그래프에 대한 핵심 정리는 홀수 길이의 사이클을 포함하지 않는 경우에만 그래프가 두 부분으로 나뉜다는 것입니다. 이 정리는 정말 유용합니다. 노드를 다시 방문하게되면 본인에게 중요한지 여부를 결정할 수 있기 때문입니다. 홀수 길이의 사이클이 닫히는 경우, 그래프가 이원적이지 않고 완료되었다는 사실을 알게됩니다. 그렇지 않으면 짝수 - 길이주기를 닫으면 무시하고 계속 진행할 수 있습니다.
이를 바탕으로 그래프의 DFS 또는 BFS를 약간 수정하여 그래프가 이원적인지 여부를 확인할 수 있습니다. 첫째, 검색 할 때의 깊이를 추적하십시오. 모든 노드를 짝수 레벨로 표시하고 모든 노드를 홀수 레벨에 검정으로 표시하십시오. 탐색을 수행 할 때 노드에 색상을 지정하고 이웃 중 하나에 이미 동일한 색상이 지정된 것을 알게되면 홀수 길이의 사이클이 생기며 색상이 없음을보고 할 수 있습니다 (이유는 무엇입니까?). 이것이 결코 발생하지 않는다면, 당신은 각 노드를 같은 색의 두 인접 노드가없는 빨간색이나 검은 색으로 채색했습니다. 그러면 끝났습니다!
노드 당 일정한 양의 작업을 BFS 또는 DFS에 추가하므로 런타임의 그래프 크기가 선형이됩니다. 원하는 검색 알고리즘을 선택할 수 있습니다. 선택의 절충은 메모리 사용 등과 같은 다른 요인에 달려 있습니다.
가치가있는 점에 대해 bipartite 그래프는 매우 유명하고 유용한 그래프 클래스이며 미래에 읽을 가치가 있습니다. 그들은 멋진 속성과 멋진 응용 프로그램 톤 있습니다!