[자료구조] 그래프(DFS,BFS)

그래프

---

• 그래프는 자료구조의 일종이다.
• 정점 ( Node, Vertex ) 과 간선(Edge)으로 이루어져 있다.
• G=(V,E)로 나타낸다.
• 차수는 정점과 연결되어 있는 간선의 개수를 의미한다.

그래프의 표현

---

• 위와같은 그래프는 정점이 6개, 간선이 8개있다.
• 정점 : { 1, 2, 3, 4, 5, 6 }
• 간선 : { (1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5), (4,6) }

인접행렬

• 인접행렬은 정점의 개수를 V라고 했을 때, V x V 크기의 2차원 배열을 사용한다.
• A[i][j] = 1 ( i->j 간선이 있을때 ), 0 (없을때)
• 2차원 배열로 나타낸 A[i][j]

인접 리스트

• 리스트를 이용해서 구현한다.
• A[i] = i와 연결된 정점을 리스트로 포함하고 있다.
• 리스트는 크기를 동적으로 변경할 수 있어야 한다.
• 링크드 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다.
• C++에서는 vector를 사용하면 된다.
• 예시 A[1]  2  5
  A[2]  1  3  4  5
  A[3]  2  4
  A[4]  3  5  2  6
  A[5]  1  2  4
  A[6]  4

간선 리스트

• 간선을 모두 저장하고 있는 배열
• 각 간선의 앞 정점을 기준으로 개수를 센다
• 예시