그래프에서 가장 강력하게 연결된 구성 요소의 크기를 빠르게 결정하는 방법이 있습니까?그래프 - 강하게 연결된 구성 요소
명백한 접근법은 모든 SCC (두 개의 DFS 호출을 사용하여 수행 할 수 있음)를 결정한 다음이를 반복하면서 최대 값을 취하는 것을 의미합니다.
나는 단지 그 구성 요소의 크기와 유일한 구성 요소의 크기가 필요할 경우 더 나은 접근법이 있어야한다는 것을 확신하지만, 좋은 해결책을 생각할 수는 없습니다. 어떤 아이디어?
감사합니다.
질문에 대한 답변을 드릴까요?
모든 값을 조사하지 않고 세트의 어느 값이 가장 큰지 어떻게 알 수 있습니까?
글쎄, 때로는 가능합니다. 당신이 당신의 세트/스무드에 관한 추가 정보를 가지고 있다면. 나는 모르겠다. 아마도 최대의 접근 방식이 유일하고 동시에 최고 일 것이라고 생각할 것이다. 그러나 나의 직감은 더 좋은 방법이 있어야한다고 말한다. 당신이 절대적으로 이것이 더 빨리 끝날 수 없다고 확신한다면 나는 당신을 믿을 것입니다. –
확실하지 않습니다, 이것은 직관입니다. 리콜하면 하나의 DFS에 구성 요소를 가져 오는 알고리즘이 있습니다. 나는 당신이 한 번의 스캔보다 적은 알고리즘을 발견하게 될지 의심 스럽다. 그래프에 대한 정보가 있으면 게시하고 아마도 뭔가를 생각해 낼 수 있습니다. – Rubys
먼저 Tarjan's algorithm을 사용할 수 있습니다. 두 개가 아닌 하나의 DFS 만 필요합니다. 알고리즘을 명확하게 이해하면 SCC는 DAG를 형성하고이 알고리즘은 역 위상 배열 순서로 SCC를 찾습니다. 따라서 시각적 표현과 같은 그래프에 대한 감각이 있고 상대적으로 큰 SCC가 DAG의 끝에서 발생한다는 것을 알고 있다면 처음 몇 개의 SCC가 발견되면 알고리즘을 중지 할 수 있습니다.
Tarjan과 같은 알고리즘이 선형이며 모든 SCC를 결정하기 위해 매우 작은 상수 오버 헤드가 있으므로 질문에 대한 답을 모르겠다. 왜 이렇게할까요? 또한 구현하기 쉽습니다. – Pinch