끄적끄적 개발 블로그입니다.

2 분 소요

그래프

그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

  • 그래프는 아이템(사물 또는 추삭적 개념)들과 이들 사이의 연결 관계를 표현한다.

  • 정점(Vertex)

    그래프의 구성요소로 하나의 연결점

    노드node라고도 한다. ➡ 데이터가 저장되는 그래프의 기본 원소

  • 간선(Edge)

    두 정점을 연결하는 선

  • 차수(Degree)

    정점에 연결된 간선의 수

  • 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구선된 자료 구조

    • V: 정점의 개수 E:그래프에 포함된 간선의 개수

      V개의 정점을 가지고 있는 그래프는 최대 V*(V-1)/2 간선이 가능

      ex) 5개 정점이 있는 그래프의 최대 간선 수는 10(=>5*4/2)개 이다.

  • 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N관계를 가지는 원소를 표현하기에 용이하다.

그래프의 종류

  • 무향 그래프(Undirected Graph)

    image-20240626093028895

  • 유향 그래프(Directed Graph)

    image-20240626093246666

  • 가중치 그래프(Weighted Graph)

    image-20240626093113529

  • 사이클 없는 방향 그래프(DAG, Diredcted Acydic Graph)

    image-20240626093300422

  • 완전 그래프

    정점들에 대해 가능한 모든 간선들을 가진 그래프

    image-20240626093353680

  • 부분 그래프

    원래 그래프에서 일부의 정점이나 간섬을 제외한 그래프

트리도 그래프이다.

  • 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
  • 각 노드는 자식 노드가 없거나 하나 이상의 존재할 수 있다.
  • 두 노드 사이에는 유일한 경로가 존재한다.

그래프의 특징

  • 인접(Adjacency)

    • 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.

    • 완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.

      image-20240626201135126

  • 경로(path)란 어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것
    • 같은 정점을 거치지 않는 간성들의 sequence
    • 어떤 정점에서 다른 정점으로 가는 경로는 여러가지 알 수 있다.

  • 사이클(Cyde)

    • 경로의 시작 정점과 끝 정점이같음
    • 시작한 정점에서 끝나는 경로

간선리스트

  • 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장
  • 간선을 표현하는 두 정점의 정보를 나타냄(시작 정점, 끝 정점)

image-20240626131613170

그래프 탐색(순회)

그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(점점)을 빠짐없이 탐색하는 것을 의미한다.

  • 방법
    • 너비 우선 탐색(Breadth First Search, BFS)
    • 깊이 우선 탐색(Depth First Search, DFS)

너비 우선 탐색

너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

알고리즘의 개요은 시작점을 큐(queue)에 넣은 뒤에, 큐에 아무런 요소가 없을 때까지 인접한 정점들을 탐색해 나아가며 진행

인접한 정점들을 보는 과정에서 시간 복잡도 차이가 발생

  • 시간복잡도

    • 인접행렬

      O(V2)

    • 인접 리스트

      O(V+E)

동작 과정

image-20240626201705362

  1. 시작점인 1을 큐에 넣고 방문처리를 한다.
  2. 1을 꺼내고 인접한 정점인 2, 3, 8을 큐에 넣고 방문처리를 한다.
  3. 큐에서 2를 꺼내고 방문하지 않은 7을 꺼내서 방문처리
  4. 큐에서 3을 꺼내고 방문하지 않은 4,5를 꺼내서 방문처리
  5. 위와 같이 큐에서 더이상 꺼낼 것이 없을때까지 반복
  • 최단거리 문제에서 너비우선탐색 사용하기

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

그래프의 시작점에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색한다.

알고리즘의 개요는 시작점에서 시작점에 연결된 정점 그 정점에 연결된 정점 과 같은 식으로 재귀 혹은 스택을 통해 탐색을 수행하고 더 이상 연결된 간선이 없을 때까지 탐색하면 다시 되돌아가 연결된 정점을 탐색한다.

시간복잡도

  • 인접행렬

    O(V2)

  • 인접 리스트

    O(V+E)

인접행렬 방식은 모든 관계를 저장해서 노드가 많을 수록 메모리가 낭비된다.

메모리 효율: 인접리스트 > 인접행렬

조회속도: 인접리스트 < 인접행렬

동작과정

image-20240626202208845

  1. 시작점인 1번 노드를 스택에 넣고 방문처리
  2. 스택 최상단 노드(1)와 미방문한 노드중 가장 번호가 낮은 2넣고 방문처리
  3. 스택 최상단 노드(2)와 미방문한 노드(7)를 스택에 넣고 방문처리
  4. 스택 최상단 노드(7번)와 미방문한 노드 중 가장 번호가 낮은 6번 넣고 방문처리
  5. 스택 최상단 노드(6번)와 미방문한 노드가 없을때는 추출(pop)
  6. 스택 최상단 노드(7번)와 미방문한 노드(8번)를 스택에 넣고 방문처리
  7. 이와같은 메커니즘으로 스택에 아무것도 없을때까지 반복

재귀함수

재귀함수는 자기 자신을 다시 호출하는 함수

재귀함수를 작성할 때에는 반드시 종료 조건을 만들어서 함수를 작성해야한다.

종료조건을 제대로 명시하지 않으면, 함수가 무한이 호출된다.

업데이트:

댓글남기기

참고