Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
A graph G = ⟨V, E⟩ is defined by a pair of two sets:
-
-
If a pair of edges is unordered, (u, v) is the same as (v, u).
u and v are adjacent to each other and are connected by the undirected edge (u, v).
u and v are endpoints of the edge (u, v) and are incident to this edge, which is also incident to its endpoints.
-
-
-
A weighted graph is a graph with numbers assigned to its edges, called weights or costs.
Traversing
DFS
On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. This process continues until a dead end is encountered, when the algorithm backs up one edge to the vertex it came from, continuing to try visiting unvisited vertices. It ends when backing up to the starting vertex.
-
Depth-first search forest: structure analogous to a tree, but has back edges that connect a vertex to its ancestor, other than the parent.
For adjacency matrix, the transversal time is Θ(|V|²).
For adjacency list, the transversal time is Θ(|V| + |E|).
BFS
Visits first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all the vertices in the same connected component as the starting vertex of another connected component of the graph.
Unlike DFS, BFS uses a queue to trace its operations.
Breadth-first search forest: instead of back edges, has cross edges, which connects not only to its ancestor, but any other vertex other than its parent.
Topological Sorting
-
To verify if the graph is a dag, perform DFS, taking note the order in which vertices are popped off the transversal stack. Reversing this order yields a solution to the topological sorting problem. Provided a back edge has been encountered, the digraph is not a dag, and topological sorting is impossible.
Another solution is identifying and removing sources, which are vertices with no incoming edges, and deleting them until there are none left. If there are no sources, the problem can't be solved by topological sorting.