원본 그래프에서 DFS를 실행 한 다음 새 노드가 발견되면 미러의 보조 목록을 생성하여 방향 그래프의 조 변경을 구성하려고합니다.유향 그래프를 조 변경하는 데 드는 비용은 얼마입니까?
이 계산 시간은 어떻게 되나요? DFS는 O (| V | + | E |)를 사용하지만 adjancy 목록을 만드는 것은 어떨까요? DFS를 통해 이항의 보조 목록을 작성하는 데 얼마나 걸리나요?
그래프에 항목을 O (1) 삽입 한 경우 (정점 조회에 해시 테이블 또는 해시 맵을 사용하고 정점이 정수로 표시되는 경우 배열을 사용한다고 가정 할 때) 점근 적 런타임은 DFS.
솔직히 말하면 실제로 DFS를 할 필요가 없다고 생각합니다. 각 꼭지점의 인접 목록을 반복하고 그런 다음 가장자리를 추가 할 수 있다고 생각합니다. 런타임은 여전히 O (V + E)이므로 이론적으로는 별 문제가되지 않습니다.
또한 그래프가 가장자리 목록으로 표시되면 전치 그래프를 O (E)로 만들 것이라고 생각하지만 그래프를 연결해야한다고 생각합니다.
죄송합니다. 거기에 추가 정보가 너무 많으면 도움이 될 수 있기를 바랍니다.
감사합니다 딜란! – fdh
내가 도울 수있어서 기쁩니다! –
은 표준 용어 "미러"입니까? Google은이 q를 첫 번째 히트로 표시합니다. http://en.wikipedia.org/wiki/Glossary_of_graph_theory에 나타나지 않습니다. http://en.wikipedia.org/wiki/Transpose_graph –
@ 예, 전치 그래프가 올바른 용어 일 것입니다. – fdh