[자료구조]그래프란

그래프란

• 정점끼리의 연결을 나타내는 자료구조이다.
• 정점과 간선으로 이루어져 있다.
  • 정점(vertex): data를 표현하는 단위(node)
  • 간선(edge): data 끼리의 연결을 나타내는 선

• vertex는 총 6개이고
• edge는 총 8개의 간선이 있다.

 

 

그래프와 트리의 차이점

• 트리와 그래프 둘 다 정점끼리의 연결구조를 가지고 있다.
• 하지만 cycle의 유무에 따라 그리고 계층적인 구조를 가지냐에 따라 나뉜다.
• 그래프(graph)
  • cycle을 가짐
  • 계층 구조를 가지지 않음
  • → 오로지 정점끼리의 연결만 나타낸다.
• 트리(tree)
  • cycle을 가지지 않음
  • 계층 구조를 가지고 있음
  • → root로부터 다른 정점들이 계층적임

 

cycle이란

• if vertex의 집합을 {v1,v2,v3,v4,v5,v6}가 있다면
• 특정 정점 vi에서 시작해서 다시 vi로 돌아오는 경로(path)가 있을 시
• → 그 경로를 cycle이라고 부른다.

• 이 그림에서 다양한 cycle이 있지만 한가지 예를 들어보면
  • path : 0 → 4 → 2 → 1 → 0 이 있다.

 

그래프를 나타내는 방법

1. 인접행렬(배열로 표현)
2. 인접리스트(연결리스트로 표현)

인접행렬

인접리스트

 

 

 

그래프의 종류

• 무방향 그래프: 간선의 방향이 없는 그래프

• 방향 그래프: 간선의 방향이 있는 그래프

 

 

 

그래프의 용어 정리

• 정점(vertex)
• 간선(edge)
• path: 특정 정점에서 시작해서 특정 정점까지의 루트
• ex) path : 0 → 4 → 2 → 1 → 0
• cycle
• 차수(degree) : 어떤 정점에 연결되어 있는 간선의 수

방향그래프에서의 차수

1. 진입 차수: 정점에 들어오는 방향의 간선의 수
2. 진출차수: 정점이 나가는 방향의 간선의 수

• 진입 차수 진출 차수 확인하는 법
  • vertex 1을 보자 그림으로 보면 진입차수는 2 진출 차수는 1인걸 알 수 있다.
  • 인접행렬을 보면 1행을 보면 연결되어있는 수가 진출 차수이고
  • 인접행렬의 1열을 보면 연결되어있는 수가 진입차수이다.
  • 진출차수

• 진입차수