우회 가중 그래프 구현

Question

무 지향성 가중 그래프를 구현하는 효율적인 방법을 알고 싶습니다. Prim과 Kruskal 알고리즘을 수행하고 싶습니다. 나는 인접성 목록에 대해 알고 있지만 낭비하지는 않을 것입니다. 예를 들면. 나는 'X'무게 가장자리가 두 꼭지점 A와 B를 가정 해 연결 한 수 있습니다, 그래서 인접 목록에 두 개의 항목을 추가해야합니다 :

A,B,x 
B,A,x 

내가 실종 무엇인가?

Answer 1

인접 목록은 인접 행렬이 아닌 그래프를 구현하는 메모리 효율적인 방법입니다.

실제로 두 가지 옵션이 있습니다.

• 시간과 메모리를 줄이려면 작성한 것을해야합니다.
• 더 많은 시간과 메모리를 원한다면 가장자리를 구현할 수 있습니다. A,B,x 여기서 A>B. 그러나 어떤 정점의 인접 정점을 얻는 동안 많은 시간을 소비하게됩니다.

전화 해주세요. 하지만 수백만 개 미만의 노드를 다루는 경우에는 두 번째 글 머리 기호를 사용하지 않는 것이 좋습니다.

Answer 2

그래프 방향성 때문에 나는 당신이 노드 A와 B

사이에만 하나 가장자리를해야합니다 생각