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