자료 구조 - 비선형 자료 구조 (그래프)

참고 링크

i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조를 의미

그래프

점들, 그리고 점들을 연결하는 선들만 이루어진 형태

이때 점을 정점(vertex), 선을 간선(edge)이라고 부름

인접 행렬 :  O(v*e)

인접 리스트 : O(v+e)

관련 용어

• 정점(Vertex)
  • 연결점, 여러 가지 특성을 가질 수 있는 객체
  • 어떤 객체도 정점이 될 수 있음
  • 고립 정점
    • 간선이 하나도 연결되지 않은 외톨이 정점
• 간선(Edge)
  • 두 정점을 연결하는 연결선, 두 정점간의 관계
  • 단방향 간선
    • 단방향으로만 이동 가능한 간선. 이동이 가능한 방향으로 화살표를 그림
  • 양방향 간선
    • 양방향으로 모두 이동이 가능한 간선이다. 양쪽 화살표를 사용해도 되지만, 양방향 그래프에서는 모든 간선이 양방향 간선이므로 화살표 대신 선분으로 표현
  • 자가 간선
    • 자기 자신을 연결하는 간선
  • 다중 간선
    • 동일한 다른 접점과 여러 간선이 연결되는 간선이다.
• 인접
  • 두 정점이 하나의 간선으로 연결되어 있을 때 두 정점이 인접하다고 한다.
• 차수(Degree)
  •  정점에 연결된 간선의 수
  • 진입 차수
    • 정점으로 들어오는 간선의 수
  • 진출 차수
    • 정점에서 나가는 간선의 수
• 경로(Path)
  • 어떤 한 정점에서 다른 하나의 정점으로 가는 다른 길
  • 두 정점이 반드시 다를 필요는 없다.
  • 길이(Length)
    • 어떤 경로에서 시작 정점에서 도착 정점까지 거쳐야 하는 정점의 수
  • 단순 경로
    • 경로에서 시작, 끝 정점을 제외한 방문하는 모든 점이 서로 다른 경로
      • 사이클(Cycle)
        • 시작 정점과 끝 정점이 같은 단순 경로
        • 재귀 사이클
          • 간선 하나만으로 이루어진 사이클
• 부분 그래프(Sub Graph)
  • 그래프를 구성하는 정점들을 임의로 선택한 후 그 정점을 연결했던 간선들로 선택한 정점을 연결한 그래프를 말함

종류

크게 두 구성요소 정점과 간선의 차이

• 단순 그래프
  • 임의의 두 정점 사이에 간선이 최대 하나 있는 그래프
• 다중 그래프
  • 임의의 두 정점 사이에 여러 개의 간선을 허용하는 그래프
• 의사 그래프
  • 다중 그래프이면서 사이클을 허용하는 그래프
• 양방향(무향) 그래프
  • 연결된 두 정점의 순서를 바꾸어도 같은 간선이 되는 그래프, 즉 양방향으로 통행이 가능한 그래프.
• 단방향(유향) 그래프
  • 일반통행만 가능한 그래프
• 연결 그래프
  • 임의의 두 정점 사이에 반드시 경로가 존재하는 그래프
  • 완전 그래프
    • 모든 정점이 서로 간선으로 양방향 연결되어 있는 그래프
• 가중치 그래프
  • 간선에 가중치가 부여된 그래프

그래프 순회 알고리즘

깊이 우선 탐색 (DFS ; Depth First Search)

방문한 정점으로 부터 깊게 들어가며, 쭉 탐색한 후 되돌아 나오다가 아직 탐색하지 않은 노드를 탐색하는 방식

실행 과정

1. 첫 정점을 방문한다.
2. 인접한 정점 중 아직 방문하지 않은 정점을 방문한다(한 길로 쭉 파고 들어간다).
3. 더 이상 들어갈 길이 없을 때(인접한 모든 정점이 이미 방문한 정점일 때), 방문하지 않은 인접한 정점을 찾을 때까지 들어간 길을 돌아나온다.
4. 위 과정을 반복한다.

너비 우선 탐색 (BFS ; Breadth First Search)

넓게 퍼져가며 정점을 방문

실행 과정

1. 첫 정점을 방문한다.
2. 아직 방문하지 않은 인접한 정점들을 큐에 넣는다.
3. 큐에 있는 정점들을 순서대로 방문한다.
4. 큐에 있는 정점에 대해 인접하면서 아직 방문하지 않은 정점들로 새로운 큐를 구성한다.
5. 위 과정을 반복한다.