그래프는 많은 애플리케이션에서 중요한 데이터 구조이며, 이를 효율적으로 탐색하는 것은 매우 중요합니다. 가중치가 없는 그래프의 경우, 방향성이 있거나 없음에 관계없이 두 가지 주요 알고리즘이 돋보입니다: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS). 이 두 방법 모두 두 노드 사이에 경로가 존재하는지 여부를 판단하고 해당 경로를 재구성할 수 있습니다. 특히, BFS는 가중치가 없는 그래프에서 최단 경로(간선 수 기준)를 찾는 것을 보장합니다.

깊이 우선 탐색 (DFS)

깊이 우선 탐색은 그래프의 한 시작 노드에서 출발하여 가능한 한 깊이 한 경로를 따라 이동하는 방식입니다. 더 이상 방문할 수 있는 노드가 없으면, 탐색은 이전 노드로 되돌아가 다른 분기를 탐색합니다. 이 방식은 재귀 호출 또는 명시적인 스택 자료구조를 사용하여 구현할 수 있습니다. DFS는 연결된 모든 노드를 탐색하고, 특정 노드의 도달 가능성을 확인하며, 시작 노드에서 목표 노드까지의 경로를 구성하는 데 유용합니다.

local DepthFirstSearcher = {}
DepthFirstSearcher.__index = DepthFirstSearcher

-- 새로운 DepthFirstSearcher 인스턴스를 생성합니다.
-- graphInstance는 getNeighbors(node) 메서드를 제공하는 그래프 객체여야 합니다.
function DepthFirstSearcher.create(graphInstance)
    local explorer = {
        graph = graphInstance,
        startNode = nil,
        visitedSet = {},
        parentMap = {} -- 특정 노드에 도달하기 직전의 노드를 저장
    }
    setmetatable(explorer, DepthFirstSearcher)
    return explorer
end

-- 대상 노드까지 도달 가능한지 확인합니다.
function DepthFirstSearcher:isNodeReachable(targetNode)
    return self.visitedSet[targetNode] == true
end

-- 특정 시작 노드로부터 도달 가능한 모든 노드를 탐색합니다.
function DepthFirstSearcher:traverseFrom(initialNode)
    self.startNode = initialNode
    self.visitedSet = {}
    self.parentMap = {}

    local function dfsRecursive(currentNode)
        self.visitedSet[currentNode] = true

        local neighbors = self.graph:getNeighbors(currentNode) -- 그래프 인스턴스는 getNeighbors 메서드를 가지고 있다고 가정
        for _, neighborNode in ipairs(neighbors) do
            if not self.visitedSet[neighborNode] then
                self.parentMap[neighborNode] = currentNode
                dfsRecursive(neighborNode)
            end
        end
    end

    dfsRecursive(initialNode)
end

-- 시작 노드에서 목표 노드까지의 경로를 반환합니다.
-- 경로가 없으면 nil을 반환합니다.
function DepthFirstSearcher:getPathTo(destinationNode)
    if not self:isNodeReachable(destinationNode) then return nil end

    local pathStack = {}
    local current = destinationNode
    while current ~= self.startNode do
        table.insert(pathStack, 1, current) -- 경로를 역순으로 구성
        current = self.parentMap[current]
        if not current then return nil end -- 경로 추적 중 오류 방지
    end
    table.insert(pathStack, 1, self.startNode)
    return pathStack
end

DFS 테스트 예시

-- 가상의 그래프 생성 함수 (예시용)
-- DGraph는 그래프 구현 클래스라고 가정하며, addVertex, addEdge, getNeighbors 메서드를 포함합니다.
local DGraph = {}
DGraph.__index = DGraph
function DGraph.new()
    local obj = { adj = {} }
    setmetatable(obj, DGraph)
    return obj
end
function DGraph:addVertex(v) self.adj[v] = self.adj[v] or {} end
function DGraph:addEdge(u, v) self:addVertex(u); self:addVertex(v); table.insert(self.adj[u], v) end
function DGraph:getNeighbors(v) return self.adj[v] or {} end

function createSampleDirectedGraph()
    local g = DGraph.new()
    g:addVertex("A")
    g:addVertex("B")
    g:addVertex("C")
    g:addVertex("D")
    g:addVertex("E")
    g:addVertex("F")

    g:addEdge("A", "B")
    g:addEdge("A", "C")
    g:addEdge("B", "D")
    g:addEdge("C", "E")
    g:addEdge("D", "F")
    --g:addEdge("E", "A") -- 순환 경로 추가

    return g
end

function runDfsTest()
    local myGraph = createSampleDirectedGraph()
    local dfsExplorer = DepthFirstSearcher.create(myGraph)

    dfsExplorer:traverseFrom("A") -- 'A'에서 탐색 시작

    print("Is D reachable from A? " .. tostring(dfsExplorer:isNodeReachable("D"))) -- true
    print("Is F reachable from A? " .. tostring(dfsExplorer:isNodeReachable("F"))) -- true
    print("Is Z reachable from A? " .. tostring(dfsExplorer:isNodeReachable("Z"))) -- false

    local pathToF = dfsExplorer:getPathTo("F")
    if pathToF then
        print("Path from A to F: " .. table.concat(pathToF, " -> ")) -- A -> B -> D -> F (또는 A -> C -> E -> F, DFS 특성상 특정 경로만 나옴)
    else
        print("No path from A to F found.")
    end

    local pathToC = dfsExplorer:getPathTo("C")
    if pathToC then
        print("Path from A to C: " .. table.concat(pathToC, " -> ")) -- A -> C
    else
        print("No path from A to C found.")
    end
