Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10 - Coggle Diagram
M10
Graphs: a graph G = V , E
is defined by a pair of two sets
-
-
If these pairs of vertices are unordered, i.e., a pair of vertices (u, v) is the same as the pair (v, u), we say that the vertices u and v are adjacent
Graph Representations
Graphs for computer algorithms are usually repre-
sented in one of two ways: the adjacency matrix and adjacency lists
Weighted Graphs
is a graph (or digraph) with numbers assigned to its edges. These numbers are called weights or costs.
Paths and Cycles
Among the many properties of graphs, two are important for a
great number of applications: connectivity and acyclicity.
Depth-First Search
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.
At a dead end, the algorithm backs up one edge to the vertex
it came from and tries to continue visiting unvisited vertices from there.
It is also very useful to accompany a depth-first search traversal by construct-
ing the so-called depth-first search forest.
Topological Sorting
A directed graph, or digraph for short, is a graph with directions specified for all
its edges
-
There are only two notable differences between undirected and directed graphs in representing them: (1) the adjacency matrix of a directed graph does not have to be symmetric; (2) an edge in a directed graph has just one (not two) corresponding nodes in the digraph’s adjacency lists.
Breadth-First Search
is a traversal for the brave (the algorithm goes as far from “home” as it can), breadth-first search is a traversal for the cautious. 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.
Similarly to a DFS traversal, it is useful to accompany a BFS traversal by constructing the so-called breadth-first search forest. The traversal’s starting vertex serves as the root of the first tree in such a forest.