옆집 스위프트: 1-6) 데이터 구조 - 그래프(Graph)

주말 잘 쉬고 그래프로 월요일을 시작합니다.

 

6. 그래프(Graph)

• 그래프에 대하여
  • 코딩에서 그래프는 상호 연결된 노드의 집합을 나타내는 데이터구조이다. 노드는 정점(vertice)이라고도 하며 이들간의 관계를 정의하는 정적선(edge)로 연결될 수 있다.
  • 그래프의 종류
    • 무방향 그래프: 엣지(edge, 정적선)가 특정 방향을 가지지 않고 단순히 두개의 정점간에 연결을 나타낸다.
    • 방향 그래프: 엣지가 특정 방향을 가진다. 정점1이 정점2에 연결되어있다고 해서 반드시 정점2가 정점1에 연결되어 있다는 것을 의미하지 않는다. 방향그래프의 엣지는 종종 화살표로 표시된다.
    • 가중 그래프: 각 엣지에 가중치 또는 비용을 부여한다. 이러한 가중치는 거리, 용량 또는 비용과 같은 다양한 속성을 나타낼 수 있다. 예를 들어, 교통망 그래프에서 엣지의 가중치는 두 위치 간의 거리를 나타낼 수 있다.
    • 순환 그래프: 루프를 형성하는 경로인 사이클을 포함한다. 즉, 그래프를 순회하고 시작 정점으로 돌아오는 동안 다른 정점을 다시 방문하지않고 가능한 경우를 말한다.
    • 비순환 그래프: 비순환 그래프는 사이클을 형성하지 않는다. 시작 정점으로 돌아가는 경로가 없다.
• 그래프 알고리즘: 그래프 조작 및 분석을 위해 특별히 설계된 여러 알고리즘
  • 너비 우선 탐색(BFS): 그래프를 너비 방향을 탐색하거나 검색하는데 사용되는 알고리즘이다. 지정됨 정점에서 시작하여 모든 이웃을 탐색한 후 그들의 이웃으로 이동한다.
  • 깊이 우선 탐색(DFS): 그래프를 탐색하거나 검색하기 위한 또 다른 알고리즘이다. 이는 사이클을 발견하거나 그래프에서 경로를 찾는데 적합하다.
  • 다익스트라 알고리즘: 가중 그래프에서 두 정점 간의 최단 경로를 찾는데 널리 사용되는 알고리즘이다. 시작 정점에서 모든 다른 정점까지의 최단 거리를 계산하여 경로 계획이나 네트워크 최적화에 유용하다.
  • 크루스칼 알고리즘: 연결된 가중 그래프에서 최소 신장 트리를 찾는데 사용된다. 최소 신장 트리는 모든 정점을 최소 총 가중치로 연결하는 엣지의 부분집합이다.

// 스위프트로 보는 그래프

// 인접 리스트: 각 정점은 인접한 정점들의 리스트와 연결되어 있다. 
// 필요한 연결만 저장하기 때문에 상대적으로 엣지가 적은 희소 그래프에 대해 효율적이다.
var adjacencyList: [Int: [Int]] = [:]

adjacencyList[1, default:[]].append(2)
adjacencyList[2, default:[]].append(1)

// 행렬 표현: 인접 행렬으로 정점 간의 연결을 나타내는 2차원 배열을 만들수 있다.
// (i, j) 위치의 값은 정점 i 에서 점점 j로 엣지가 존재하는지 여부를 나타낸다.
var adjacencyMatrix: [[Bool]] = Array(repeating: Array(repeating: false, count: vertexCount), count: vertexCount)

adjacencyMatrix[1][2] = true
adjacencyMatrix[2][1] = true

// 인전 리스트를 이용한 그래프 표현
class Graph {
	var adjacencyList: [Int: [Int]] = [:]
	
	func addEdge(from source: Int, to destination: Int) {
		if adjacencyList[source] == nil {
			adjacencyList[source] = []
		}
		
		adjacencyList[source]?.append(destination)
	}
	
	func getConnections(from node: Int) -> [Int] {
		return adjacencyList[node] ?? []
	}
}

// DFS 그래프 탐색(stack 사용)
func depthFirstSearch(graph: Graph, startNode: Int) {
	var visited: Set<Int> = []
	var stack: [Int] = []
	
	stack.append(startNode)
	
	while !stack.isEmpty {
		let currentNode = stack.removeLast()
		
		if !visited.contains(currentNode) {
			visited.insert(currentNode)
			print("방문한 노드: \\(currentNode)")
			
			for neighbor in graph.getConnections(from: currentNode) {
				stack.append(neighbor)
			}
		}
	}
}

// BFS 그래프 탐색(queue 사용)
func dreadthFirstSearch(graph: Graph, startNode: Int) {
	var visited: Set<Int> = []
	var queue: [Int] = []
	
	queue.append(startNode)
	
	while !queue.isEmpty {
		let currentNode = queue.removeFirst()
		
		if !visited.contains(currentNode) {
			visited.insert(currentNode)
			print("방문한 노드: \\(currentNode)")
			
			for neighbor in graph.getConnections(from: currentNode) {
				queue.append(neighbor)
			}
		}
	}
}

