[알고리즘 스터디 with 케이시] 비선형 자료구조 - 그래프

[알고리즘 스터디 with 케이시] 비선형 자료구조 - 그래프

정의

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
• 정점 집합과 간선 집합으로 표현할 수 있다.

사용처

• 지하철 노선도
• 페이지 랭크 알고리즘(구글 검색 알고리즘)

특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

무방향 그래프

간선의 방향이 존재하지 않는 그래프
-> 양방향으로 이동이 가능

• [A - B]
  • A to B : (A,B)
  • B to A : (B,A)
  • 위 둘은 같은 간선

방향 그래프

간선의 방향성이 존재하는 그래프
-> 일방 통행이다.

• [A - B]
  • A to B : <A,B>
  • B to A : <B,A>
  • 위 둘은 서로 다른 간선

연결 상태에 따른 분류 3가지

1. 연결 그래프: 모든 정점이 서로 이동 가능 상태인 그래프
2. 비연결 그래프: 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
3. 완전 그래프: 모든 정점끼리 연결된 상태인 그래프

한 정점의 간선 수 == 모든 정점의 수 - 1
모든 간선의 수 == (모든 정점의 수 - 1) * 정점 수
모든 간선 수 == 한 정점의 간선 수 * 정점의 수

1.  

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

그래프의 구현 방법

• 인접 행렬(Adjacency Matrix)
  • 이차원 배열로 구현 가능
• 인접 리스트(Adjacency List)
  • 연결 리스트로 구현 가능