on
Graph
Graph
Graph
자료구조에서 배운 트리와 연관된 개념으로 노드간 연결이 가능하다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있다
트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프생성을 통해 다른범위의 개념으로 사용되는 자료구조이다
그래프는 노드간의 관계, 트리는 노드간의 계층 을 표현한다 ex) object 간의 관계를 표현할 때 유용하다
그래프 유형
그래프의 특성은 directed(방향성), undirected(무방향성) 이 있다
방향성그래프
그래프가 한쪽 방향(one-way)로 설명될 수 있따면 directed 그래프가 가장 적합 방향성그래프는 순서가 있으므로 마지막에는 노드(leaf node)가 있다
방향성 그래프는 bidirectional(양방향)가 될 수 있다 노드끼리 양방으로 전달될 수 있다
무방향성 그래프
관계목적이 상호 교환이라면, undirected 그래프가 적합 교환관계는 항상 상호이므로 undirected 가 가장 의미있다
무방향성은 방향이 따로 지정되어있지않고, 간선으로 연결된 노드끼리는 서로 인접(adjacent)해 있다고하며, 이웃(neighbor)라고 칭한다
Cyclic and Acyclic Graphs(순환 및 비순환 그래프)
루프를 형성(방문한 노드에 다시방문)할 수 있는 경우는 순환 그래프
undirected 그래프는 항상 동일한 노드에 재방문 할 수 있으므로 순환그래프
반대의 경우가 비순환 그래프
Weighted Graphs(가중 그래프)
가중 그래프에는 간선(edge)와 관련된 값이 있다
각 edge의 가중치에 할당된 특정값을 호출한다
가중치는 서로다른 그래프에서 서로다른 데이터를 나타낸다
예를들어, 도로 구간을 나타내는 그래프에서 가중치는 도로의 길이를 나타낼 수 있다
그래프에서 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다 가중치는 모든 경로 비교시, 어떤 경로를 선택할지에 사용된다 최단경로로 가고싶다면 가중치의 합들이 작은 노드방향으로 진행하는 느낌
가중 그래프에서는 가중치를 선정하는것이 가장 어렵다
Directed Acyclic Graphs(DAGs)
데이터 사이언스에서 많이 등장하는 용어로, 방향성 비순환그래프(DAG)는 순환되지않는 단방향 그래프이다
edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬 할 수 있다
그래프의 활용
그래프를 나타내는 방법은 인접리스트(adjacency lists), 인접행렬(adjacency matrices)가 있다
그래프를 구현할 떄 저장할 데이터유형과 그래프에서 실행하야하는 작업을 이해하는것이 중요하다 이것을 이해하기위해 필요한개념이 인접리스트와 인접행렬이다 행렬에서는 노드간 연결된경우 1로, 연결리스트에서는 a: => b,c 식으로 표현
인접리스트 (Adjacency List)
인접리스트에서 그래프는 전체 노드 목록을 저장한다
vertices(정점)은 O(1) 상수시간에 각 edge(간선)에 접근할 수 있다 한마디로 하나의 정점에서 다른정점으로 가는것이 빠르고 단순하게 가능하다
# 노드가 키가 되고, 인접노드가 값이 되는 딕셔너리이다. # 가장자리 노드들은 set으로 구현되어 있다. class Graph: def __init__(self): self.vertices = { "A": {"B"}, # 여기서 {"B"}가 set의 형태이다. "B": {"C", "D"}, # {"B" : {}}의 형태는 딕셔너리 "C": {"E"}, # 즉, 딕셔너리 안에 set이 있는 것이다. "D": {"F", "G"}, "E": {"C"}, "F": {"C"}, "G": {"A", "F"} }
인접행렬 (Adjacency metrics)
연결되는 노드에 대해서는 1로 표현(가중치가있다) 하지만, 행렬형태로 되어있으므로 노드간의 연관성을 한눈에 파악하는것이 인접리스트에비해 복잡하다
노드값과 해당 인덱스 사이에 연관성이 없다는 단점도 있다
하지만 간선가중치를 알 수 있다
0은 관계없음을 나타내지만, 다른값은 edge label, edge weight를 나타낸다
인접리스트와 행렬을 모두 구현하면 Vertex 와 Edge 클래스를 포함하여 많은 정보를 파악 할 수 있다
# 간선 가중치는 1이다. class Graph: def __init__(self): self.edges = [[0,1,0,0,0,0,0], [0,0,1,1,0,0,0], [0,0,0,0,1,0,0], [0,0,0,0,0,1,1], [0,0,1,0,0,0,0], [0,0,1,0,0,0,0], [1,0,0,0,0,1,0]]
그래프의 복잡도
인접행렬은 구현이 쉽지만, 특정노드에 방문한 노드를 파악하려면 모든 노드를 확인해야한다 O(n)
인접리스트는 연결된 관계만 저장하기때문에 실행시간에 영향을 적게주지만, 특정 노드간의 연결관계를 확인하기위해 반복문이 활용되며 이떄 O(n)이상의 시간복잡도를 가진다
# 인접리스트 구현 # 간선에 가중치를 부여할 수 있다는것이 특징 class Graph: def __init__(self): self.vertices = { "A": {"B": 1}, # 가중치 부여 "B": {"C": 3, "D": 2}, # 가중치 부여 "C": {}, "D": {}, "E": {"D": 1} # 가중치 부여 } # 인접행렬 구현 # 간선가중치를 보다 쉽게 표현가능 class Graph: def __init__(self): self.edges = [[0,1,0,0,0], [0,0,3,2,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,1,0]]
순회 Traversal
그래프나 트리같은 연결된 구조에서 노드를 한번씩 탐색하는 개념
(모든노드 혹은 특정노드를 방문하는 방법을 찾는것)
이진겁색트리 BST 와 다른 규칙이 적용되며, 방향에 따라 탐색방법이 달라진다
깊이우선탐색(DFS) 와 너비우선탐색(BFS) 라는 탐색 알고리즘이 존재한다
트리의 순회
그래프는 루트,부모,자식노드의 개념이 없지만, 전위,중위,후위순회 개념을 활용해 DFS, BFS를 구현할 수 있다
Preorder traverse 전위순회 : 루트를 먼저 방문 루트방문 후 왼쪽노드 -> 오른쪽노드
Inorder traverse 중위순회 : 왼쪽 서브트리를 방문 후 루트방문 왼쪽노드 방문후 루트노드 -> 오른쪽노드
Postorder traverse 후위순회 : 서브트리를 순서대로 모두 방문(좌->우) 후 루트방문
# 어떤결과가 나올것인지 예상해보기위해 서브트리를 구분해 높으면 헷갈리는것을 방지할 수 있다 -> 루트와 부모노드, 부모와 자식노드 형태로 서브트리를 나누는것 # 먼저 순회를 진행하기 위해 트리형태의 노드들을 생성한다. class node: # root -> left -> right 방향대로 노드 생성 def __init__(self, value, left=None, right=None): value left right root_node = node(10, node(8, node(7), node(1, node(3), node(2) ) ), node(9, node(11), node(12, node(13) ) ) )
# 전위 순회 def pre_order(node): print(node.value) # 루트노드 pre_order(node.left) # 왼쪽노드 pre_order(node.right) # 오른쪽노드 # 중위 순회 def in_order(node): in_order(node.left) # 왼쪽노드 print(node.value) # 루트노드 in_order(node.right) # 오른쪽노드 # 후위 순회 def post_order(node): post_order(node.left) # 왼쪽노드 post_order(node.right) # 오른쪽노드 print(node.value) # 루트노드
from http://bong7233.tistory.com/30 by ccl(A) rewrite - 2021-09-30 13:00:28