[Data Structure / Algorithms] Graph

주제: 그래프 자료구조

---

그래프

• 그래프는 객체간의 관계를 나타내는 데이터 자료구조입니다.
• 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이며, 그래프는 네트워크 모델을 표현하는 데 사용됩니다.
• 정점(Vertex)

  그래프의 기본 요소로, 위치를 나타냅니다. 노드라고도 불립니다.

• 간선(Edge)

  두 정점을 연결하는 선으로, 두 정점 사이의 관계를 나타냅니다.

그래프 종류

가중 그래프(Weighted graphs)

• 가중 그래프에서는 각 엣지가 가중치를 가지며, 이 값은 해당 엣지를 사용하는 데 드는 비용을 나타냅니다.
• 이러한 가중치를 통해 두 개의 정점 사이에서 가장 싼 또는 가장 짧은 경로를 선택할 수 있습니다.

방향 그래프(Directed graphs)

• 엣지에 가중치를 할당하는 것과 함께, 그래프에 방향을 부여할 수 있습니다.
• 방향 그래프는 엣지가 한 방향으로만 탐색 가능하도록 제한합니다.

무방향 그래프(Undirected graphs)

• 간선에 방향성이 없는 그래프입니다. 간선은 양방향으로 간주됩니다.
• 두 개의 연결된 정점은 서로 오가는 엣지를 가지며, 엣지의 가중치는 양 항뱡 모두에 적용됩니다.

그래프 표현 방식

깊이 우선 탐색(DFS, Depth-First Search)

• 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색하는 방식입니다.

너비 우선 탐색(BFS, Breadth-First Search)

• 시작 정점에서 인접한 정접을 먼저 탐색한 후, 차례대로 더 멀리 있는 정점을 탐색하는 방식입니다.

그래프의 활용

• 최단 경로 찾기

  다양한 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜 등)을 사용하여 최단 경로를 찾는데 사용됩니다.

• 네트워크 흐름

  최대 흐름 문제와 같은 네트워크 흐름 문제를 해결하는 데 사용됩니다.

• 사이클 감지

  그래프에서 사이클을 감지하는데 사용됩니다.

그래프 관련 문제

• 연결성

  그래프 내의 모든 정점이 서로 연결되어 있는지 확인하는 문제입니다.

• 이분 그래프

  그래프의 정점을 두 그룹으로 나누어 각 그룹 내의 정점끼리는 서로 인접하지 않도록 할 수 있는지 확인하는 문제입니다.

구현

고려사항

• 가중치와 방향

  그래프에 가중치나 방향이 있을 경우, 이를 고려하여 구현해야 합니다.

• 자료구조 선택

  특정 문제에 적합한 자료구조 (인접 리스트 또는 인접 행렬)를 선택하여 효율적인 그래프 구현이 가능합니다.

공통

public enum EdgeType {
	case directed
	case undirected
}

public protocol Graph { 
	associatedtype Element 
	
