Please enable JavaScript.
Coggle requires JavaScript to display documents.
Elementary Graph Algorithm ----------Chapter 20---------- - Coggle Diagram
Elementary Graph Algorithm
----------Chapter 20----------
Searchin a graph means systematically following the edges of the graph, so as to visit the vertices of the graph.
A graph-searching algorithm can
discover much about the structure of a graph.
Algorithm
Searching their input graph
to obtain the structural information.
basic graph searching
Techniques
Heart of the field of graph algorithms.
Representation of graphs
Section 20.1
adjancency lists
Undirected graph
Undirected graph G: 5 vertices and 7 edges.
undirected graph, the sum of the lengths of all the adjacency lists is 2E
.
Amount of memory it requires.
Finding each edge in the graph time (each |V| adjacency list must be examined).
if
such as in a connected, undirected graph or a strongly connected, directed graph.
Finding each edge takes
time.
compact way to represent
sparse graphs
.
E is much less than V^2
Adjacency-list representation of G.
array Adj of V lists, one for each vertex in V. For each
, the adjacency list Adj[u] contains all the vertices v such that there is an edge
.
That is, Adj[u] consists of all the vertices adjacent to u in G.
array Adj can be treated as an attribute of the graph.
Notation
edge E
G.Adj[u]
weighted graphs
each edge has an associated weight given by a weight function w.
disadvantages
https://www.notion.so/Elementary-Graph-Algoritms-1e4932afb7248035b0e4dab08bf762ff?pvs=4
adjancency matrices
when the graph is
dense
, E is close to V^2
Adjancency-matrix representation of G. It can represent a weighed graph.
It assumes that the vertices are numbered 1, 2, ...,|V| in some arbitrary manner.
it requieres
memory and time.
The adjacency matrix A of an undirected graph is its own transpose
Directed graph.
Directed graph G: 6 vertices and 8 edges.
directed graph G, the sum of the lengths of
all the adjacency list is E
(V) vertices and (E) edges.
Breadth-first search
Section 20.2
breadth-first Tree
Initially containing the root (vertex s)
vertex u
predecessor or parent of v
if
u
is on the simple path in the tree from
the root
s
to vertex
v
.
u
is an ancestor of
v
and
v
is a descendant of
u
.
vertex v
edge (u, v)
"Each vertex reachable from s
has exactly one parent."
Just
s
has no parent because it's the root.
Atributes
Depth-first search
Section 20.3
order in which depth-first
search visit vertices
Topological sort
Section 20.4
real application of depth-first search
Strongly connected components
Section 20.5
second application of depth-first seach, directed graph.
