-
그래프(Graph)와 행렬(matrix)알고리즘 2023. 9. 22. 17:09
❓그래프
- Vertex(정점)과 Edge(간선)으로 이루어진 자료구조
- 정점과 정점 사이의 관계를 Edge(간선)으로 표현한다.
좌 : 무방향 그래프 / 우 : 방향 그래프 그래프 구성 요소
- Vertex/Node(정점) : Node 혹은 Vertex 라고 표현하며 그래프에서 각각 지점을 의미한다. (위 그림은 1, 2, 3 등)
- Edge/Link(간선) : Node 와 Node 혹은 Vertex 와 Vertex등 각 정점들을 연결하는 선을 의미한다. (그래프 사이 선)
- Weight(가중치) : 간선을 통해 이동하는데 소요되는 비용등을 표시하는 곳에 사용한다. ( 표기되어 있지 않지만 간선과 간선사이의 비용등을 나타냄 )
- Direction Graph : 방향이 있는 그래프를 의미하고 간선의 방향에 따라 이동만 가능한 경우에 사용된다.
- Undirected Graph : 방향이 없는 무방향 그래프를 의미하고 양방향 이동이 가능한 그래프이다.
- Adjacency : 간선으로 연결된 인접 정점들을 의미한다.
- Degree : 각 정점에 연결된 Edge들의 수를 의미한다. Out-Degree 와 In-Degree로 나뉘며 이 둘의 합을 통해 그 정점에서 Degree를 구할 수 있다. ( 나가는 간선과 들어오는 간선을 뜻한다. )
- Path : 정점 A에서 B로 이동할 수 있는 경로를 의미힌다. 여러 종류의 길이 존재할 수 있으며 길이 존재하면 Reachable 할 수 있다고 표현한다.
Cycle, Self-loop 그래프 - Self-loops : 정점에서 자기 자신으로 돌아오는 간선을 뜻한다. (위 그림에서 4번)
- Simple Path : 경로 상 모든 정점들이 중복되지 않으면 이 경로를 simple path라고 한다. ( ex : 1 2 6 )
- Cycle : 그래프가 Path를 따라 동일한 정점으로 돌아올 수 있는 경우를 의미한다. < 1, 2, 3 >가 사이클을 이룬다. 시작점과 끝점을 제외하고 중복을 이루면 안된다.
그래프 구현 방법
그래프를 구현하는 방법에는 인접리스트와 인접행렬 방식이 존재한다.
인접리스트
인접 리스트는 연결리스트를 이용하여 각 정점과 인접한 다른 정점들을 저장하는 방법
무방향 그래프 리스트 - 무방향 그래프의 경우 노드가 양방향으로 연결되어 있으므로 각각 연결된 노드들의 리스트를 2차원 배열로 만들어준다.
graph = [ [], [2,3], [1,4], [1], [2,6], [6], [4,5] ]
방향 그래프 리스트 - 방향 그래프의 경우 각 화살표가 가리키는 방향의 노드들을 추가해준다.
graph = [ [], [2,3], [6], [4], [], [6], [] ]
인접행렬
무방향 그래프 인접 행렬 - 인접 행렬을 만드는 경우는 각각 인덱스와 매칭되도록 좌표값에 1을 표시해서 연결 되었음을 알려준다.
- 대각선을 기준으로 대칭으로 배열이 생성된다.
matrix = [ [0,1,1,0,0,0], [1,0,0,1,0,0], [1,0,0,0,0,0], [0,1,0,0,0,1], [0,0,0,0,0,1], [0,0,0,1,1,0], ]
방향 그래프 인접 행 - 방향 그래프 행렬의 경우 화살표가 연결된 부분만 1로 표시해준다.
matrix = [ [0,1,1,0,0,0], [0,0,0,0,0,1], [0,0,0,1,0,0], [0,0,0,0,0,0], [0,0,0,0,0,1], [0,0,0,0,0,0], ]
인풋값으로 입력된 값을 통해 리스트와 행렬 만들기
from pprint import pprint N = int(input()) matrix = [ [0] * (N+1) for _ in range(N+1) ] graph = [ [] for _ in range(N+1) ] for _ in range(10): A, B = map(int,input().split()) graph[A].append(B) graph[B].append(A) matrix[A][B] = 1 matrix[B][A] = 1 print(graph) pprint(matrix) 7 1 3 1 2 2 5 2 7 3 4 1 6 5 6 4 7 7 3 1 7 [[], [3, 2, 6, 7], [1, 5, 7], [1, 4, 7], [3, 7], [2, 6], [1, 5], [2, 4, 3, 1]] [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0, 1, 1], [0, 1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1, 0], [0, 1, 0, 0, 0, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0, 0]]
'알고리즘' 카테고리의 다른 글
LCS 알고리즘 (1) 2024.06.16 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) (0) 2023.08.10 이진 탐색(Binary Search) (0) 2023.03.02 DP(Dynamic Programming) 동적 프로그래밍 (0) 2023.02.15 탐욕 알고리즘(Greedy Algorithm) (0) 2023.01.23