Ford (1) 썸네일형 리스트형 6. 그래프 1. 그래프 표현법 - 무방향, 비가중치 인접행렬 희소그래프가 아닌 경우에 주로 사용된다. (희소 그래프일 경우 탐색에 불필요한 자원이 낭비된다.) 정점이 서로 연결된 경우 1로 표시하고 그렇지 않은 경우 0으로 표시한다. 장점으로는 구현이 간단하고 연결을 확인하는데에 O(1)의 시간복잡도만 필요하다. (1과 2의 연결확인은 length[1][2]의 값을 확인하면 됨.) 단점으로는 특정 노드에 연결된 모든 노드 n개를 방문하기 위해서 O(n)의 시간 복잡도가 필요하다. 그렇기에 위에서 말한 희소그래프가 아닌 경우에 주로 사용된다. 예를들어 노드가 1억개이고 간선이 두개 뿐인 희소그래프를 고려해보면, 특정 노드에 연결된 노드가 무엇인지 찾기 위해 1억번의 탐색이 필요하다. class Graph{ priva.. 이전 1 다음
