그래프 표현 방법 간단한 정리

그래프(Graph)

정점과 간선의 집합으로 구성되는 자료구조

 

 

방향 그래프

• 간선에 방향이 있는 그래프
• A정점에서 B정점으로 향하는 간선과 B정점에서 A정점으로 향하는 간선이 서로 다를 수있다.

무방향 그래프

• 간선에 방향이 없는 그래프
• A-B를 연결하는 간선이 동일한 간선이다.

가중치 그래프

• 간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프
• 연결된 정점들 간 탐색에 드는 비용이나, 연결 강도 등을 표현

 

 

그래프 표현 방법

인접 행렬

• 일반적으로 2차원 배열을 이용해서 표현
• adj[행][열] = 연결여부(or 가중치)
• 공간 복잡도
  • V개의 정점이 있다면, V*V 만큼의 공간을 사용한다.
• 시간 복잡도
  • 연결관계(가중치) 조회/저장 : O(1)
  • 한 정점에 연결된 모든 간선 조회 : O(V)
  • A와 B를 잇는 간선 존재 여부 확인 : O(1)

인접 리스트

• 간선의 정보를 기반으로 저장하는 방법
• 공간 복잡도
  • V개의 정점, E개의 간선이 있다면 V+E 만큼의 공간을 사용한다.
• 시간 복잡도
  • 연결관계(가중치) 조회/저장 : O(deg(V))
  • 정점에 연결된 모든 간선 조회 : O(deg(V))
  • A와 B를 잇는 간선 존재 여부 확인 : O(min(deg(A), deg(B)))

 

정점의 차수와 성질

이러한 성질은 단방향 그래프일 경우 적용되지 않는다. 이 점을 참고하자 !

출처) 패스트캠퍼스 알고리즘 강의 : 류호석님 강의 자료

 

 

 

 

간단하게 그래프 탐색 알고리즘 문제를 풀기 전에, 그래프 성질에 대해 알아보았다. 이미 알고 있던 내용이지만 복습 겸 정리했다. 그래프에 대해 더 자세히 공부하고 싶다면 아래 글을 읽어보면 좋을 것 같다. 이제 알고리즘 문제를 풀어보자 !

 

https://yozm.wishket.com/magazine/detail/2411/

그래프 알고리즘 종류와 활용 방법 | 요즘IT