breadth_first_search(graph::Dict{Int64,Array{Int64,1}}, start::Int64)

The breadth-first search (BFS) is an algorithm dedicated to traversing or searching for tree or graph data structures. It starts at a specified tree root (start) for exploring all connected neighbor nodes. The important feature is that the BFS automatically leaves the present depth and passes on to the next nodes at a deeper level. BFS is queue-based. For more information see: https://en.wikipedia.org/wiki/Breadth-first_search

Arguments

• graph::Dict{Int64,Array{Int64,1}}: Graph of the connected nodes
• start::Int64: Startpoint (first selected vertex) of the graph-traveling process

Examples

julia> import ClassicAlgorithmsCollections
julia> graph = Dict(1=> [2, 3], 2=> [3], 3=> [1, 4], 4=> [4])
julia> ClassicAlgorithmsCollections.breadth_first_search(graph, 3)
[3, 1, 4, 2]

depth_first_search(graph::Dict{Int64,Array{Int64,1}}, start::Int64)

The depth-first search (DFS) is an algorithm dedicated to traversing or searching for tree or graph data structures. It starts at a specified tree root (start) for exploring as far as possible at each branch. Afterthat the BFS starts automatically backtracking. DFS is stack-based. For more information see: https://en.wikipedia.org/wiki/Depth-first_search

Arguments

• graph::Dict{Int64,Array{Int64,1}}: Graph of the connected nodes
• start::Int64: Startpoint (first selected vertex) of the graph-traveling process

Examples

julia> import ClassicAlgorithmsCollections
julia> graph = Dict(1=> [2, 3], 2=> [3], 3=> [1, 4], 4=> [4])
julia> ClassicAlgorithmsCollections.depth_first_search(graph, 3)
[3, 1, 2, 4]

minimum_spanning_tree(graph::Dict{Int64,Array{Tuple{Int64,Int64},1}}))

The minimum spanning tree (MST) algorithm detects a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together. The MST algorithms focus is a) to exclude any cycles and b) to find the minimum possible total edge weight, which will create a spanning tree whose sum of edge weights is as small as possible. The Kruskal's algorithm is used to find the minimum spanning forest of an undirected edge-weighted graph. For more information see: https://en.wikipedia.org/wiki/Minimumspanningtree and https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Arguments

• graph::Dict{Int64,Array{Tuple{Int64,Int64},1}}: Graph of the connected nodes with the weights

Examples

julia> import ClassicAlgorithmsCollections
julia> graph_with_spanning_tree = Dict(1 => [(2, 10), (3, 6), (4, 5)], 2 => [(4, 15)], 3 => [(4, 4)]
julia> ClassicAlgorithmsCollections.minimum_spanning_tree(graph_with_spanning_tree)
[3 4 4; 1 4 5; 1 2 10]

shortest_path_tree(graph::Dict{Int64,Array{Tuple{Int64,Int64},1}}, u=nothing, v=nothing)

The Shortest Path Tree (SPT) algorithm solves the shortest path problem between every pair of vertices in a given edge-weighted directed Graph based on the Floyd–Warshall algorithm. Optional, the SPT also provides the total parts between a start- (u) and end- point (v). For more information see: https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

Arguments

• next::Array{Int64,2}: Vertex matrix of the connected nodes
• u::Int64: Startpoint of the to investigated path; optional
• v::Int64: Endpoint of the to investigated path; optional

Examples

julia> import ClassicAlgorithmsCollections
julia> graph = Dict( 1 => [(3, -2)], 2 => [(1, 4),(3, 3)], 3 => [(4, 2)], 4 => [(2, -1)]
julia> ClassicAlgorithmsCollections.shortest_path_tree(graph, 2, 4)
([0 -1 -2 0; 4 0 2 4; 5 1 0 2; 3 -1 1 0], [2, 1, 3, 4])

graph_cycle_check(graph::Dict{Int64,Array{Int64,1}})

The disjoint-set data structure principle is used to check if a direct or undirect graph contains a cycle. For this reason, the algorithm keeps the first track of a set of items partitioned into several disjoint (non-overlapping) subsets to find which subset a particular item is kept. This procedure is essential to figure out if two items are in the same subgroup. Next, the two subsets have to be merged into a single subset. For more information see: https://en.wikipedia.org/wiki/Disjoint-setdatastructure

Arguments

• graph::Dict{Int64,Array{Int64,1}}: Graph of the connected nodes

Examples

julia> import ClassicAlgorithmsCollections
julia> graph_cycle_true = Dict(1 => [2], 2 => [3], 3 => [1, 4])
julia> ClassicAlgorithmsCollections.graph_cycle_check(graph_cycle_true)
true
julia> graph_cycle_false = Dict(1 => [2], 2 => [5], 3 => [1, 4])
julia> ClassicAlgorithmsCollections.graph_cycle_check(graph_cycle_false)
false

graph_bridge_check(graph::Dict{Int64,Array{Int64,1}}))

For finding a bridge or more bridges in an undirect connected graph, the kind of connection has to be found, which can disconnect the graph by removing it. In case of disconnected undirected graphs, the bridge is the connection which increases number of disconnected components by removing it.

Arguments

• graph::Dict{Int64,Array{Tuple{Int64,Int64},1}}: Graph of the connected nodes

Examples

julia> import ClassicAlgorithmsCollections
julia> graph_bridge = Dict(1 => [2, 3, 4], 2 => [1, 3], 3 => [1, 2], 4 => [1, 5], 5 => [4])
julia> ClassicAlgorithmsCollections.graph_bridge_check(graph_bridge)
[4 5; 1 4]

boogle_word_check(
    graph::Dict{Int64,Array{String,1}},
    reference_words::Array{String,1},
)

For finding words (reference_words) in a field of chars, the boogle word check algorithm goes for every single char up and down to see if the sum of the chars build a word contained in th refernce word list. For this porpose the Depth First Traversal algorithm in function find_word is used.

Arguments

• graph::Dict{Int64,Array{String,1}}: Graph of the connected nodes of chars, which can build the words
• reference_words::Array{String,1}: Reference words to search for

Examples

julia> import ClassicAlgorithmsCollections
julia> word_list = ["GEEKS", "FOR", "QUIZ", "GO"]
julia> graph_boogle = Dict(
        1 => ["G", "I", "Z"],
        2 => ["U", "E", "K"],
        3 => ["Q", "S", "E"],
        4 => ["D", "O", "P"],
        5 => ["F", "O", "R"],
        )
julia> ClassicAlgorithmsCollections.boogle_word_check(graph_boogle, word_list)
["GEEKS", "QUIZ", "FOR"]