그래프란 무엇인가?
그래프는 구성은 정점(Vertex 또는 Node), 간선(Edge 또는 Link)로 이루어진 자료구조이다. 위 그림에서 정점은 a, b, c, d, e를 의미한다. 간선은 a에서 b, a에서 c, b에서 d와 같이 두 정점 사이의 관계를 의미한다. 즉 그래프는 정점(Vertex) 집합과 간선(Edge) 집합으로 이루어져있다. 트리와 같이 계층 관계를 가지지 않는다. 객체와 이에 대한 관계를 유연하게 나타낼 수 있다.
그래프의 종류
그래프 자료구조는 간선의 방향성 유무와 가중치에 따라 다양하게 존재한다.
무방향 그래프: 간선에 방향이 없는 그래프
방향 그래프: 간선에 방향이 있는 그래프
가중치 그래프: 간선에 가중치가 들어간 그래프
가중치라 하면 비용, 우선순위 등 다양하게 해석이 가능하다.
완전 그래프: 모든 정점이 연결되어 있는 그래프
위 그래프 외에도 다양한 종류(Disconnected Graph, Acyclic Graph 등)가 있다.
그래프의 구현
기준에 대한 정점(노드)에서 인접한 정점(노드) 정보를 가지게 된다. 크게 2차원 배열을 활용하는 인접행렬, 연결리스트를 활용하는 인접리스트로 인접한 정점에 대한 정보를 가지고 있다.
인접행렬 방식
인접행렬 방식으론 이차원 배열이 활용된다. 모든 정점들의 간선정보를 담으므로 두 정점에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도를 갖는다. 하지만 2차원 배열이기에 필요 이상의 공간을 차지하게 된다.
인접리스트 방식
인접리스트는 그래프를 연결리스트로 표현한 것이다. 연결정보를 탐색할 때 O(n)의 시간이 걸리고 공간 낭비가 적다. 하지만 구현이 어려울 수 있고, 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.
그래프 동작방식
그래프 초기화(Create Graph)
그래프 생성 및 초기화는 인접행렬 방식과 인접리스트 방식 중 선택하면 된다.
노드 추가(Insert Vertex)
노드 삭제(Delete Vertex)
간선 추가(Insert Edge)
간선 삭제(Delete Edge)
코드로 구현
#Python code for Graph Data Struture
V = 5
#Maximum number of vertices in th graph
#Declaring vertices
class Vertex:
def __init__(self, end):
self.end = end
self.next = None
#Declaring Edges
class Edge:
def __init__(self, start, end):
self.start = start
self.end = end
#Declaring graph data structure
class Graph:
def __init__(self):
self.point = [None] * V
def create_graph(edges, x):
graph = Graph()
for i in range(V):
graph.point[i] = None
for i in range(x):
start = edges[i].start
end = edges[i].end
v = Vertex(end)
v.next = graph.point[start]
graph.point[start] = v
return graph
edges = [Edge(0, 1), Edge(0, 2), Edge(0, 3), Edge(1, 2), Edge(1, 4), Edge(2, 4), Edge(2, 3), Edge(3, 1)]
n = len(edges)
graph = create_graph(edges, n)
#Range
print("The graph created is: ")
for i in range(V):
ptr = graph.point[i]
while ptr is not None:
print("({} -> {})".format(i, ptr.end), end="\t")
ptr = ptr.next
print()Reference
