가장자리 목록을 사용하여 일련의 정점을 개별 구성 요소로 분할하는 방법이 필요합니다. 프로그램이 입력되게되면가장자리 목록을 사용하여 그래프 그리기
예를 들어,
2,3-
1,5-
3,4-
4,2
I가 필요 1과 5가 연결되어 있지 않으므로 2, 3, 4와는 별도의 구조로 배치하십시오.
모든 정점을 인접 목록에 넣는 것이 좋습니까? 그렇다면 분할 방법을 결정하는 방법은 무엇입니까?
또한 꼭지점 수와 가장자리 수는 모두 알려져 있지만 가변적이라는 점을 명심하십시오.
정확하게 이해했다면 깊이 우선 검색과 같은 것을 사용할 수 있습니다. 어떤 지점에 올 때 색인 0으로 표시합니다 (예 :). 연결된 구조의 모든 지점을 통과 한 것으로 보이는 경우 (검색 완료) 표시되지 않은 지점이 있는지 확인하기 위해 지점 배열을 반복하여 시작하므로 깊이 우선 검색을 시작하십시오. 그 시점에서 1 ... 으로 모든 점을 표시하면 점의 배열을 분석하고 그 중 일부는 0으로 표시되고 일부는 1, 일부는 2 표시가 있음을 볼 수 있습니다. 0,1,2를 가지면 3 개의 분리 된 구조를가집니다.
희망이있었습니다.
ohhhh ... 그건 실제로 꽤 영리합니다! 그리고 그렇게하면 어떤 점이 어떤 구조에 있는지도 알 수 있습니다. DFS를 실행하는 방법을 보여줄 수 있습니까? – user2203239
늦게 답변 해 주셔서 죄송합니다. 이력에 대한 설명은 개념을 설명하는 링크입니다 : http://algs4.cs.princeton.edu/41undirected/DepthFirstSearch.java.html – rshmelev
연결이 끊어진 그래프와 다른 점은 무엇입니까? 나는 이것을 위해 별도의 구조가 필요 없다고 생각한다. – greedybuddha
구조체가 필요할 경우, 인접 행렬을 찾는다. –
아마도 내 질문에 명확하지 않았습니다. 나는 입력을 받고 목록이나 행렬에 저장하는 데 아무런 문제가 없다. 하나의 꼭지점이 다른 꼭지점에 연결되어 있는지 여부를 확인하기 위해 깊이 우선 검색을 사용하는 방법을 알아야합니다. 그래서 만약 내가 2, 3, 3, 4, 5, 나는 2가 3과 4에 연결되어 있지만 1이나 5가 아니라는 것을 알 필요가있다. 누군가가 아이디어를 가지고 있다면 코드에 그것을 크게 두는 것이 좋다. . – user2203239