Lua 程式設計教學:圖 (Graph)

PUBLISHED ON MAR 18, 2018 — PROGRAMMING

註:此處的圖,是指數學上的圖論 (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
TAGS: LUA, LUA 語法, GRAPH
comments powered by Disqus