Verkon alkusolmu Lua pseudokoodi TIRA

-- http://repl.it/eqz/7

local WHITE = nil   -- not visited
local GRAY  = 1     -- visited
local RED   = 2     -- visited and possible startvertex (must have one)

-- visit vertex and mark visited
local function visit(L, color, startvertex, i)
    -- if we can access a startvertex it can not be the startvertex, so we remove it.
    if (color[i] == RED) then
        startvertex[i] = nil
        startvertex.count = startvertex.count-1
    end

    -- if we have not yet visited this vertex, visit it
    if (color[i] == WHITE) then
        -- mark visited
        color[i] = GRAY

        -- visit all it's neighbours
        for j = 1, #L[i] do
            visit(L, color, startvertex, L[i][j])
        end
    end
end

-- takes in an adjacency list, outputs true or false
local function hasstartvertex(L)
    -- list of start vertexes and count of them
    local startvertex = {count = 0}
    -- vertex colors, see top of code
    local color = {}

    -- go through all vertexes, visit them and their adjacents and mark the
    -- starting node as possible starvertex. We only go through not visited vertexes
    for i = 1, #L do
        if (color[i] == WHITE) then
            -- visit the vertex and it's adjacents
            visit(L, color, startvertex, i)

            -- set the vertex as possible startvertex
            startvertex[i] = true
            startvertex.count = startvertex.count+1
            color[i] = RED
        end
    end

    -- in the end there must be only one start vertex since start vertexes can't
    -- be reached from each other.
    return startvertex.count == 1
end

-- Test lists:

-- complex net, false
local L1 = {
    {2, 3},
    {1, 4},
    {6},
    {},
    {1, 3},
    {},
    {4},
}
-- complex net, true
local L2 = {
    {2, 3},
    {1, 4},
    {6},
    {},
    {1, 3},
    {},
}

-- loop, true
local L3 = {
    {2},
    {3},
    {4,2},
    {1},
}

print(hasstartvertex(L1), "expected", false)
print(hasstartvertex(L2), "expected", true)
print(hasstartvertex(L3), "expected", true)