[Algorithms] 그래프란?

이 게시글은 문제 풀이용이 아닙니다.

 

그래프(Graph)라는 자료 구조를 이용해 다양한 문제를 해결하는 방법이 있음.

그래프라는 개념을 간단히 설명하자면, 그래프는 꼭짓점(또는 정점)과 모서리(또는 간선)로 이루어진 구조야.

• 꼭짓점들의 모음: vertices
• 모서리들의 모음: edges

근데 왜 이게 뭐 어쨌다고? 얻다 써먹냐고?

봐봐요. SNS 앱들에서 팔로우 관계는 어떻게 연결되어 있을 것 같음? 느낌 옴?

 

각 사용자 프로필을 꼭짓점으로 보고, 그 사용자들의 연결(팔로우 여부)을 모서리로 나타낸다.

이 외에도 GPS 경로 탐색 같은 다양한 곳에서 그래프가 쓰임.

---

그래프에는 보편적으로 많이 쓰이는 몇 가지 유형이 있다.

1. 무방향성 그래프(Undirected Graph)

꼭짓점을 연결하는 모서리가 양방향인 그래프! 즉, 꼭짓점 A와 B가 연결되어 있으면 A에서 B로, 그리고 B에서 A로 모두 이동이 가능.
어따 써먹냐? 예를 들어 친구 관계를 표현할 때 아주 적합하지! 서로가 서로를 친구로 연결하는 거니까.

2. 방향성 그래프(Directed Graph)

방향이 있는 그래프! A -> B 또는 B -> A처럼 특정 방향으로만 연결됨. 그래서 모서리 끝에 화살표를 추가해서 나타낸다.
어디에 쓰냐? 도시 간 왕복 여행이나 내비게이션 경로, 또는 알고리즘 문제에서 자주 보이는 형태지.

3. 가중치 그래프(Weighted Graph)

모서리에 추가 정보나 두 꼭짓점을 잇는 경로의 비용을 나타냄.

예를 들어 A -> B로 가는 데 걸리는 시간을 모서리마다 표시하면, 경로를 지날 때 걸리는 시간을 계산할 수 있음
언제 쓸 수 있을까? 경로 탐색에서 최단 시간을 구할 때, 또는 최소 비용을 계산해야 할 때 유용하게 쓸 수 있음.

---

그래프의 표현 방식

1. 객체지향 접근법: 구조체와 클래스 활용

구조체나 클래스를 사용해서 그래프를 객체지향적으로 표현할 수 있다.

그래프의 정점과 간선을 별도의 객체로 만들어서 각 정점 간의 관계를 정의하는 방식

 

class Vertex<T> {
    let value: T
    var edges: [Edge<T>] = []
    
    init(value: T) {
        self.value = value
    }
}

class Edge<T> {
    let source: Vertex<T>
    let destination: Vertex<T>
    let weight: Int? // 가중치가 있을 경우
    
    init(source: Vertex<T>, destination: Vertex<T>, weight: Int? = nil) {
        self.source = source
        self.destination = destination
        self.weight = weight
    }
}

 

2. 이웃 목록(Adjacency List)

이웃 목록은 각 정점이 연결된 정점들을 리스트 형태로 저장하는 방식, 공간 효율이 좋고, 그래프가 희소(즉, 간선이 많지 않은 경우)할 때 유용하다~ Swift에서 이웃 목록을 사용하는 방법은 보통 딕셔너리(Dictionary)를 이용해 구현

 

var adjacencyList: [String: [String]] = [
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
]

 

3. 이웃 매트릭스(Adjacency Matrix)

이웃 매트릭스는 그래프의 정점을 2차원 배열로 표현하는 방식으로 정점 간의 연결 여부를 행렬로 나타내는 방식이다, 각 위치에 1 또는 0을 넣어서 두 정점이 연결되었는지 여부를 표시

 

var adjacencyMatrix: [[Int]] = [
    [0, 1, 1, 0], // A의 연결 상태
    [1, 0, 0, 1], // B의 연결 상태
    [1, 0, 0, 1], // C의 연결 상태
    [0, 1, 1, 0]  // D의 연결 상태
]

 

4. 근접 매트릭스(Incidence Matrix)

근접 매트릭스는 정점과 간선의 관계를 행렬로 나타내는 방식, 행은 정점을 나타내고 열은 간선을 나타내며, 정점이 간선에 연결되었는지를 표시해. 이 방식은 그래프가 어떤 방식으로 연결되었는지 명확하게 볼 수 있지만, 다른 방법에 비해 구현이 복잡하고 효율이 떨어질 수 있다.

 

var incidenceMatrix: [[Int]] = [
    [1, 1, 0, 0], // 정점 A의 연결 상태
    [1, 0, 1, 0], // 정점 B의 연결 상태
    [0, 1, 0, 1], // 정점 C의 연결 상태
    [0, 0, 1, 1]  // 정점 D의 연결 상태
]

---

자, 이제 구조체와 제네릭, 그리고 프로토콜을 사용해서 그래프의 꼭지점과 모서리를 구현해 보겠다.

 

하나씩 차근차근해볼 거임. 전체 코드 한 번에 안 줌.

 

1. 꼭짓점(Vertex) 구조체 생성

우선, 그래프에서 각 꼭짓점(정점)을 표현하기 위해 새로운 구조체를 생성한다.

이때 제네릭을 사용해서 다양한 타입의 데이터를 처리할 수 있도록 한다.

public struct Vertex<T: Equatable>:Equatable {
    var data: T
    var index: Int
}

