Please enable JavaScript.
Coggle requires JavaScript to display documents.
M11 - Algorithms and Data Structures - Coggle Diagram
M11 - Algorithms and Data Structures
1 Introduction
1.4 Fundamental Data Structures
Graphs
a graph is informally thought of as a collection of points in the plane called
“vertices” or “nodes"
some of them connected by line segments called
“edges” or “arcs”
Formally, a graph
G = (V,E)
is defined by a pair of two sets: a finite nonempty set V of items called
vertices
and a set E of pairs of these items called
edges
.
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
and that they are
connected by the undirected edge (u, v)
We call the
vertices u and v endpoints of the edge (u, v)
and say that
u and v are incident to this edge
;
we also say that the edge (u, v) is incident to its endpoints u and v
A graph G is called
undirected
if every edge in
it is undirected.
If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the edge (u, v) is
directed
from the vertex u, called the edge’s
tail
, to the vertex v, called the edge’s
head
.
We also say that the edge (u, v) leaves u and enters v.
A graph whose every edge is directed is called
directed
. Directed graphs are also called
digraphs
Our definition of a graph does not forbid loops. Unless explicitly stated otherwise, we will consider graphs without loops
we have the following inequality for the number of edges |E| possible in an undirected graph with |V| vertices and no loops:
0 ≤ |E| ≤ |V| (|V| − 1) / 2
A graph with every pair of its vertices connected by an edge is called
complete
.
A standard notation for the complete graph with |V | vertices is K|V|
A graph with relatively few possible edges missing is called
dense
.
a graph with few edges relative to the number of its vertices is called
sparse
.
Graph Representations
1. the adjacency matrix
a graph with
n vertices is an n × n
boolean matrix with one row and one column for each of the graph’s vertices
in which 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 and equal to
0 if there is no such edge
always symmetric, i.e., A[i, j] = A[j, i] for every 0 ≤ i, j ≤ n − 1
If a graph is sparse, the adjacency list representation may use less space than the corresponding adjacency matrix despite the extra storage consumed by pointers of the linked lists
1 more item...
2. adjacency lists
a collection of linked lists
, one for each vertex, that contain all the vertices adjacent to the list’s vertex (i.e., all the vertices connected to it by an edge)
Usually, such lists start with a header identifying a vertex for which the list is compiled
adjacency lists indicate columns of the adjacency matrix that, for a given vertex, contain 1’s.
Weighted Graphs
A weighted graph (or weighted digraph) is a graph (or digraph) with
numbers assigned to its edges.
These numbers are called
weights or
costs.
An interest in such graphs is motivated by numerous real-world applications, such as finding the shortest path between two points
If a weighted graph is represented by its adjacency matrix, then its element A[i, j] will simply contain the weight of the edge from the ith to the j th vertex if there is such an edge and a special symbol, e.g., ∞ if there is no such edge
Such a matrix is called the weight matrix or cost matrix
1 more item...
Paths and Cycles
Among the many properties of graphs, two are important for a great number of applications: connectivity and acyclicity
Both are based on the notion of a path
A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends woth v
If all vertices of a path are distinct, the path is said to be
simple
.
The
length
of a path is the total number of vertices in the vertex sequence defining the path minus 1,which is the same as the number of edges in the path
1 more item...
3 Brute Force and
Exhaustive Search
3.5 Depth-First Search and Breadth-First Search
depth-first search (DFS)
starts a graph’s traversal at an arbitrary vertex by marking it as visited
the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in
This process continues until a dead end — a vertex with no adjacent unvisited vertices — is encountered
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
If unvisited vertices still remain, the depth-first
search must be restarted at any one of them
It is convenient to use a
stack
to trace the operation of depth-first search
1 more item...
breadth-first search (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.
If there still remain unvisited vertices, the algorithm has to be restarted at an arbitrary vertex of another connected component of the graph.
It is convenient to use a
queue
On each iteration, the algorithm identifies all unvisited vertices that are adjacent to the front vertex, marks them as visited, and adds them to the queue; after that, the front vertex is removed from the queue
Breadth-first search has the same efficiency as depth-first search
BFS can be used to
check connectivity and acyclicity of a graph
1 more item...
4 Decrease-and-Conquer
4.2 Topological Sorting
for topological sorting to be possible, a
digraph in question must be a dag (directed acyclic graph)
It turns out that being a dag is not only necessary but also sufficient for topological sorting to be possible
an important problem for directed graphs
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.
Conversely, if a DFS forest of a digraph has no back edges, the digraph is a
dag (directed acyclic graph)
, an acronym for directed acyclic graph
As to applications of topological sorting in computer science, they include instruction scheduling in program compilation, cell evaluation ordering in spreadsheet formulas, and resolving symbol dependencies in linkers.