end

runDfsTest()

너비 우선 탐색 (BFS)

너비 우선 탐색은 시작 노드에서 가까운 노드들을 먼저 탐색하는 방식입니다. 즉, 시작 노드에서 한 간선 떨어진 모든 노드를 방문한 다음, 두 간선 떨어진 노드들을 방문하는 식으로 점차 멀리 있는 노드들로 확장해 나갑니다. 이 알고리즘은 큐(Queue) 자료구조를 사용하여 구현되며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 가장 적합합니다.

local BreadthFirstSearcher = {}
BreadthFirstSearcher.__index = BreadthFirstSearcher

-- 새로운 BreadthFirstSearcher 인스턴스를 생성합니다.
-- graphInstance는 getNeighbors(node) 메서드를 제공하는 그래프 객체여야 합니다.
function BreadthFirstSearcher.create(graphInstance)
    local explorer = {
        graph = graphInstance,
        rootNode = nil,
        exploredNodes = {},
        pathParents = {} -- 특정 노드의 부모 노드를 저장하여 경로 추적
    }
    setmetatable(explorer, BreadthFirstSearcher)
    return explorer
end

-- 특정 노드의 도달 가능 여부 확인
function BreadthFirstSearcher:isNodeExplored(targetNode)
    return self.exploredNodes[targetNode] == true
end

-- 시작 노드로부터 도달 가능한 모든 노드를 탐색합니다.
function BreadthFirstSearcher:exploreGraphFrom(startingNode)
    self.rootNode = startingNode
    self.exploredNodes = {}
    self.pathParents = {}

    local discoveryQueue = {}
    self.exploredNodes[startingNode] = true
    table.insert(discoveryQueue, startingNode) -- 큐에 시작 노드 추가

    while #discoveryQueue > 0 do
        local currentNode = discoveryQueue[1]
        table.remove(discoveryQueue, 1) -- 큐에서 노드 추출 (FIFO)

        local adjacentNodes = self.graph:getNeighbors(currentNode)
        for _, neighbor in ipairs(adjacentNodes) do
            if not self.exploredNodes[neighbor] then
                self.pathParents[neighbor] = currentNode
                self.exploredNodes[neighbor] = true
                table.insert(discoveryQueue, neighbor) -- 이웃 노드를 큐에 추가
            end
        end
    end
end

-- 시작 노드에서 목표 노드까지의 최단 경로를 반환합니다.
-- 경로가 없으면 nil을 반환합니다.
function BreadthFirstSearcher:findShortestPath(endNode)
    if not self:isNodeExplored(endNode) then return nil end

    local shortestPath = {}
    local current = endNode
    while current ~= self.rootNode do
        table.insert(shortestPath, 1, current) -- 경로를 역순으로 구성
        current = self.pathParents[current]
        if not current then return nil end -- 경로 추적 중 오류 방지
    end
    table.insert(shortestPath, 1, self.rootNode)
    return shortestPath
end

BFS 테스트 예시

-- DFS 테스트에서 사용한 DGraph 클래스를 재사용합니다.

function createAnotherDirectedGraph()
    local graph = DGraph.new()
    graph:addVertex("0")
    graph:addVertex("1")
    graph:addVertex("2")
    graph:addVertex("3")
    graph:addVertex("4")
    graph:addVertex("5")

    graph:addEdge("0", "2")
    graph:addEdge("2", "0")
    graph:addEdge("2", "1")
    graph:addEdge("2", "3")
    graph:addEdge("2", "5")
    graph:addEdge("3", "2")
    graph:addEdge("3", "4")
    graph:addEdge("3", "5")
    --graph:addEdge("1", "4") -- 추가 간선

    return graph
end

function runBfsTest()
    local complexGraph = createAnotherDirectedGraph()
    local bfsExplorer = BreadthFirstSearcher.create(complexGraph)

    bfsExplorer:exploreGraphFrom("0") -- '0'에서 탐색 시작

    print("Is 3 explored from 0? " .. tostring(bfsExplorer:isNodeExplored("3"))) -- true
    print("Is 5 explored from 0? " .. tostring(bfsExplorer:isNodeExplored("5"))) -- true
    print("Is 4 explored from 0? " .. tostring(bfsExplorer:isNodeExplored("4"))) -- true

    local pathFrom0to5 = bfsExplorer:findShortestPath("5")
    if pathFrom0to5 then
        print("Shortest path from 0 to 5: " .. table.concat(pathFrom0to5, " -> ")) -- 0 -> 2 -> 5
    else
        print("No path from 0 to 5 found.")
    end

    local pathFrom0to4 = bfsExplorer:findShortestPath("4")
    if pathFrom0to4 then
        print("Shortest path from 0 to 4: " .. table.concat(pathFrom0to4, " -> ")) -- 0 -> 2 -> 3 -> 4
    else
        print("No path from 0 to 4 found.")
    end
end

runBfsTest()