	func createVertex(data: Element) -> Vertex<Element>
	func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
	func addUndirectedEdge(between source: Vertex<Element>, and destination: Vertex<Element>, weight: Double?)
	func add(_ edge: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
	func edges(from source: Vertex<Element>) -> [Edge<Element>]
	func weight(from source: Vertex<Element>, to destination: Vertex<Element>) ->  Double? 
}

• createVertex: 정점을 생성하고 그래프에 추가합니다.
• addDirectedEdge: 두 정점 사이에 방향성이 있는 간선을 추가합니다.
• addUndirectedEdge: 두 정점 사이에 양방향 간선을 추가합니다.
• add: EdgeType을 사용하여 두 정점 사이에 방향성 또는 양방향 간선을 추가합니다.
• edges: 특정 정점에서 나가는 간선 목록을 반환합니다.
• weight: 두 정점 사이의 간선 가중치를 반환합니다.

Vertex 구현

public struct Vertex<T> { 
	public let index: Int
	public let data: T
}
extension Vertex: Hashable where T: Hashable {} 
extension Vertex: Equatable where T: Equatable {}

extension Vertex: CustomStringConvertible { 
	public var description: String { 
		"\(index): \(data)"
	}
}

• 정점은 그래프 내에서 고유한 인덱스를 가지며 데이터를 보유합니다.
• dictionary의 key 유형으로 Vertex를 사용할 것이므로 Hashable을 준수하도록 만들어야 합니다.
•  Hashable 프로토콜은 Equatable을 상속하므로 이 프로토콜의 요구 사항도 충족해야 합니다.
• 위의 확장은 빈 상태이지만 컴파일러는 두 프로토콜 모두에 대한 일치를 자동으로 생성할 수 있습니다.

Edge 구현

public struct Edge<T> { 
	public let source: Vertex<T>
	public let destination: Vertex<T>
	public let weight: Double? 
}

• Edge는 두 개의 Vertex를 연결하며 선택적 가중치를 가집니다.

Adjacency list(인접 리스트)

• 각 정점에 인접한 정점들의 목록을 저장하는 방식입니다. 보통 배열, 리스트, 연결 리스트 등으로 구현됩니다.
• 간선의 수에 비례하는 메모리를 사요합니다. 그래프가 희소할수록(간선이 적을수록) 메모리 효율이 좋습니다.
• 특정 정점에 연결된 모든 정점을 탐새하는 데는 빠르지만, 두 정점 사이에 간선이 존재하는지 확인하는데는 시간이 더 걸립니다.
• 간선의 수가 정점의 수에 비해 상대적으로 적은 희소 그래프에 적합합니다. 예를 들어, 소셜 네트워크의 사용자 간 관계나 도로망에서의 교차로 등이 있습니다.

public class AdjacencyList<T: Hashable>: Graph { 
	private var adjacencies: [Vertex<T>: [Edge<T>]]  = [:]
	
	public init() { }
	
	public func createVertex(data: T) -> Vertex<T> { 
		let vertex = Vertex(index: adjacencies.count, data: data)
		adjacencies[vertex] = [] 
		return vertex
	}
	
	public func edges(from source: Vertex<T>) -> [Edge<T>] { 
		adjacencies[source] ?? []
	}
	
	public func weight(from source: Vertex<T>, to destination: Vertex<T>) -> Double? { 
		edges(from: source)
				.first { $0.destination == destination }? 
				.weight
	}
	public func addDirectedEdge(from source: Vertex<T>, to destination: Vertex<T>, weight: Double?) { 
		let edge = Edge(source: source, destination: destination, weight: weight)
		adjacencies[source]?.append(edge)
	}
	
	public func addUndirectedEdge(between source: Vertex<T>, and destination: Vertex<T>, weight: Double?) { 
		addDirectedEdge(from: source, to: destination, weight: weight)
		addDirectedEdge(from: destination, to: source, weight: weight)
	}
	
	public func add(_ edge: EdgeType, from source: Vertex<T>, to destination: Vertex<T>, weight: Double?) { 
		switch edge { 
			case .directed:
				addDirectedEdge(from: source, to: destination, weight: weight)
			case .undirected: 
				addUndirectedEdge(between: source, and: destination, weight: weight)
		}
	}
}

extension AdjacencyList: CustomStringConvertible {

  public var description: String {
    var result = ""
    for (vertex, edges) in adjacencies { // 1
      var edgeString = ""
      for (index, edge) in edges.enumerated() { // 2
        if index != edges.count - 1 {
          edgeString.append("\(edge.destination), ")
        } else {
          edgeString.append("\(edge.destination)")
        }
      }
      result.append("\(vertex) ---> [ \(edgeString) ]\n") // 3
    }
    return result
  }
}

let graph = AdjacencyList<String>()

let singapore = graph.createVertex(data: "Singapore")
let tokyo = graph.createVertex(data: "Tokyo")
let hongKong = graph.createVertex(data: "Hong Kong")
let detroit = graph.createVertex(data: "Detroit")
let sanFrancisco = graph.createVertex(data: "San Francisco")
let washingtonDC = graph.createVertex(data: "Washington DC")
let austinTexas = graph.createVertex(data: "Austin Texas")
let seattle = graph.createVertex(data: "Seattle")

graph.add(.undirected, from: singapore, to: hongKong, weight: 300)
graph.add(.undirected, from: singapore, to: tokyo, weight: 500)
graph.add(.undirected, from: hongKong, to: tokyo, weight: 250)
graph.add(.undirected, from: tokyo, to: detroit, weight: 450)
graph.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
graph.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
graph.add(.undirected, from: detroit, to: austinTexas, weight: 50)
graph.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
graph.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
graph.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
graph.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
graph.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 297)

