자료구조와 알고리즘2

그래프는 N:M의 자료를 나타낸다.

• 정점 : Vertex, Node
• 간선 : Edge
• 무방향 그래프, 방향 그래프
• 차수 : Degree,정점에 연결된 간선의 수(방향 그래프의 경우 진입,진출 차수 구분)
• 사이클 : 현재 노드로 돌아올 수 있는 경로가 존재할 때
• 연결 그래프, 비연결 그래프
• 연결 요소

그래프를 표현하는 방법은 인접 행렬과 인접 리스트가 있다.

인접행렬은 두 정점간의 연결관계를 파악할 때 유리하다.

• isConnected(i,j) : O(1)

• adjecentList[] : O(V)

• 공간 복잡도 : V^2

• 무방향 그래프의 경우 대각선을 기준으로 대칭성을 갖는다.

인접리스트는 한 정점에 연결된 다른 정점의 목록을 파악할 때 유리하다.

• adjecentList[] : O(degree(X))
• isConnected(i,j) : O(Min(i,j))
• 공간 복잡도 : V+E, V+2E

그래프의 순회 방법 DFS,BFS

모든 정점과 간선을 살펴봐야 하므로 O(V+E)
방문 체크는 필수이다. 트리와 달리 방문한 곳을 재방문할 여지가 있기 때문이다.

DFS는 깊이 우선 탐색 재귀로 구현하고, BFS는 너비 우선 탐색 Queue로 구현한다.

• 가중치가 없는 그래프에서의 최단 경로는 BFS로 구할 수 있다.

최단경로는 주어진 그래프의 형태와 구하고자 하는 상황에 따라 달라진다.

• 간선의 가중치가 양수이면서, 한 정점에서 다른 모든 정점으로의 최단 거리를 알고자 할 때 : 다익스트라 O(ElogV, V^2)
  - 방문하지 않은 정점 중 가장 가까운 정점을 선택

  • 해당 정점 방문 처리
  • 방문하지 않은 정점 중, 해당 정점에서 갈 수 있는 정점들 중에서 거쳐서 가는 것이 더 이득이면 갱신

• 모든 정점에서 다른 모든정점으로의 최단 거리를 알고자 할 때 : 플로이드 워셜 O(V^3)
  - 2차원 INF 초기화 후, 경유지, 출발지, 도착지의 3중 포문으로 구현한다.

• 간선의 가중치가 음수가 포함되어 있다면 : 벨만포드 O(VE)
  - 아이디어는 다익스트라랑 같은데 모든 정점에 대해서 모든 간선을 확인하며

  • 음수 사이클의 존재 여부를 체크하여야 한다.