// 그래프를 나타내는 간선 리스트
const edges = [
  { from: 'A', to: 'B', weight: 4 },
  { from: 'A', to: 'C', weight: 2 },
  { from: 'B', to: 'C', weight: 1 },
  { from: 'B', to: 'D', weight: 5 },
  { from: 'C', to: 'D', weight: 8 },
  { from: 'C', to: 'E', weight: 10 },
  { from: 'D', to: 'E', weight: 2 },
  { from: 'E', to: 'A', weight: 3 },
]

// 벨만-포드 알고리즘 함수
function bellmanFord(edges, startNode) {
  const distances = {}
  edges.forEach((edge) => {
    distances[edge.from] = Infinity
    distances[edge.to] = Infinity
  })
  distances[startNode] = 0

  for (let i = 0; i < Object.keys(distances).length - 1; i++) {
    edges.forEach(({ from, to, weight }) => {
      if (distances[from] + weight < distances[to]) {
        distances[to] = distances[from] + weight
      }
    })
  }

  // 음수 가중치 사이클 확인
  edges.forEach(({ from, to, weight }) => {
    if (distances[from] + weight < distances[to]) {
      throw new Error('음수 가중치 사이클이 존재합니다.')
    }
  })

  return distances
}

// 예제 실행
const startNode = 'A'
try {
  const shortestDistances = bellmanFord(edges, startNode)
  console.log(`최단 거리 테이블 (${startNode}에서 시작):`, shortestDistances)
} catch (error) {
  console.error(error.message)
}

// 그래프를 나타내는 인접 행렬 (무한대를 Infinity로 표현)
const graph = [
  [0, 3, Infinity, 5],
  [2, 0, Infinity, 4],
  [Infinity, 1, 0, Infinity],
  [Infinity, Infinity, 2, 0],
]

// 워셜 알고리즘 함수
function floydWarshall(graph) {
  const nodes = graph.length
  const dist = Array.from({ length: nodes }, () => Array(nodes).fill(Infinity))

  // 거리 배열 초기화 (초기 그래프 상태 복사)
  for (let i = 0; i < nodes; i++) {
    for (let j = 0; j < nodes; j++) {
      dist[i][j] = graph[i][j]
    }
  }

  // 모든 노드를 중간 노드로 사용하여 최단 거리 계산
  for (let k = 0; k < nodes; k++) {
    for (let i = 0; i < nodes; i++) {
      for (let j = 0; j < nodes; j++) {
        // 기존 거리와 중간 노드를 거친 거리 중 더 작은 값 선택
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j]
        }
      }
    }
  }

  return dist
}

// 결과 출력
const shortestDistances = floydWarshall(graph)

console.log('모든 쌍 최단 거리 테이블:')
console.table(shortestDistances)

// 그래프를 표현하기 위한 인접 리스트 형태의 객체
const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 },
}

// 디익스트라 알고리즘 함수
function dijkstra(graph, startNode) {
  // 최단 거리 테이블을 초기화
  const distances = {}
  for (let node in graph) {
    distances[node] = Infinity // 초기에는 모든 거리를 무한대로 설정
  }
  distances[startNode] = 0 // 시작 노드의 거리는 0

  // 방문한 노드를 추적하기 위한 집합
  const visited = new Set()

  // 우선순위 큐 역할을 하는 배열
  const queue = []
  queue.push({ node: startNode, distance: 0 })

  while (queue.length > 0) {
    // 현재 큐에서 가장 짧은 거리를 가진 노드를 선택
    queue.sort((a, b) => a.distance - b.distance)
    const { node: currentNode, distance: currentDistance } = queue.shift()

    // 이미 방문한 노드는 스킵
    if (visited.has(currentNode)) continue
    visited.add(currentNode)

    // 현재 노드의 이웃을 확인
    for (let neighbor in graph[currentNode]) {
      const totalDistance = currentDistance + graph[currentNode][neighbor]

      // 더 짧은 거리가 발견되면 업데이트
      if (totalDistance < distances[neighbor]) {
        distances[neighbor] = totalDistance
        queue.push({ node: neighbor, distance: totalDistance })
      }
    }
  }

  return distances
}

// 예제 실행
const startNode = 'A'
const shortestDistances = dijkstra(graph, startNode)

console.log(`최단 거리 테이블 (${startNode}에서 시작):`, shortestDistances)

// BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색) 구현

/**
 * 그래프를 표현하는 예제
 * @type {Object} 그래프 인접 리스트
 */
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F', 'G'],
  D: [],
  E: [],
  F: [],
  G: [],
}

/**
 * BFS (너비 우선 탐색)
 * @param {Object} graph - 그래프 인접 리스트
 * @param {string} start - 탐색 시작 노드
 * @returns {string[]} - 탐색 순서
 */
function bfs(graph, start) {
  const visited = new Set() // 방문한 노드를 기록
  const queue = [start] // 큐 초기화
  const result = []

  while (queue.length > 0) {
    const node = queue.shift() // 큐에서 노드 제거
    if (!visited.has(node)) {
      visited.add(node) // 방문 처리
      result.push(node)

      // 인접 노드를 큐에 추가
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor)
        }
      }
    }
  }

  return result
}

/**
 * DFS (깊이 우선 탐색) - 재귀
 * @param {Object} graph - 그래프 인접 리스트
 * @param {string} node - 현재 노드
 * @param {Set} visited - 방문한 노드
 * @param {string[]} result - 탐색 결과
 * @returns {string[]} - 탐색 순서
 */
function dfsRecursive(graph, node, visited = new Set(), result = []) {
  if (!visited.has(node)) {
    visited.add(node) // 방문 처리
    result.push(node)

    for (const neighbor of graph[node]) {
      dfsRecursive(graph, neighbor, visited, result) // 재귀 호출
    }
  }

  return result
}

/**
 * DFS (깊이 우선 탐색) - 반복
 * @param {Object} graph - 그래프 인접 리스트
 * @param {string} start - 탐색 시작 노드
 * @returns {string[]} - 탐색 순서
 */
function dfsIterative(graph, start) {
  const visited = new Set() // 방문한 노드를 기록
  const stack = [start] // 스택 초기화
  const result = []

  while (stack.length > 0) {
    const node = stack.pop() // 스택에서 노드 제거
    if (!visited.has(node)) {
      visited.add(node) // 방문 처리
      result.push(node)

      // 인접 노드를 스택에 추가 (역순으로 추가하여 순서 유지)
      for (const neighbor of graph[node].slice().reverse()) {
        if (!visited.has(neighbor)) {
          stack.push(neighbor)
        }
      }
    }
  }

  return result
}

// 실행 예제
console.log('BFS 탐색 순서:', bfs(graph, 'A')) // A -> B -> C -> D -> E -> F -> G
console.log('DFS 탐색 순서 (재귀):', dfsRecursive(graph, 'A')) // A -> B -> D -> E -> C -> F -> G
console.log('DFS 탐색 순서 (반복):', dfsIterative(graph, 'A')) // A -> B -> D -> E -> C -> F -> G