print(graph)


2: Hong Kong ---> [ 0: Singapore, 1: Tokyo, 4: San Francisco ]
4: San Francisco ---> [ 2: Hong Kong, 5: Washington DC, 7: Seattle, 6: Austin Texas ]
5: Washington DC ---> [ 1: Tokyo, 6: Austin Texas, 4: San Francisco, 7: Seattle ]
6: Austin Texas ---> [ 3: Detroit, 5: Washington DC, 4: San Francisco ]
7: Seattle ---> [ 5: Washington DC, 4: San Francisco ]
0: Singapore ---> [ 2: Hong Kong, 1: Tokyo ]
1: Tokyo ---> [ 0: Singapore, 2: Hong Kong, 3: Detroit, 5: Washington DC ]
3: Detroit ---> [ 1: Tokyo, 6: Austin Texas ]

Adjacency matrix(인접 행렬)

• 인접 행렬은 그래프의 모든 정점들 사이의 연결 관계를 행렬로 표현하는 방식입니다. 행렬의 각 요소는 두 정점 사이의 간선의 존재 여부나 가중치를 나타냅니다.
• 정점의 수의 제곱에 비례하는 메모리를 사용합니다. 간선의 수와 관계없이 고정된 크기의 메모리가 필요합니다.
• 두 정점 사이에 간선이 존재하는지를 상수 시간 내에 확인할 수 있습니다. 하지만, 특정 정점에 연결된 모든 정점을 찾는 데는 시간이 더 걸립니다.
• 간선의 수가 많은 밀집그래프에 적합합니다. 예를들어, 네트워크나 행렬에서의 이웃하는 요소들 간의 관계 등이 있습니다.
• 이 행렬은 두 개의 차원을 가지며, matrix[row][column]의 값을 row와 column의 정점 사이 엣지 가중치를 나타냅니다.

public class AdjacencyMatrix<T>: Graph { 
	private var vertices: [Vertex<T>] = []
	private var weights: [[Double?]] = []
	
	public init() { }
	
	public func createVertex(data: T) -> Vertex<T> { 
		let vertex = Vertex(index: vertices.count, data: data) 
		vertices.append(vertex)
		// 기존에 있던 값에 추사된 vertex 가중치를 위한 자리 만들기 (Up down)
		for i in 0..<weights.count { 
			weights[i].append(nil)
		}
		// 추가된 vertex의 가중치를 위한 자리 만들기
		let row = [Double?](repeating: nil, count: vertices.count)
		weights.append(row)
		
		return vertex 
	}
	
	public func addDirectedEdge(from source: Vertex<T>, to destination: Vertex<T>, weight: Double?) { 
		weights[source.index][destination.index] = weight
	}
	
    public func addUndirectedEdge(between source: Vertex<T>, and destination: Vertex<T>, weight: Double?) {
        addDirectedEdge(from: source, to: destination, weight: weight)
        addDirectedEdge(from: destination, to: source, weight: weight)
    }
    
    public func add(_ edge: EdgeType, from source: Vertex<T>, to destination: Vertex<T>, weight: Double?) {
        switch edge {
        case .directed:
            addDirectedEdge(from: source, to: destination, weight: weight)
        case .undirected:
            addUndirectedEdge(between: source, and: destination, weight: weight)
        }
    }
	
