무 디렉션 그래프 (있는 경우)에서 하나의 사이클을 구성하는 경로의 노드를 반환하는 알고리즘을 생성하려고합니다. 지금까지 탐색 된 노드로 이어지는 발견되지 않은 가장자리에 도달 할 때까지 그래프에서 DFS를 수행하고 있습니다 (그 시점에서 사이클이 있음을 알았습니다). 그러나 어떤 경로가 순환을했는지 어떻게 알 수 있습니까? 내 경로를 기록하기 위해 스택/큐를 사용하면 어떻게 도움이됩니까? 사이클 경로의 일부가 아닌 노드에서 시작한다고 가정 해 봅시다. 나중에 스택/큐에서 꺼내는 방법을 알았습니까?무 방향성 그래프에서 하나의 사이클의 경로를 반환하는 알고리즘
모든 의견을 많이 주시면 감사하겠습니다.
각 노드를 방문했을 때 보낸 노드 인 DFS 레코드를 수행 할 때. 새 노드에 대해 parent이라고합니다. 이제 이미 방문한 노드 v으로 연결되는 가장자리 (u, v)에 도달하면 부모에 의해 만들어진 경로는 u까지 또는 DFS의 소스 (최대 s)까지 올라와야합니다.
항상 둘 중 하나에 도달합니다. s에 도달하면 v에서 동일한 작업을 수행하고주기가 있습니다. u에서 s까지의 경로는 s에서 v까지의 경로와 새 가장자리로 구성됩니다. v에 도달하면 u에서 v까지의 경로와 새 가장자리보다 한주기가 반복됩니다.
@AYR 스스로 연습 해 보시기 바랍니다. 나는 나의 대답이 이것을 위해 충분히 자세하다고 믿는다. –
알고리즘을 올바르게 이해했다면 DFS 자체에 사용 된 스택 이외의 스택을 사용할 필요가 없습니다. – AYR
각 노드에 대해 부모를 스택하려면 추가 배열이 하나 필요합니다. 또한 사이클의 재구성 (''v'' 또는''s'' 경로 재구성)을 위해 하나 이상의 스택을 사용할 것입니다.하지만 당신은 그것도없이 할 수 있습니다. –
당신은 그 일을 할 수 있습니다. 발견 된 노드로 이어지는 발견되지 않은 에지를 때릴 때, 같은 노드로 돌아갈 때까지 가장자리를 따라 뒤로 걷습니다. 교차 한 가장자리와 노드 만 사이클의 일부가됩니다. 그러나,이 방법은 필연적으로 어떤 사이클을 발견 할 것인가? 나는 잘 모르겠다. – pandubear
그렇습니다.하지만 어떻게 "뒤로"걸어 가야합니까? – AYR
만약 당신이 그들을 걸을 때 노드를 추가하면, 그냥 그들을 밖으로 팝업 ... 그렇지 않으면, 당신은 당신이 필요로하는 정보를 보유 할 자신의 유형을 만들 수 있습니다 ... – Noctis