[자료구조] 그래프

그래프(Graph)

사물을 정점(Vertex)와 간선(Edge)로 나타내기 위한 도구

이미지 출처 : Wikipedia

이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤 형태임

• 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용
• 인접 리스트(Adjacency List) : 리트스를 사용

 

• 무방향 그래프 : 모든 간선이 방향성을 가지지 않는 그래프
• 비가중치 그래프 : 모든 간선에 가중치가 없는 그래프. 연결되어 있는 상황을 인접 행렬로 출력할 수 있음
• 방향 그래프 : 모든 간선이 방향을 가짐
• 가중치 그래프 : 모든 간선에 가중치가 있음

 

그래프 개념과 구현

• 인접 행렬은 모든 정점들의 연결 여부를 저장하여 O(V2)의 공간을 요구하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간을 요구함
• 인접 리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하므로 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(V)의 시간이 필요

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수