Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, Topological Sorting, Search Algorithms - Coggle Diagram
Graphs
Paths
-
Types of paths
-
Directed path
sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed from the vertex listed first to the vertex listed next
-
-
Weighted graphs
Graphs with numbers, weight costs, assigned to its edges
If represented by a matrix, the edge on the matrix will receive the weigth value
If represented by a list, the node of the list will have to be modified to receive the adjacent node and the weight value
Graph representation
-
Adjacency list
Collection of linked lists, one for each vertice, that stores all adjacent vertices
Topological Sorting
Algorithm
-
- Solves the topological sorting problem
Two ways
- Perform a DFS traversal and note the order in which vertices becomes dead-ends. Reverse that order and it will answer the topological sorting problem
- Repeatedly identify in a remaining digraph a vertex with no incoming edges (source). Delete it along with all the edges outgoing from it. The order in which the vertices are deleted yields a solution to the topological sorting problem
For a certain digraph, can we list its 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?
-
The digraph needs, and it is enough, to be a dag
Search Algorithms
Depth-First Search (DFS)
-
-
-
When at a dead end, the algorithm backs up onde edge and tries to go on again
If unvisited vertices will still remain, the DFS shall be restarted at one of them
-
Breadth-First Search
-
-
-
Keeps doing it until all vertices in the same connected component as the starting vertex are visited