Please enable JavaScript.
Coggle requires JavaScript to display documents.
22.Elementary Graph Algorithms - Coggle Diagram
22.Elementary Graph Algorithms
22.1 Representations of Graphs
Section 22.1 discusses the two most common computational representations of graphs: as
adjacency lists
and as
adjacency matrices.
Adjacency lists
if G is an undirected graph, the sum of the lengths of all the adjacency lists is 2 jEj,
For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of
memory it requires is O(|V| + |E|).
A potential
disadvantage of the adjacency-list representation
is that it provides no quicker way to determine whether a given edge .u; / is present in the graph than to search for in the adjacency list AdjOEu. An adjacency-matrix representation of the graph remedies this disadvantage, but at the cost of using asymptotically more memory
If G is a directed graph, the sum of the lengths of all the adjacency lists is jEj,
Adjacency-matrix
Since in an undirected graph, .(u,v) and .(v; u) represent the same edge, the adjacency matrix A of an undirected graph is its own transpose: A = AT, i.e,
A is symmetric
.
In some applications, it pays to store only the entries on and above the diagonal of he adjacency matrix, thereby
cutting the memory needed to store the graph almost in half
The adjacency matrix of a graph
requires O(V^2) memory,
independent of the number of edges in the graph..
Like the adjacency-list representation of a graph,
an adjacency matrix can represent a weighted graph
. For example, if G D .V;E/ is a weighted graph with edgeweight
function w, we can simply store the weight w.u; / of the edge .u; / 2 E as the entry in row u and column of the adjacency matrix.
22.3 Depth-first Search (DFS)
Section 22.3 presents
depth-first search (DFS)
and proves some
standard results about the order in which depth-first search visits vertices.
The predecessor subgraph of a depth-first search forms a depth-first forest comprising
several depth-first trees. The edges in E are tree edges.
property of depth-first search is that the predecessor subgraph G does indeed
form a forest of trees
, since the structure of the depth first trees exactly mirrors the structure of recursive calls of DFS-VISIT. That is, u D : if and only if DFS-VISIT.G; / was called during a search of u’s adjacency list. Additionally, vertex is a descendant of vertex u in the depth-first forest if and only if is discovered during the time in which u is gray
Another important property of depth-first search is that discovery and finishing
times have
parenthesis structure
. (page 606)
Corollary 22.8 (nesting of descendants’ intervals)
Vertex is a proper descendant of vertex u in the depth-first forest for a (directed or undirected) graph G if and only if u:d < v:d < v:f < u:f .
Theorem 22.9 (
White-path theorem
) In a depth-first forest of a (directed or undirected) graph G D .V;E/, vertex is a descendant of vertex u if and only if at the time u:d that the search discovers u, there is a path from u to consisting entirely of white vertices.
Classification of edges
(page 630)
22.4 Topological Sort
22.4 provides our first real application of depth-first search:
topologically sorting
a directed acyclic graph.
We can perform a topological sort in time
O(.V + E)
, since depth-first search takes ‚.O(.V + E) time and it takes O(1) time to insert each of the jV j vertices onto the front of the linked list.
Lemma 22.11 A directed graph G is acyclic if and only if a depth-first search of G yields no back edges.
Theorem 22.12 TOPOLOGICAL-SORT produces a topological sort of the directed acyclic graph provided as its input. (page 614)
22.5 Strongly Connected Components
A second application of depth-first search, finding the
strongly connected components
of a directed graph, is the topic of Section 22.5.
22.2 Breadth-first Search (BST)
Conecta com o capitulo 24 (MIT OCW 2005)
Link
Section 22.2 presents a simple graph-searching algorithm called
breadth-first search (BFS)
and shows how to create a breadth-first tree.
Prim’s minimum-spanning tree algorithm
(Section 23.2) and
Dijkstra
’s single-source shortest-paths algorithm (Section 24.3) use ideas similar to those in breadth-first search.
The algorithm works
on both directed and undirected graphs.
This algorithm discovers all vertices at distance k from s before discovering any vertices at distance k+1.
Breadth-first search constructs a
breadth-first tree
, initially containing only its root, which is the source vertex s.
This while loop maintains the following
invariant
: At the test in line 10, the queue Q consists of the set of gray vertices.
The results of breadth-first search may depend upon the order in which the neighbors of a given vertex are visited in line 12: the breadth-first tree may vary, but the
distances d computed by the algorithm will not. (See
Exercise 22.2-5.)
The following corollary shows that the d values at the time that vertices are
enqueued are
monotonically increasing over time
. (page 599)
Theorem 22.5 (Correctness of breadth-first search) page 600
22. Introduction
This chapter presents methods for
representing
a graph
and for
searching
a graph
Appendix B
B.4 Graphs
The cycle is simple if, in addition, v1; v2;... ;vk are distinct.
A directed graph is strongly connected if it has only one strongly connected component.
B.2 Relations
A relation that is reflexive, symmetric, and transitive is an equivalence relation.
B1. Sets
B3. Functions
B.5 Trees
A free tree is a connected, acyclic, undirected graph
Properties and proofs page 1174