• 여기서 T는 제네릭으로 선언됐고, Equatable 프로토콜을 따르도록 했어. 이 말은 즉, T가 Equatable 해야 한다는 뜻이야. Equatable을 사용하면 두 꼭짓점 간의 비교가 가능해. Euquatable 프로토콜에 부합하기 위해서는 필수 메서드 구현해야 됨 (원래는 했어야 했으나 이젠 아님)
• Vertex 구조체는 꼭짓점의 데이터를 저장하는 data와, 그래프에서의 위치를 나타내는 index를 가지고 있어.

 

 

2. 모서리(Edge) 구조체 생성

이제 두 꼭짓점을 연결하는 모서리(Edge)를 표현해 보자.

모서리는 어느 정점에서 출발하고 어느 정점으로 가는지를 나타내지.

public struct Edge<T:Equatable>: Equatable {
    let from:Vertex<T>
    let to:Vertex<T>
}

• 여기서도 제네릭 T는 Equatable 프로토콜을 따르도록 설정했어. from과 to는 출발 정점과 도착 정점을 나타냄.
• 마찬가지로 Swift에서 Equatable을 자동으로 처리해 주니까, 두 모서리도 쉽게 비교 가능

 

3. 이웃 목록(Adjacency List) 구현

그래프에서 각 정점이 어느 정점과 연결되어 있는지를 관리하기 위해 이웃 목록(Adjacency List)을 구현해 보자.

이를 위해 도우미 구조체를 먼저 생성해보자.

import Foundation

public struct VertexEdgeList<T: Equatable & Hashable> {
    public let vertex: Vertex<T>
    public var edges: [Edge<T>] = []

    init(vertex: Vertex<T>) {
        self.vertex = vertex
    }

    public mutating func addEdge(edge: Edge<T>) {
        // 중복된 모서리 확인
        if self.edges.count > 0 {
            let equalEdges = self.edges.filter { existingEdge in return existingEdge == edge }
            if equalEdges.count > 0 { return }
        }
        // 새로운 모서리 추가
        self.edges.append(edge)
    }
}

이 코드가 하는 일은 간단히 말해, 하나의 정점과 해당 정점에서 출발하는 간선 목록을 관리한다. 즉, 이웃 목록에서 하나의 정점과 그 정점의 연결 정보(간선들)를 저장하는 단위라고 볼 수 있다.

구체적으로 설명하자면

1. VertexEdgeList는 하나의 정점과 그 정점에 연결된 모서리들(간선들)을 관리하는 구조체로, 여기서 vertex는 정점을 나타내고, edges는 그 정점에서 출발하는 간선들을 리스트로 보관하고 있음.
2. addEdge 함수는 중복된 모서리를 방지하면서 새로운 모서리를 추가하는 역할을 함. 즉, 동일한 간선이 여러 번 추가되지 않도록 필터링하는 기능

하지만, 이 코드는 하나의 정점에 대한 이웃 목록을 구현한 것이지, 그래프 전체의 이웃 목록을 구현한 것은 아님.

그래프 전체를 표현하려면 각 정점마다 이 VertexEdgeList를 관리하는 자료 구조가 필요함. 저건 말 그대로 도우미 구조체.

 

public struct AdjacencyListGraph<T: Equatable & Hashable> {
    public var adjacenctLists: [VertexEdgeList<T>] = []
    
    public var vertices: [Vertex<T>] {
        get {
            var vertices = [Vertex<T>]()
            for list in adjacenctLists {
                vertices.append(list.vertex)
            }
            return vertices
        }
    }
    
    public var edges: [Edge<T>] {
        get {
            var edges = Set<Edge<T>>()
            for list in adjacenctLists {
                for edge in list.edges {
                    edges.insert(edge) // Set에 모서리 추가
                }
            }
            return Array(edges) // Set을 배열로 변환
        }
    }
    
    init() { }
}

 

이렇게 이웃 목록을 포함한 새로운 구조체를 생성한다.

여기서 두개의 프로퍼티를 통해서 그래프의 모든 꼭지점 정보오 모서리 정보를 가져오도록 한다.

B.U.T 위의 코드를  실행하면 에러가 뜬다. 왜 에러일 것 같음?

Set을 이용하려면 Hashable 프로토콜을 따르고 각각의 모서리가 각자의 유일한 해시값을 지니도록 해야 한다. ㅇㅋ?

그러므로 Edge, Vertex 구조체에 익스텐션을 추가하자.

 

첫번째로, 아까 작성한 Edge 구조체의 첫 번째 라인을 변경한다.

그리고 익스텐션을 추가한다.

import Foundation

public struct Edge<T: Equatable & Hashable>: Equatable {
    let from: Vertex<T>
    let to: Vertex<T>
}

extension Edge: Hashable {
    // hash(into:) 필수 메서드 구현
    public func hash(into hasher: inout Hasher) {
        hasher.combine(from.index)
        hasher.combine(to.index)
    }
}

 

Vertex 구조체 역시 같은 방법으로 변경한다.

import Foundation

public struct Vertex<T: Equatable & Hashable>: Equatable {
    var data: T
    var index: Int
}

extension Vertex: Hashable {
    // hash(into:) 메서드 구현
    public func hash(into hasher: inout Hasher) {
        hasher.combine(data)
        hasher.combine(index)
    }
}

 

이상으로 Vertex, Edge, AdjacencyList를 표현하기 위한 개체와 이웃 목록 배열로 표현할 그래프를 생성했다.

다음으로, AdjacencyListGraph에 이웃 목록의 기능을 수행하기 위한 기능을 추가할 차례다.

AdjacencyListGraph에 addVertex 메소드를 추가한다.

 

나머지는 나중에 하겠다.... 너무 졸림...