그래프

그래프

목차
1.그래프란
2.그래프 용어
3.그래프 구현 방법
4.그래프 종류
4.그래프 탐색

그래프란

---

• 정점과 간선으로 이루어진 자료구조.
• 트리는 그래프의 일종이다.
• 네트워크 모델이다.
  • 객체와 이에 대한 관계를 나타낸다.
  • 예) 지하철, 도로 등.
• 그래프의 순회방식 : BFS, DFS

그래프 용어

---

• 정점 : 노드로서 정점에는 데이터가 저장.
• 간선 : 링크라고 불리우며 노드간 관계를 나타냄.
• 인접 정점 : 간선에 의해 연결된 정점.
• 단순 경로 : 경로 중 반복적으로 탐색하는 정점이 없는 경로. 즉 같은 간선을 지나지 않는 경로.
• 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수 : 방향 그래프에서 사용되는 용어로서 한 노드에서 외부로 향하는 간선의 수를 의미.
  • 진출 차수 : 방향 그래프에서 사용되는 용어로서 외부 노드에서 노드로 들어오는 간선의 수를 의미.

그래프 구현 방법

---

• 인접행렬
  

  

  • 그래프의 노드들을 행과 열로 표현한 2차원 배열로 만든 것.
  • 장점
    • 2차원 배열 안에 모든 정점들의 간선 정보를 가지고 있으므로 행과 열안에 정점을 표시하면 두 점에 대한 연관 정보를 조회할 수 있으므로 시간 복잡도 O(1)를 갖는다.
    • 구현이 매우 직관적이고 한눈에 파악하기 용이하다.
  • 단점
    • 모든 정점에 대한 간선의 정보들을 대입해야 하므로 O(노드의 개수의^2)의 시간복잡도를 갖는다.
    • 정점은 많지만 간선의 개수가 적을 때 메모리 측면에서 비효율적인 측면을 갖는다.

• 인접리스트
  

  

  • 그래프의 각 노드와 연결된 노드들을 리스트로 표현한 것.
  • 장점
    • 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능하다.
    • 정점이 많지만 간선의 개수가 적을 때 메모리 측면에서 좋다.
  • 단점
    • 특정 두 점이 연결되었는지 확인하기 위해 모든 정점을 뒤져봐야 하는 단점이 있다.

그래프 종류

---

• 무방향 그래프 : 두 정점을 연결하는 간선의 바향이 없는 그래프
  • 인접행렬 : [i][j],[j][i] 는 둘다 연결됨.
  • 인접리스트 : list.get(i)에 j가 존재하고, list.get(j)에 i가 존재.
• 방향 그래프 : 두 정점을 연결하는 간선에 방향이 존재하는 그래프.
  • 단 간선의 방향으로만 이동가능하다.
• 가중치 그래프
  • 간선에 가중치(힘)가 있는 것으로서 두 정점을 지나기 위한 비용을 표현한 그래프.
• 완전 그래프
  • 모든 정점들끼리 간선으로 연결되어 있는 그래프

그래프 탐색

• DFS

  • 갈 수 있는 최대한 깊이 간 다음, 갈곳이 없다면 이전 점점으로 돌아가면서 다시 순회할 곳을 찾는 방법.
  • 재귀 방식

• BFS

  • 시작정점에서 인접한 노드들을 방문한 후 인접한 노드들 다음 깊이에 있는 정점을 순회하는 방식.
  • 큐