210914. Graph1

sylph0105·2021년 9월 21일
0

With Codestates

목록 보기
104/114
post-thumbnail

공부시간 : 19:30 ~ 22:00

오늘의 공부
[자료구조/알고리즘] 자료구조 기초 : Graph

💡 Graph

💜 Graph 개념

  • 여러 개의 점들이 서로 복잡하게 연결되어 있는 연결 데이터를 저장할 수 있는 자료구조
  • 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선으로 연결되며, 간접적인 관계가 있는 경우 몇 개의 점과 선을 통해 연결됨
  • 그래프에서는 하나의 점을 정점(vertex/node)라고 표현하고, 하나의 선을 간선(edge)라고 표현함
  • 주로 네비게이션, 사회연결망(SNS), 포털사이트 검색엔진에서 주로 사용하는 자료구조가 그래프

💜 Graph 용어

🤍 정점(node)

  • 그래프에서 하나의 데이터 단위를 나타내는 객체

🤍 간선(edge)

  • 그래프에서 두 정점의 직접적인 연결 관계 데이터

🤍 인접

  • 두 정점 간에 간선이 직접 이어져 있는 것을 '인접'이라고 표현

🤍 경로

  • 한 정점에서 다른 정점까지 가는 길로 즉, 정점들을 잇는 간선들을 '경로'라고 함
  • 무가중치 그래프(=비가중치 그래프)에서 경로의 거리는 간선의 수로 표현하지만, 가중치 그래프에서 경로의 거리는 한 경로에 있는 간선의 가중치의 합으로 표현
  • 두 정점 사이의 가장 짧은 경로를 '최단 경로'라고 표현

🤍 가중치 그래프

  • 무가중치 그래프(=비가중치 그래프)의 경우 거리는 단순하게 경로에 있는 간선의 수를 의미
  • 가중치 그래프의 경우 거리는 경로 내에 있는 모든 간선의 가중치들의 합을 의미

🤍 사이클

  • 한 정점에서 출발하여 다시 해당 정점에서 끝나는 경로를 '사이클'이라고 표현

🤍 차수

  • 한 정점이 가지고 있는 간선의 수를 '차수'라고 표현
  • 진입차수(in-degree)와 진출차수(out-degree)로 나눌 수 있음

🤍 무방향 그래프

  • 무방향 그래프의 예시로는 친구관계가 있음
  • 정점을 잇는 간선을 화살표가 없는 직선으로 표현
  • 그래프의 특정 경로를 읽을 때에도 정점의 순서 상관없이 읽으면 됨

🤍 방향 그래프

  • 방향 그래프의 예시로는 SNS 팔로우가 있음
  • 정점을 잇는 간선을 화살표가 있는 직선으로 표현
  • 방향 그래프에서는 간선이 떠나는 정점의 순서를 앞에, 간선이 들어가는 정점의 순서를 뒤로 하여 읽으면 됨
  • 방향이 있다해도 쌍방향 가능(순방향과 역방향인 간선들을 만들면 됨)

📌 무방향 그래프와 방향 그래프의 차이점

  1. 경로
    : 방향 그래프에서는 경로에도 방향이 있음
  2. 간선의 차수
    : 방향 그래프에서는 차수를 출력 차수와 입력 차수, 이렇게 2개로 나눔
profile
Connecting the dots

0개의 댓글