0
저는 그래프 이론을 처음 접했고, 지금까지 그래프 이론에서 BFS와 디스 조인트 집합 만 배웠습니다. 주어진 무향 연결된 그래프에주기가있는 경우 BFS 을 사용하여 찾을 수 있습니까? 제 의도는 사이클의 모든 정점을 인쇄하는 것입니다. 미리 감사드립니다.BFS는 사이클을 그래프로 찾을 수 있습니까?
A
답변
0
그래프 이론에서는 Circles이 아닌 Cycles라고 불립니다. 노드를 방문한 것으로 표시하고 방문한 노드가 다시 방문하면 순환이라고보고합니다. D.F.S를 사용하는 BW 발견주기가 더 좋습니다. 당신은 http://codes-at-igit.weebly.com/uploads/1/2/2/7/12272842/ideone_0sbcx.cpp
예 http://stackoverflow.com/questions/4464336/pseudocode-to-find-cycles-in-a-graph-using-breadth-first-search, 그것은 원이 아니다 여기에 코드를 찾을 수 있습니다 , 그래프의 사이클이라고합니다 : P –
죄송합니다. 사이클을 의미합니다. 나는 그것을 바로 잡았다. –
당신은 유향 그래프를 의미합니까? 그래프가 무 방향이면 두 노드를 연결하는 링크가 하나의 사이클을 형성합니다. 예 : 당신이 A - B를 가졌다면, A - B - A는 순환입니다. –