그래프(vertex, edge, node, arc)
자세한 내용은 https://blog.encrypted.gg/1016 를 참고하면 좋습니다.
그외 참고 사이트
https://velog.io/@orcasuit/그래프vertex-edge-node-arc
https://velog.io/@ffwang/인접-행렬과-인접-리스트
https://suyeon96.tistory.com/32
위와 같은 것을 우리는 알고리즘에서 그래프라고 합니다. 그림에서도 알 수 있듯이 그래프는 Vertex라는 노드와 Edge라고 불리는 간선의 집합으로 구성됩니다.
관련 용어
- Vertex(정점, 노드): 데이터가 저장되는 그래프의 기본 원소
- Adjacent Vertex(인접 정점): 정점에서 간선으로 직접 연결되어 있는 정점(1번 기준으로 3,2,8임)
- Edge(간선): 링크라고도 하며 정점 간의 관계를 의미(방향성이 없으므로 무방향 그래프의 간선)
- Arc(간선): 정점 간의 방향성있는 관계를 의미, A→B와 B→A는 다르다(방향성이 있으므로 방향 그래프의 간선)
- 가중치: 간선에는 추가적인 가중치가 할당할 수 있다.
- Degree(차수): 정점에 연결된 간선의 수. 위의 1번 기준으로 차수는 3이다.
모든 장점의 차수는 무방향 그래프에서 하나의 간선이 두개의 정점에 인접하므로 간선 수의 2배이다. 즉, 18개
방향 그래프에서는 노드 기준으로 들어오는 간선은 In-Degree(진입차수)이고 나가는 간선은 Out-Degree(진출 차수)이다.
그래프의 종류(이외에도 더 있음)
- 무방향 그래프: 말그대로 정해진 방향이 없는 그래프. 양방향 통행
- 방향 그래프: 정해진 방향이 있는 그래프. 일방 통행. 그렇기 때문에 indegree, outdegree의 개념이 있음.
- 순환 그래프: 한점으로 출발해서 자기 자신으로 돌아올 수 있는 경로를 사이클이라 한다. 그래프 안에 싸이클이 하나라도 있으면 순환 그래프이다.(보통 무방향 그래프는 순환 그래프가 된다)
- 비순환 그래프: 순환 그래프와 반대로 경로상 사이클이 돌지 않는 그래프이다. 방향 그래프를 직접 한 노드에서 전개해보며 자기자신으로 돌아오는지 확인하면된다.
- 완전 그래프: 모든! 서로 다른 두 정점 쌍이 간선으로 연결된 그래프. 즉, 모든 노드가 연결되어 있어야한다.
- 연결 그래프: 임의의 두 정점 사이에 경로가 항상 존재하는 그래프.
- 단순 그래프: 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프. 보통의 모든 그래프.
(서로 꼭 연결되어 있을 필요 X, 간선이 반드시 1개 이하X, 본인이 본인으로 들어가는 간선도 가능(루프))
그래프를 구현하는 방법에는 배열(Array)을 사용하는 인접 행렬 방법과 연결리스트(Linked List)를 사용하는 인접 리스트 방법이 있다.
- 해당 방법 외에도 모든 간선을 하나의 리스트로 표현하는 간선 리스트와 객체 지향 언어에서 각 노드를 객체로 표현하고, 이웃 노드를 포인터나 참조로 연결할 수 있는 객체와 포인터 방법이 있다.
인접 행렬
그래프의 정점과 연결되는 간선을 2차원 배열로 만든 것.
정점의 개수에 따라 V*V의 2차원 배열을 인접 행렬로 사용.
인접 행렬에서 행과 열은 정점을 의미하고, 각각의 원소들은(1, 0) 정점 간 간선 나타낸다.
가중치 그래프라면 원소들에 해당되는 가중치를 입력한다.
무방향 그래프는 0,0을 기준으로 대칭적인 구조를 가집니다.(대각선)왜냐하면, 서로 연결된것이랑 다름없기 때문이다.
그래서 인접 행렬을 쓸때, 무방향 그래프일때 0,0 기준으로 나눠서 공간을 절약할 수 있다.
인접 리스트
그래프의 각 정점에 인접한 정점들을 연결리스트로 표현한 것.
해당 방식은 인접 행렬과 비교했을때, 정점이 많고 간선은 적은, 작은 상황에서 공간을 절약할 수 있는 방식.
경우에 따라 인접 행렬로는 절대 저장이 불가능해서 인접 리스트만 써야하는 경우도 있다.
정점의 개수만큼 인접리스트가 존재한다. 각각의 인접리스트에는 인접한 정점 정보가 저장되는 것이다. (A에는 A와 연결된 노드를 다 연결) 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.
무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드도 추가해야 한다.(당연)
그러면 인접 행렬과 리스트의 장단점, 특징, 차이점을 알아보자
V: 정점, E: 간선
인접 행렬과 리스트의 장단점, 특징, 차이점
파이썬에서는 networkx라는 라이브러리나 리스트와 딕셔너리를 적절히 사용하여 그래프를 쉽게 표현 가능.
#파이썬에서 인접 리스트를 이용한 예시(딕셔너리)
#무방향 그래프
graph1 = {1: [2, 3, 5], 2: [1, 3], 3: [1, 2, 4], 4: [3, 5], 5: [1, 4]}
#방향 그래프
graph2 = {1: [2, 3], 2: [3], 3: [4], 4: [], 5: [1, 4]}
#아래와 같이 딕셔너리 대신 리스트를 이용하여 그래프를 표현가능하다.
#무방향 그래프
graph1 = [[], [2, 3, 5], [1, 3], [1, 2, 4], [3, 5], [1, 4]]
#방향 그래프
graph2 = [[], [2, 3], [3], [4], [], [1, 4]]
#만약 위의 인접 리스트를 인접 행렬로 표현하면 아래와 같이 된다.
# 무방향 그래프 (인접 행렬)
graph1_matrix = [
[0, 1, 1, 0, 1], # 1번 노드
[1, 0, 1, 0, 0], # 2번 노드
[1, 1, 0, 1, 0], # 3번 노드
[0, 0, 1, 0, 1], # 4번 노드
[1, 0, 0, 1, 0] # 5번 노드
]
# 방향 그래프 (인접 행렬)
graph2_matrix = [
[0, 1, 1, 0, 0], # 1번 노드 → 2, 3
[0, 0, 1, 0, 0], # 2번 노드 → 3
[0, 0, 0, 1, 0], # 3번 노드 → 4
[0, 0, 0, 0, 0], # 4번 노드 → 없음
[1, 0, 0, 1, 0] # 5번 노드 → 1, 4
]
# 딕셔너리, set은 서칭이 빠르다.이러한 그래프는 네트워크 디자인, 경로 찾기, 소셜 네트워크(팔로우), 탐색 알고리즘(검색), 작업 스케줄링에서 잘 쓰입니다.