	public func edges(from source: Vertex<T>) -> [Edge<T>] { 
		var edges: [Edge<T>] = []
		for column in 0..<weights.count { 
			if let weight = weights[source.index][column] { 
				edges.append(Edge(source: source, destination: vertices[column], weight: weight))
			}
		}
		return edges
	}
	
	 public func weight(from source: Vertex<T>, to destination: Vertex<T>) -> Double? {
        weights[source.index][destination.index]
    }

}

extension AdjacencyMatrix: CustomStringConvertible {

  public var description: String {
    // 1
    let verticesDescription = vertices.map { "\($0)" }
                                      .joined(separator: "\n")
    // 2
    var grid: [String] = []
    for i in 0..<weights.count {
      var row = ""
      for j in 0..<weights.count {
        if let value = weights[i][j] {
          row += "\(value)\t"
        } else {
          row += "ø\t\t"
        }
      }
      grid.append(row)
    }
    let edgesDescription = grid.joined(separator: "\n")
    // 3
    return "\(verticesDescription)\n\n\(edgesDescription)"
  }
}

let graph2 = AdjacencyMatrix<String>()

let singapore2 = graph2.createVertex(data: "Singapore")
let tokyo2 = graph2.createVertex(data: "Tokyo")
let hongKong2 = graph2.createVertex(data: "Hong Kong")
let detroit2 = graph2.createVertex(data: "Detroit")
let sanFrancisco2 = graph2.createVertex(data: "San Francisco")
let washingtonDC2 = graph2.createVertex(data: "Washington DC")
let austinTexas2 = graph2.createVertex(data: "Austin Texas")
let seattle2 = graph2.createVertex(data: "Seattle")

graph2.add(.directed, from: singapore2, to: hongKong2, weight: 300)
graph2.add(.directed, from: singapore2, to: tokyo2, weight: 500)
graph2.add(.directed, from: hongKong2, to: tokyo2, weight: 250)
graph2.add(.directed, from: tokyo2, to: detroit2, weight: 450)
graph2.add(.directed, from: tokyo2, to: washingtonDC2, weight: 300)
graph2.add(.directed, from: hongKong2, to: sanFrancisco2, weight: 600)
graph2.add(.directed, from: detroit2, to: austinTexas2, weight: 50)
graph2.add(.directed, from: austinTexas2, to: washingtonDC2, weight: 292)
graph2.add(.directed, from: sanFrancisco2, to: washingtonDC2, weight: 337)
graph2.add(.directed, from: washingtonDC2, to: seattle2, weight: 277)
graph2.add(.directed, from: sanFrancisco2, to: seattle2, weight: 218)
graph2.add(.directed, from: austinTexas2, to: sanFrancisco2, weight: 297)

print(graph2)

0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle

ø		500.0	300.0	ø		ø		ø		ø		ø		
ø		ø		ø		450.0	ø		300.0	ø		ø		
ø		250.0	ø		ø		600.0	ø		ø		ø		
ø		ø		ø		ø		ø		ø		50.0	ø		
ø		ø		ø		ø		ø		337.0	ø		218.0	
ø		ø		ø		ø		ø		ø		ø		277.0	
ø		ø		ø		ø		297.0	292.0	ø		ø		
ø		ø		ø		ø		ø		ø		ø		ø	

그래프 표현방식 선택 기준

• 간선의 수와 정점의 수

  희소 그래프에서는 인접 리스트가, 밀집 그래프에서는 인접 행렬이 메모리 효율적입니다.

• 자주 수행되는 작업

  간선의 존재 여부를 자주 확인해야 한다면 인접 행렬, 특정 정점의 인접 정점을 자주 확인한다면 인접 리스트가 유리합니다.

• 메모리와 시간의 트레이드오프

  메모리 사용량을 줄이고자 한다면 인접 리스트, 연산 속도를 높이고자 한다면 인접 행렬을 선택합니다.

출처(참고문헌)

• https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/36-graphs

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.