广度优先搜索

Version >= 0.5.0

（尽管此示例是使用版本 v0.5 中引入的语法编写的，但它也可以在旧版本上进行少量修改。）

在用邻接列表表示的图上的广度优先搜索 （BFS）的实现使用 while 循环和 return 语句。我们将要解决的任务如下：我们有一系列人和一系列友谊（友谊是相互的）。我们想确定两个人之间的联系程度。也就是说，如果两个人是朋友，我们将返回 1; 如果一个人是另一个朋友的朋友，我们将返回 2，依此类推。

首先，让我们假设我们已经有一个邻接列表：Dict 映射 T 到 Array{T, 1}，其中键是人，值是该人的所有朋友。在这里，我们可以代表我们选择的任何类型的人; 在这个例子中，我们将使用 Symbol。在 BFS 算法中，我们将人员队列保持访问，并标记他们与原始节点的距离。

function degree(adjlist, source, dest)
    distances = Dict(source => 0)
    queue = [source]

    # until the queue is empty, get elements and inspect their neighbours
    while !isempty(queue)
        # shift the first element off the queue
        current = shift!(queue)

        # base case: if this is the destination, just return the distance
        if current == dest
            return distances[dest]
        end

        # go through all the neighbours
        for neighbour in adjlist[current]
            # if their distance is not already known...
            if !haskey(distances, neighbour)
                # then set the distance
                distances[neighbour] = distances[current] + 1

                # and put into queue for later inspection
                push!(queue, neighbour)
            end
        end
    end

    # we could not find a valid path
    error("$source and $dest are not connected.")
end

现在，我们将编写一个函数来构建一个给定一系列人的邻接列表，以及一系列 (person, person) 元组：

function makeadjlist(people, friendships)
    # dictionary comprehension (with generator expression)
    result = Dict(p => eltype(people)[] for p in people)

    # deconstructing for; friendship is mutual
    for (a, b) in friendships
        push!(result[a], b)
        push!(result[b], a)
    end

    result
end

我们现在可以定义原始函数：

degree(people, friendships, source, dest) =
    degree(makeadjlist(people, friendships), source, dest)

现在让我们测试一些数据的功能。

const people = [:jean, :javert, :cosette, :gavroche, :éponine, :marius]
const friendships = [
    (:jean, :cosette),
    (:jean, :marius),
    (:cosette, :éponine),
    (:cosette, :marius),
    (:gavroche, :éponine)
]

让以自己的步伐与自己相连：

julia> degree(people, friendships, :jean, :jean)
0

让和珂赛特是朋友，所以有学历：

julia> degree(people, friendships, :jean, :cosette)
1

Jean 和 Gavroche 通过珂赛特和 Marius 间接联系，所以他们的学位是 3：

julia> degree(people, friendships, :jean, :gavroche)
3

Javert 和 Marius 没有通过任何链接，因此会出现错误：

julia> degree(people, friendships, :javert, :marius)
ERROR: javert and marius are not connected.
 in degree(::Dict{Symbol,Array{Symbol,1}}, ::Symbol, ::Symbol) at ./REPL[28]:27
 in degree(::Array{Symbol,1}, ::Array{Tuple{Symbol,Symbol},1}, ::Symbol, ::Symbol) at ./REPL[30]:1