Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graph - Coggle Diagram
Graph
Topological Sorting
Problem
For every edges the vertex where starts is listed before the vertex at the end.
linear ordering
for Directed Acyclic Graph
DFS
Decrease-(by-once)-and-conquer
Representations
Adjacent Matrix
Adjacent Lists
Collection of linked lists
Represent the columns of the matrix
Weghed Graphs
Number assigned to edges
Shorted path find
Paths and Cycles
Path
Sequence of adjacent vertices
Cycle
Path that start and ends at the same vertex and does't transverse the same edge more than once
Search
Depth-First
Visit the adjacent vertex one by one until its not possible, than return one vertex
Eventually return to the starting vertex
is convenient to use a Stack
Breadth-First
is convenient to use a queue
Visit the all the adjacent vertices to a starting vertex
Then all the unvisited vertices two edgers apart from it
and so on...
Definition
Pairs of sets
Vertices (u,v)
Edges
Unordered
Adjacent each other
u and v are connected by undirected edge
They are endpoints of the edge
Indirect Graph
(u, v) != (v, u)
Directed Graph
every pair of vertices are connected by an edger
Connected Graph