그래프

트리와 연결리스트는 그래프의 단순한 버전이다.
vertex: 정점, node: 노드
edge: 간선

그래프

• 무방향undirected/양방향directed 그래프가 있다
• 루프가 가능하다
• 루트 노드라는 개념이 없다
• 부모-자식 관계라는 개념이 없다
• 그래프의 순회는 DFS나 BFS로 이루어진다
• 그래프는 네트워크 모델이다

트리

• 트리는 그래프의 특별한 케이스이며 "최소 연결 트리"라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 루프가 없다
• 간선은 항상 정점의개수-1 만큼을 가진다
• 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모노드만을 가진다
• 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다
• 트리의 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
• 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.
• 트리는 계층 모델이다

---

인접행렬과 인접리스트

노드V, 간선E	메모리	시간	알고리즘
인접행렬	O(V^2)	O(1)	플로이드워셜 알고리즘 (노드 개수가 적을 때)
인접리스트	O(E)	O(V)	다익스트라 최단경로 알고리즘(우선순위큐 방식)

인접 리스트 adjacency lists

• 배열에 저장하기
• 연결리스트에 저장하기
• 딕셔너리에 저장하기

//MARK: - Vertex
public struct Vertex<T: Hashable> { // 딕셔너리 타입이라 Hashable을 따라야
    var data: T
}

extension Vertex: Hashable {
    public func hash(into hasher: inout Hasher) {
        print("\(data)".hashValue)
    }
    
    static public func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.data == rhs.data
    }
}

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

//MARK: - Edge
public enum EdgeType {
    // 방향, 무방향
    case directed, undirected
}

public struct Edge<T: Hashable> {
    public var source: Vertex<T>      // 출발지
    public var destination: Vertex<T> // 도착지
    public let weight: Double?        // 가중치
}

extension Edge: Hashable {
    public func hash(into hasher: inout Hasher) {
        print("\(source)\(destination)\(String(describing: weight))".hashValue)
    }
    
    static public func ==(lhs: Edge<T>, rhs: Edge<T>) -> Bool {
        return lhs.source == rhs.source && lhs.destination == rhs.destination && lhs.weight == rhs.weight
    }
}

//MARK: - Graphable
protocol Graphable {
    associatedtype Element: Hashable
    var description: CustomStringConvertible { get }    // 디버깅용
    
    func createVertex(data: Element) -> Vertex<Element>
    func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
    func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
    func edges(from source: Vertex<Element>) -> [Edge<Element>]?
}

//MARK: - Adjacency List
open class AdjacencyList<T: Hashable> {
    public var adjacencyDict: [Vertex<T>: [Edge<T>]] = [:]
    public init() {}
    
    // 방향
    fileprivate func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
        let edge = Edge(source: source, destination: destination, weight: weight)   // 간선 생성
        adjacencyDict[source]?.append(edge) //출발점에서 간선 추가
    }
    
    // 무방향 (양쪽을 연결)
    fileprivate func addUndirectedEdge(vertices: (Vertex<Element>, Vertex<Element>), weight: Double?) {
      let (source, destination) = vertices
      addDirectedEdge(from: source, to: destination, weight: weight)
      addDirectedEdge(from: destination, to: source, weight: weight)
    }
}

extension AdjacencyList: Graphable {
    public typealias Element = T
    
    var description: CustomStringConvertible {
        var result = ""
        for (vertex, edges) in adjacencyDict {
            var edgeString = ""
            for (index, edge) in edges.enumerated() {
                if index != edges.count - 1 {
                    edgeString.append("\(edge.destination), ")
                } else {
                    edgeString.append("\(edge.destination)")
                }
            }
            result.append("\(vertex)--->[\(edgeString)]\n")
        }
        return result
    }
    
    func createVertex(data: T) -> Vertex<T> {
        let vertex = Vertex(data: data)
        
        if adjacencyDict[vertex] == nil {   // 존재하지 않으면
            adjacencyDict[vertex] = []      // 정점을 생성한다
        }
        
        return vertex
    }
    
    // 무방향/방향 타입에 따라 정점에 간선 추가하기
    func add(_ 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:
            addUndirectedEdge(vertices: (source, destination), weight: weight)
        }
    }
    
    func weight(from source: Vertex<T>, to destination: Vertex<T>) -> Double? {
        guard let edges = adjacencyDict[source] else {
            return nil
        }
        
        for edge in edges {
            if edge.destination == destination {
                return edge.weight
            }
        }
        
        return nil
    }
    
    func edges(from source: Vertex<T>) -> [Edge<T>]? {
        return adjacencyDict[source]
    }
    
}

인접 행렬 adjacency matrix

그리디 알고리즘: 크루스칼Kruskal 알고리즘
큐, 스택: 위상정렬Topology 알고리즘

우선순위큐: 다익스트라 최단 경로 알고리즘
최소힙, 최대힙
최소힙: 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조(방향O)

플로이드워셜 알고리즘
다익스트라 최단경로 알고리즘