Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10 - Coggle Diagram
M10
graphs
paths and cycles
-
the length of the path is the number of vertices in the sequence minus 1, which is the same as the number of edges in the path
-
a cycle is a path that starts and ends at the same vertex and does not traverse the same edge more than once
-
-
weighted graphs
-
adjacency matrix
- the elements contain the weight of the edge or a spacial symbol if the edge does not exist
adjacency list
- the list node includes the weight of the edge
-
-
(u,v) = (v,u) -> u and v are adjacents and connected by undirected edges
-
(u,v) != (v,u) -> the edge is directed
-
-
-
-
topological sorting
-
-
possible edges in a DFS forest of a digraph
- tree edges
- back edges
- forward edges
- cross edges
-
-
linear ordering of vertices such that for every directed edge from u to v, vertex u comes before vertex v
-
depth-first search
-
-
if a back edge is found, the topological sorting cannot be done
-
-
-
DFS and BFS
-
depth-first search
visits unvisited vertices adjacent to the one currently being visited and backs up when the vertex is a dead end
if the algorithm halts and there are still unvisited vertices, it starts again in a new unvisited vertex
- it means the graph is not connected
traversal stack
- push a vertex when it is reached for the first time
- pop a vertex when it becomes a dead end
depth-first forest
- starting vertex is the first root
- tree edge
- back edge
efficiency
- adjacency matrix:
Theta(|V|²)
- adjacency list:
Theta(|V| + |E|)
provides two ordering of vertices
- the order vertices are visited for the first time (push)
- the order vertices become dead ends (pop)
-
-
breadth-first search
-
if there are still unvisited vertices when the algorithm stops, start again at an arbitrary unvisited vertex
- it means the graph is not connected
traversal queue
- the queue is initialized with the starting vertex
- mark the adjacent vertices as visited and add them to the queue
- remove the front vertex and do the same for the new front
breadth-first forest
- the starting vertex is the root of the first tree
- tree edge
- cross edge
efficiency
- adjacency matrix:
Theta(|V|²)
- adjacency list:
Theta(|V| + |E|)
-
-
-