[Lua] 程式設計教學：實作圖 (Graph)

註：此處的圖，是指數學上的圖論 (graph theory)，而非電腦圖像 (computer graphics)。

圖 (graph) 是一種非線性、非階層的資料結構，由不重覆的點 (vertex or node) 和邊 (edge) 組成。理論上，樹 (tree) 是圖的特例，但圖的實作較複雜，通常不會直接拿圖取代樹。

圖本身是數學上的抽象理論，內部常見的實作方式如下：

• Edge list
• Adjacency matrix
• Adjacency list

Edge list 就是直接以陣列儲存成對的點，實作起來很簡單，但存取資料時會其效率會退化為線性，沒有充分利用到圖本身非線性所帶來的優點，實際上較少以 edge list 實作圖。

如同其名稱，adjacency matrix 以矩陣儲存圖；因矩陣內部通常是陣列，此種實作存取資料快速，但大量增減資料時效率較差，在圖較稀疏時，也比較耗空間。

Adjacency list 內部則是以串列儲存圖，此種實作在點較稀疏時，較 adjacency matrix 省空間，增減資料也比較有效率，但有時存取資料的效率會退化成線性。有一種變體是使用雜湊表來存圖，利用雜湊表非線性存取的特性避免存取效率退化。

圖有許多種變體，此處以單純的有向性圖 (simple digraph) 來展示如何實作圖，內部則利用 table 來做 adjacency list：

local Graph = {}
package.loaded["Graph"] = Graph

Graph.__index = Graph

function Graph:new()
    self = {}
    self._graph = {}
    setmetatable(self, Graph)
    return self
end

function Graph:hasNode(n)
    return self._graph[n] ~= nil
end

function Graph:hasEdge(u, v)
    return self._graph[u] ~= nil and self._graph[u][v] == true
end

function Graph:addNode(n)
    if self._graph[n] == nil then
        self._graph[n] = {}
    end
end

function Graph:addEdge(u, v)
    self:addNode(u)
    self:addNode(v)

    self._graph[u][v] = true
end

function Graph:removeEdge(u, v)
    if self._graph[u][v] == true then
        self._graph[u][v] = nil
    end
end

function Graph:removeNode(n)
    if self._graph[n] ~= nil then
        for p, _ in pairs(self._graph) do
            local isContinue = false

            if p == n then
                isContinue = true
            end

            if not isContinue then
                for q, _ in pairs(self._graph[p]) do
                    if q == n then
                        self._graph[p][q] = nil
                    end
                end
            end
        end

        self._graph[n] = nil
    end
end

return Graph

由於這裡僅是展示圖的實作方式，我們只實作基本的點和邊的增刪和存取，圖論有許多的運算，這裡就不一一展示。使用範例如下：

local graph = require("digraph")

do
    local g = graph:new()

    g:addEdge("a", "b")

    assert(g:hasNode("a"))
    assert(g:hasNode("b"))
    assert(g:hasEdge("a", "b"))
end

do
    local g = graph:new()

    g:addEdge("a", "b")
    g:addEdge("a", "c")

    assert(g:hasNode("a"))
    assert(g:hasNode("b"))
    assert(g:hasNode("c"))
    assert(g:hasEdge("a", "b"))
    assert(g:hasEdge("a", "c"))

    g:removeEdge("a", "c")

    assert(g:hasNode("a"))
    assert(g:hasNode("b"))
    assert(g:hasNode("c"))
    assert(g:hasEdge("a", "b"))
    assert(g:hasEdge("a", "c") == false)
end

do
    local g = graph:new()

    g:addEdge("a", "b")
    g:addEdge("a", "c")

    assert(g:hasNode("a"))
    assert(g:hasNode("b"))
    assert(g:hasNode("c"))
    assert(g:hasEdge("a", "b"))
    assert(g:hasEdge("a", "c"))

    g:removeNode("a")

    assert(g:hasNode("a") == false)
    assert(g:hasNode("b"))
    assert(g:hasNode("c"))
    assert(g:hasEdge("a", "b") == false)
    assert(g:hasEdge("a", "c") == false)
end