Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, Breadth-First Search, Depth-First Search, a collection of points…
-
-
-
a collection of points in the plane called vertices or "nodes", some of them connected by line segments called edges or arcs
-
-
-
-
-
is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list's vertex
-
starts a graph traversal at an arbitrary vertex by marking ir as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in.
ir proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on
-
-
-
-
-
to list a Digraph vertices in such an order that for every edge in the graph, the vertex where the edge starts is listed before the vertex where the edge ends
If a digraph has no directed cycles, the topological sorting problem for it has a solution
Implemented with BST:
- Start the search on the origin
- When the destination is reached, stop the search
- To reconstruct the path: auxiliary array to store predecessors