[Data Structure] Graph

"그래프"(Graph)는 각 데이터와 그들을 잇는 선들로 이루어진 ADT이다. 

각 데이터들을 "정점"(vertex) 혹은 "노드"(node)라 부르며, 

이들을 잇는 선을 "간선"(edge)라 부른다.

 

즉, 그래프는 유한한 개수의 정점과 간선으로 이루어진 ADT이다. 

이러한 그래프 G를 G = (V, E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미한다. 

• 정점(노드) : 각 데이터 
• 간선 : 정점들을 잇는 선 
• 인접 정점: 간선에 의해 연결된 정점 (ex. A의 인접 정점은 B,C)
• 차수(degree) : 정점에 연결된 간선의 개수 (ex. A의 차수는 2)

이러한 그래프를 순회하는데 사용하는 알고리즘에는 대표적으로 BFS와 DFS가 있다.

순회란, 그래프내의 모든 정점을 한번씩 방문하는 것을 말한다.

 

그래프 종류 

이러한 그래프는 간선의 특징에 따라 혹은 구조적 특징에 따라 분류된다. 

 

간선의 특성에 따른 분류 

• 방향 그래프
• 무방향 그래프 
• 가중치 그래프

 

방향 그래프 vs. 무방향 그래프 

우선 간선이 방향성이 여부에 따라 "방향 그래프"와 "무방향 그래프"로 구분된다.

 

무방향 그래프는 간선에 방향이 없기 때문에, $(V_i, V_j)$, $(V_j, V_i)$ 로 표현이 가능하다. 

방향 그래프는 간선에 방향이 존재하기 때문에, $(V_i, V_j)$와 $(V_j, V_i)$는 서로 다른 간선이 된다.

 

또한, 방향 그래프의 경우에는 차수를 진입 차수와 진출 차수로 구분한다. 

• 진입 차수(in-degree) : 정점으로 들어오는 간선의 수
• 진출 차수(out-degree) : 정점에서 나가는 간선의 수

 

가중 그래프

각 간선마다 가중치가 있는 경우, "가중 그래프"라 부른다. 

이때, 간선의 가중치는 음수와 양수 모두 가능하며, 가중 그래프 중 방향 그래프인 경우 네트워크라 부른다. 

 

이런 가중 그래프에서 최단 경로 문제는 가중치 합이 최소가 되는 경로를 구하는 문제다.

대표적으로 다익스트라, 벨만포드 알고리즘, 플로이드-와샬 알고리즘 등이 존재한다.

 

구조적 특성에 따른 분류

• 연결 그래프
• 비연결 그래프
• 완전 그래프
• 부분 그래프 
• 다중 그래프

 

연결 그래프 vs. 비연결 그래프 

모든 정점 사이에 경로가 존재 여부에 따라 "연결 그래프"와 "비연결 그래프"로 구분한다. 

"연결 그래프"는 한 정점에서 다른 모든 정점으로 이동이 가능한 그래프를 말하며, 

"비연결 그래프"는 특정 정점은 다른 특정 정점으로 이동이 불가능한 그래프를 말한다.

 

완전 그래프 

그래프 내의 모든 정점들이 1:1로 연결되어 있는 그래프를 "완전 그래프"라 한다.

 

정점이 n개라 가정할 때, 

무방향 그래프의 간선의 수는 $n(n-1) / 2$,

방향 그래프의 간선의 수는 $n(n-1)$ 가 된다.

 

부분 그래프 

기존 그래프에서 특정 정점과 특정 간선으로 이루어진 그래프를 "부분 그래프"라 부른다.

G1, G2, G3, G4는 그래프 G의 부분 그래프이다. 

 

다중 그래프 

두 정점 사이에 여러 개의 간선이 존재하는 경우 "다중 그래프"라 부른다.

 

 

그래프 구현 방법

그래프를 구현하는 방법에는 크게 2가지가 존재한다.

• 인접 행렬 : 정사각 행렬을 통해 인접관계를 저장한다.
• 인접 리스트 : List 자료구조를 이용해 인접관계를 저장한다. 

 

인접 행렬 

"인접 행렬" 방법은 한 정점에 대해 다른 모든 정점과의 연결정보를 가지고 있는 정사각 행렬이다.

 

 

정점 N개에 대해서 $N^2$의 공간이 필요하게 된다. 

따라서, Dense Graph인 경우, 인접행렬은 적합하다. 

 

장점 

• 두개의 노드를 아는 경우, 사이 간선의  정보를 O(1)에 확인할 수 있다. 
• 새로운 간선을 추가하고, 제거하는 것이 O(1)에 가능하다. 

 

단점

• 인접 노드를 찾기 위해선 모든 노드를 순회해야 한다.

Sparse Graph의 경우,

즉 간선이 정점의 갯수에 비해,

인접행렬 방식은 메모리 낭비로 이어질 수 있다. 

 

인접 리스트

"인접 리스트" 방법은 한 정점의 인접 정점간의 연결정보만을 가지고 있는 List이다. 

간선의 개수만큼 메모리 공간이 필요하다. 

따라서, Sparse Graph의 경우 인접리스트 방식이 적합하다. 

 

장점

• 새로운 간선 및 정점의 추가가 O(1)에 가능하다. 
• 인접 노드 검색이 O(1)에 가능하다.

 

단점

• 두개의 정점으로 간선을 조회하는 경우, 시간이 오래 걸린다.

 

구현 

자세한 구현은 여기서 확인해볼 수 있다. 

https://github.com/jungseokyoung-cloud/Data-Structure/tree/main/Data-Structure/Graph.playground

Data-Structure/Data-Structure/Graph.playground at main · jungseokyoung-cloud/Data-Structure

우선, Swift의 Protocol을 통해 ADT를 작성해보자. 

public protocol Graph {
	associatedtype Element
	
	mutating func createVertex(data: Element) -> Vertex<Element>
	mutating func addEdge(
		_ type: EdgeType,
		from source: Vertex<Element>,
		to destination: Vertex<Element>,
		weight: Double?
	)
	
	mutating func edges(from source: Vertex<Element>) -> [Edge<Element>]
	mutating func adjacentVertex(from source: Vertex<Element>) -> [Vertex<Element>]
}

 

Vertex와 Edge는 다음과 같이 구현된다. 

public struct Vertex<T> {
	public let id: Int
	public var value: T
	
	public init(id: Int, value: T) {
		self.id = id
		self.value = value
	}
}

extension Vertex: Hashable {
	public func hash(into hasher: inout Hasher) {
		hasher.combine(id)
	}
	
	public static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
		return lhs.id == rhs.id
	}
}

