C++ 무향 그래프

Question

지난 몇 일 동안이 주제에 대해 많은 내용을 검색해 보았습니다. 무게를 가지지 않고 어떻게 방향이없는 그래프를 만들 수 있는지 이해할 수 없습니다. 아무도 내가 사용하는 구조와 간단한 알고리즘을 말해 줄 수 있습니까? 미리 감사드립니다 !!!

Answer 1

가장자리에 가중치를주는 특정 요구 사항은 없습니다. 인접 행렬에는 노드 간 연결을 지정하는 바이너리 항목 1-0 또는 true-false가있을 수 있습니다. 모든 그래프 알고리즘은 정상적으로 적용됩니다. 그래프에 대한

매우 유용한 강의 : P.R.s의 대답에 약간의 동화에서 http://www.youtube.com/watch?v=ylWAB6CMYiY

Answer 2

. 표준 행렬 표현은 상단 (북동쪽)이 위에서 아래로 (B에서 A), 왼쪽에서 위로 (남서쪽, 아무도 없음)로 쉽게 해석 될 수 있습니다. 어느 위치 (내부적으로는 boolean)의 1은 비 중량 접속을 나타냅니다.

x A B C D 
A 0 1 0 0 
B 0 0 1 1 
C 0 0 0 1 
D 0 0 0 0 

A는 아무 노드에도 연결되어 있지 않다는 것을 암시합니다. B는 A에 연결됩니다. C는 B에 연결됩니다. D는 B와 C에 연결됩니다.

이 예에서는 B가 자식 인 B와 C, A가 B의 자식 인 루트로 D가있는 트리를 만듭니다. 그리고 C leafs.

unweighted 속성은 실제로 많은 것을 단순화하지 않습니다. 오직 순수한 포인터 구현 운동에서,하지만 그것은 매우 의미가 FAPP입니다. 이 adjacency matrix 대신 adjacency list을 사용하면 메모리 사용상의 이점을 얻을 수 있습니다.