【julia学习篇】无向图的广度优先遍历迭代器写法

综合讨论区 Julia入门
1

仅为学习Julia迭代器而简单实现，假定本文中使用的无向图为连通图。

julia中关于迭代器的约定

一个简单的例子

a=[1,2,3,4,5]
for e in a
    println(e)

从状态出发

begin->1->2->3->4->5->end

换个视角

# value,(state) 

# 1, (2, 3, 4, 5)
#     2,(3, 4, 5)
#        3,(4, 5)
#           4,(5)
#              5 ()

考虑框架

iter(x)=isempty(x) ? nothing : x[1],2

function iter(x,state)
    state>length(x) && return nothing
    return x[state],state+1
end


next = iter(a)
while next !== nothing
    (i, state) = next
    # body
    println(i)
    next = iter(a, state)
end

Julia迭代器约定

Methods Brief description
iterate(iter) Returns either a tuple of the first item and initial state or nothing if empty
iterate(iter, state) Returns either a tuple of the next item and next state or nothing if no items remain 
for i in iter   # or  "for i = iter"
    # body
end

# is translated into:

next = iterate(iter)
while next !== nothing
    (i, state) = next
    # body
    next = iterate(iter, state)
end

相关文档：en zh
【入门系列视频】一起读文档

广度优先遍历(BFS)

BFS的非迭代实现

abstract type AbstractGraph end

function BFS(g::AbstractGraph)
    seq = []
    queue = []
    visted = Set()
    # 从节点1开始
    push!(queue, 1)
    push!(visted, 1)
    while !isempty(queue)
        u = popfirst!(queue)
        push!(seq, u)
        for v in neibor(g, u)
            v in visted && continue
            push!(queue, v)
            push!(visted, v)
        end
    end
    return seq
end

BFS的迭代器实现

import Base.iterate

function iterate(g::AbstractGraph)
    if g.n == 0
        return nothing
    else
        visited = Set()
        queue = []
        push!(visited, 1)
        for v in neibor(g, 1)
            push!(queue, v)
            push!(visited, v)
        end
        return 1, (visited, queue)
    end
end

function iterate(g::AbstractGraph, state)
    (visited, queue) = state
    isempty(queue) && return nothing
    u = popfirst!(queue)
    for v in neibor(g, u)
        v in visited && continue
        push!(queue, v)
        push!(visited, v)
    end
    return u, (visited, queue)
end

选择一种图的表示方法（邻接矩阵）

struct Graph <: AbstractGraph
    n::Int
    adj::Matrix
end

Graph(adj::Matrix) = Graph(size(adj, 1), adj)

isadj(g::Graph, u, v) = g.adj[u, v] == 1

neibor(g::Graph, u) = findall(!=(0), g.adj[u, :])

跑起来！

G = Graph([0 0 1 1 1; 1 0 0 1 1; 1 0 0 1 0; 0 1 1 1 0; 1 1 0 0 0])

for item in G
    println(item)
end

julia> 
1       
3
4
5
2

for item in BFS(G)
    println(item)
end

julia> 
1       
3
4
5
2
1 个赞