public enum EdgeType {
	case directed
	case unDirected
}

public struct Edge<T> {
	public var source: Vertex<T>
	public var destination: Vertex<T>
	
	public var weight: Double?
	
	public init(source: Vertex<T>, destination: Vertex<T>, weight: Double? = nil) {
		self.source = source
		self.destination = destination
		self.weight = weight
	}
}

 

인접 행렬

public struct AdjacencyMatrix<T>: Graph {
	private var weights = [[Double?]]()
	private var vertices = Set<Vertex<T>>()
	private var indexToVertex = [Int: Vertex<T>]()
	
	public init() { }
}

• weights: N * N으로 가중치의 정보를 저장
• vertices: vertex들을 저장 
• indexToVertex: index를 통해 Vertex를 검색할 수 있는 딕셔너리 

vertices와 indexToVertex같은 경우는 O(1)에 검색하기 위해 해시를 이용했다. 

 

createVertex(data:) 

mutating func createVertex(data: T) -> Vertex<T> {
	let vertex = Vertex(id: vertices.count, value: data)
	vertices.insert(vertex)
	indexToVertex[vertices.count] = vertex
	
	for index in 0..<weights.count { weights[index].append(nil) }
	weights.append(.init(repeating: nil, count: vertices.count))
	
	return vertex
}

새로운 vertex를 생성하고, 이를 리턴한다. 

 

addEdge(_:from:to:weight:)

mutating func addEdge(
	_ type: EdgeType,
	from source: Vertex<T>,
	to destination: Vertex<T>,
	weight: Double?
) {
	switch type {
		case .directed:
			addDirectedEdge(from: source, to: destination, weight: weight)
		case .unDirected:
			addNonDirectedEdge(from: source, to: destination, weight: weight)
	}
}

 

해당 메서드의 경우에는 edgeType에 따라 다른 동작을 수행한다. 

mutating func addDirectedEdge(
	from source: Vertex<Element>,
	to destination: Vertex<Element>,
	weight: Double?
) {
	weights[source.id][destination.id] = weight ?? 1.0
}

mutating func addNonDirectedEdge(
	from source: Vertex<Element>,
	to destination: Vertex<Element>,
	weight: Double?
) {
	addDirectedEdge(from: source, to: destination, weight: weight)
	addDirectedEdge(from: destination, to: source, weight: weight)
}

 

 

인접 리스트 

public struct AdjacencyList<T>: Graph {
	private var list = [Vertex<T>: [Edge<T>]]()
	
	public init() { }
}

• list: vertex를 키값으로 연결된 간선들의 배열을 저장한다.

 

createVertex(data:) 

mutating func createVertex(data: T) -> Vertex<T> {
	let vertex = Vertex(id: list.count, value: data)
	list[vertex] = []
	return vertex
}

 

addEdge(_:from:to:weight:)

mutating func addEdge(
	_ type: EdgeType,
	from source: Vertex<Element>,
	to destination: Vertex<Element>,
	weight: Double?
) {
	switch type {
		case .directed:
			addDirectedEdge(from: source, to: destination, weight: weight)
		case .unDirected:
			addNonDirectedEdge(from: source, to: destination, weight: weight)
	}
}

 

해당 메서드의 경우에는 edgeType에 따라 다른 동작을 수행한다.

mutating func addDirectedEdge(
	from source: Vertex<Element>,
	to destination: Vertex<Element>,
	weight: Double?
) {
	let edge = Edge(source: source, destination: destination, weight: weight)
	
	list[source]?.append(edge)
}

mutating func addNonDirectedEdge(
	from source: Vertex<Element>,
	to destination: Vertex<Element>,
	weight: Double?
) {
	addDirectedEdge(from: source, to: destination, weight: weight)
	addDirectedEdge(from: destination, to: source, weight: weight)
}

 

References

위키 백과

• Graph (abstract data type)
• Adjacency Matrix
• Adjacency list

 

https://www.kodeco.com/773-swift-algorithm-club-graphs-with-adjacency-list#toc-anchor-001