[그래프] 그래프의 표현

그래프 : 그래프는 노드와 엣지로 구성된 집합이며, 즉 서로 다른 객체가 연결되어 있다고 생각하면 된다.

https://www.geeksforgeeks.org/applications-of-graph-data-structure/

---

1. 그래프 기초

• 노드 (node) : 독립된 개체로 동그라미로 표현
• 에지 (edge) : 노드와 노드를 연결하는 연결선
• 아크 (arc) : 방향성을 가진 엣지
• 인접 (adjacency) : 정점 v와 정점u에 간선이 있다면, '인접하다'고 한다. 
• 차수 (Degree) : 진입차수(정점으로 들어오는 간선의 수)와 진출차수(정점을 나가는 간선의 수)의 합이다.
• 경로 (path) : 정점에서 다른 정점까지의 경로는 정점의 순서이다. 

2. 그래프 구현

2.1. 인접 리스트 (adjacency list) : 파이썬의 리스트를 이용하여 노드 개수만큼 리스트를 선언하는 방식

•   정점 하나에 인접한 모든 정점을 순서 상관없이 리스트에 저장된다.
•   그래프 구현이 복잡하다.
•   노드와 연결된 에지를 탐색하는데 시간 효율성이 뛰어나다.
•   노드 개수에 상관없이 공간 효율성이 좋아 메모리 초과 문제가 발생되지 않는다.

https://www.javatpoint.com/graph-theory-graph-representations

 

2.2. 인접 행렬 (adjacency matrix) : 2차원 자료구조를 이용하여 노드 중심으로 그래프를 표현하는 방식

•   그래프 구현이 간편하다.
•   두 노드를 연결하는 에지의 여부와 가중치의 값등을 바로 확인할수 있다.
•   노드와 관련된 에지를 탐색할시 N번 방문으로 시간 복잡도가 떨어진다. 
•   하지만 노드의 개수보다 에지가 적은경우 공간 효율성이 떨어진다.

https://www.javatpoint.com/graph-theory-graph-representations

---

2차원 리스트 생성 방법

1. 객체 생성

n = 5
m = 3

A = [[0 for col in range(n)] for row in range(m)]
A
>>> [[0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0]]

2. 얕은 복사

n = 5
m = 3

A = [[0] * n] * m
A
>>> [[0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0]]

 

---

참고서적

Do it! 알고리즘 코딩 테스트: 파이썬 편 (코딩 테스트를 처음 준비하는 취준생의 필독서!)

이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드)