procedure dfs(vertex v)
{
mark v as visited
for each w adjacent to v
if w unvisited
dfs(w)
}
Breadth-First Search
procedure BFS(vertex s) {
create a queue Q
enqueue s onto Q
mark s as visited
while Q is not empty
{
dequeue a vertex from Q into v
for each w adjacent to v
{
if w unvisited
{
mark w as visited
enqueue w onto Q
}
}
}
}
The graph can include negative weights.
This algorithm also allows us to detect cycles if the diagonal is initialized to inf and not to zero. If any of the diagonal values are changed, then the graph contains a cycle. Basically, if the cost / distance from node A to node A is not inf, it contains a cycle.
"Red is current min. Yellow is sorted list. Blue is current item." ~Wikipedia
So blue iterates through the list, comparing values as it goes along. The current minimum value is stored in red. By the time the end of the list is reached (with blue), the value that is red at that time, will be the smallest value in the "active part" of the list.
It is moved to the end of the "passive section", marked in yellow. Once it is yellow, it doesn't need to search it again, as it's already where it should be.
Please note: The algorithm doesn't really use colours. They are just for visualisation.
"Selection sort" because it selects the smallest value and works with that.