// 다익스트라 알고리즘(그리디 알고리즘) 그래프 탐색(최단 경로)
func dijkstra(graph: WeightedGraph, startNode: Int, endNode: Int) -> [Int] {
  var distances: [Int: Int] = [:]
  var previous: [Int: Int] = [:]
  var queue: [(node: Int, distance: Int)] = []
  
  distances[startNode] = 0
  queue.append((startNode, 0))
  
  while !queue.isEmpty {
    // 거리를 기준으로 정렬 (가장 짧은 거리를 가진 노드 선택)
    queue.sort { $0.distance < $1.distance }
    let (currentNode, currentDistance) = queue.removeFirst()
    
    if currentNode == endNode {
      break
    }
    
    if currentDistance > distances[currentNode] ?? Int.max {
      continue
    }
    
    for (neighbor, weight) in graph.getConnections(from: currentNode) {
      let distance = currentDistance + weight
        
      if distance < distances[neighbor] ?? Int.max {
        distances[neighbor] = distance
        previous[neighbor] = currentNode
	      queue.append((neighbor, distance))
      }
    }
  }
  
  var shortestPath: [Int] = []
  var current: Int? = endNode
  
  while let node = current {
    shortestPath.insert(node, at: 0)
    current = previous[node]
  }
  
  return shortestPath
}

// 가중치 그래프 클래스 (다익스트라를 위한 추가)
class WeightedGraph {
  var adjacencyList: [Int: [(node: Int, weight: Int)]] = [:]
    
  func addEdge(from source: Int, to destination: Int, weight: Int) {
    if adjacencyList[source] == nil {
	    adjacencyList[source] = []
    }
    adjacencyList[source]?.append((destination, weight))
  }
    
  func getConnections(from node: Int) -> [(node: Int, weight: Int)] {
    return adjacencyList[node] ?? []
  }
}

// 그래프 생성 및 초기화
let vertexCount = 6 // 0부터 5까지의 정점

// 인접 리스트 생성 예시
var adjacencyList: [Int: [Int]] = [:]
adjacencyList[0, default: []].append(1)
adjacencyList[0, default: []].append(2)
adjacencyList[1, default: []].append(3)
adjacencyList[2, default: []].append(3)
adjacencyList[2, default: []].append(4)
adjacencyList[3, default: []].append(5)
adjacencyList[4, default: []].append(5)

// 인접 행렬 생성 예시
var adjacencyMatrix: [[Bool]] = Array(repeating: Array(repeating: false, count: vertexCount), count: vertexCount)
adjacencyMatrix[0][1] = true
adjacencyMatrix[0][2] = true
adjacencyMatrix[1][3] = true
adjacencyMatrix[2][3] = true
adjacencyMatrix[2][4] = true
adjacencyMatrix[3][5] = true
adjacencyMatrix[4][5] = true

// Graph 클래스 사용 예시
let graph = Graph()
graph.addEdge(from: 0, to: 1)
graph.addEdge(from: 0, to: 2)
graph.addEdge(from: 1, to: 3)
graph.addEdge(from: 2, to: 3)
graph.addEdge(from: 2, to: 4)
graph.addEdge(from: 3, to: 5)
graph.addEdge(from: 4, to: 5)

// DFS 호출 예시
print("DFS 탐색 결과:")
depthFirstSearch(graph: graph, startNode: 0)
// 출력:
// DFS 탐색 결과:
// 방문한 노드: 0
// 방문한 노드: 2
// 방문한 노드: 4
// 방문한 노드: 5
// 방문한 노드: 3
// 방문한 노드: 1

// BFS 호출 예시
print("\\nBFS 탐색 결과:")
breadthFirstSearch(graph: graph, startNode: 0)
// 출력:
// BFS 탐색 결과:
// 방문한 노드: 0
// 방문한 노드: 1
// 방문한 노드: 2
// 방문한 노드: 3
// 방문한 노드: 4
// 방문한 노드: 5

// 가중치 그래프 생성 예시
let weightedGraph = WeightedGraph()
weightedGraph.addEdge(from: 0, to: 1, weight: 4)
weightedGraph.addEdge(from: 0, to: 2, weight: 2)
weightedGraph.addEdge(from: 1, to: 3, weight: 5)
weightedGraph.addEdge(from: 2, to: 3, weight: 1)
weightedGraph.addEdge(from: 2, to: 4, weight: 3)
weightedGraph.addEdge(from: 3, to: 5, weight: 2)
weightedGraph.addEdge(from: 4, to: 5, weight: 2)

// 다익스트라 알고리즘 호출 예시
print("\\n최단 경로 (0 → 5):")
let shortestPath = dijkstra(graph: weightedGraph, startNode: 0, endNode: 5)
print(shortestPath.map { String($0) }.joined(separator: " → "))
// 출력:
// 최단 경로 (0 → 5):
// 0 → 2 → 3 → 5
// (총 가중치: 2 + 1 + 2 = 5)

/*
이 호출 예시는 다음과 같은 그래프 구조를 가정:
    4       5
0 ----> 1 ----> 3
|              ^|
|              ||
2       1      |2
|-----> 2 ----->|
        |       v
        |3      5
        v
        4 -----> 
           2
 */