Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
Concepts
Digraphs
If a pair of vertices (u, v) is not the same as the pair (v, u).
-
-
Graphs Representations
Adjacency
matrix
The element in the ith row and the j th column is equal to 1 if there is an edge from the ith vertex to the j th vertex.
Adjacency lists
A collection of linked lists,
one for each vertex.
-
Paths and Cycles
A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.
A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once.
Searching
DFS
Starts a graph’s traversal at an arbitrary vertex by marking it
as visited. 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.
-
-
-
-
BFS
It 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, until all the vertices in the same connected component as the starting vertex are visited.
-
-
-
-
Sorting
Topological Sorting
The question is whether we can 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.
-
Two efficient algorithms
-
The second algorithm is based on a direct implementation of the decrease-(by one)-and-conquer technique: repeatedly, identify in a remaining digraph a source,which is a vertex with no incoming edges, and delete it along with all the edges
outgoing from it.
-