廣度優先搜尋

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