Graph Data Structures and Algorithms by Ali Akbar Mohammadi
G
r
a
p
h
T
a
b
l
e
o
f
C
o
n
t
e
n
t
•
Definitions
•
Graph ADT
•
Data Structure for Graph
•
Graph Traversal
•
Transitive Closure
•
Directed Acyclic Graphs
•
Shortest Paths
•
Minimum Spanning Trees
Ali Akbar Mohammadi
2
G
r
a
p
h
•
A
graph
is a way of representing relationships that exist between
pairs of objects.
•
That is, a graph is a set of objects, called vertices, together with a
collection of pairwise connections between them, called edges.
Ali Akbar Mohammadi
3
G
r
a
p
h
•
Viewed abstractly, a
graph
G
is simply a set
V
of
vertices
and a
collection
E
of pairs of vertices from
V
, called
edges
.
•
Thus, a graph is a way of representing connections or relationships
between pairs of objects from some set
V
.
Ali Akbar Mohammadi
4
E
d
g
e
•
Edges in a graph are either
directed
or
undirected
.
•
An edge (
u
,
v
) is said to be
directed
from
u
to
v
if the pair (
u
,
v
) is ordered, with
u
preceding
v
.
•
An edge (
u
,
v
) is said to be
undirected
if the pair (
u
,
v
) is not ordered.
Ali Akbar Mohammadi
5
G
r
a
p
h
Ali Akbar Mohammadi
6
U
n
d
i
r
e
c
t
e
d
,
D
i
r
e
c
t
e
d
a
n
d
M
i
x
e
d
G
r
a
p
h
•
If all the edges in a graph are undirected, then we say the graph is an
undirected graph
.
•
Likewise, a
directed graph
, also called a
digraph
, is a graph whose
edges are all directed.
•
A graph that has both directed and undirected edges is often called a
mixed graph
.
Ali Akbar Mohammadi
7
E
x
a
m
p
l
e
•
Electrical wiring networks
•
Plumbing networks
•
City map
Ali Akbar Mohammadi
8
D
e
f
i
n
i
t
i
o
n
s
•
End vertices
(or
Endpoints
): The two vertices joined by an edge.
•
Origin:
If an edge is directed, its first endpoint is its
origin.
•
Destination:
the other is the
destination
of the edge.
•
Adjacent:
Two vertices u and v are said to be
adjacent
if there is an edge
whose end vertices are u and v.
•
Incident:
An edge is said to be
incident
to a vertex if the vertex is one of the
edge’s endpoints.
•
Outgoing edges:
The
outgoing edges
of a vertex are the directed edges
whose origin is that vertex.
•
Incoming edges:
The
incoming edges
of a vertex are the directed edges
whose destination is that vertex.
Ali Akbar Mohammadi
9
D
e
f
i
n
i
t
i
o
n
s
•
Degree:
The
degree
of a vertex v, denoted edeg(v), is the number of
incident edges of v.
•
In-degree
and
Out-degree:
The
in-degree
and
out-degree
of a vertex
v are the number of the incoming and outgoing edges of v, and are
denoted indeg(v) and outdeg(v), respectively.
•
Parallel edges
or
Multiple edges:
The definition of a graph refers to
the group of edges as a
collection
, not a
set
, thus allowing two
undirected edges to have the same end vertices, and for two directed
edges to have the same origin and the same destination. Such edges
are called
parallel edges
or
multiple edges
.
Ali Akbar Mohammadi
10
D
e
f
i
n
i
t
i
o
n
s
•
Self-loop:
An edge (undirected or directed) is a
self-loop
if its two
endpoints coincide.
•
Simple
Graph:
Graphs do not have parallel edges or self-loops.
•
Path:
A
path
is a sequence of alternating vertices and edges that starts at a
vertex and ends at a vertex such that each edge is incident to its
predecessor and successor vertex.
•
Cycle:
a path that starts and ends at the same vertex, and that includes at
least one edge.
•
Simple Path:
If each vertex in the path is distinct.
•
Simple Cycle:
if each vertex in the cycle is distinct, except for the first and
last one.
Ali Akbar Mohammadi
11
D
e
f
i
n
i
t
i
o
n
s
•
Directed Path:
A path such that all edges are directed and are
traversed along their direction.
•
Directed Cycle:
A cycle such that all edges are directed and are
traversed along their direction.
•
Acyclic:
A directed graph is
acyclic
if it has no directed cycles.
•
Reachable:
we say that u
reaches
v, and that v is
reachable
from u, if
G has a (directed) path from u to v.
•
Connected:
A graph is
connected
if, for any two vertices, there is a
path between them.
Ali Akbar Mohammadi
12
D
e
f
i
n
i
t
i
o
n
s
•
Strongly Connected:
A directed graph ~G is
strongly connected
if for
any two vertices u and v of ~G, u reaches v and v reaches u.
•
Subgraph:
A graph H whose vertices and edges are subsets of the
vertices and edges of G, respectively.
•
Spanning Subgraph:
A spanning subgraph of G is a subgraph of G that
contains all the vertices of the graph G.
•
Forest:
A graph without cycles.
•
Tree:
A connected forest, that is, a connected graph without cycles.
•
Spanning Tree:
A graph is a spanning subgraph that is a tree.
Ali Akbar Mohammadi
13
Ali Akbar Mohammadi
14
A
D
i
r
e
c
t
e
d
G
r
a
p
h
R
e
p
r
e
s
e
n
t
i
n
g
a
F
l
i
g
h
t
N
e
t
w
o
r
k
G
r
a
p
h
A
D
T
•
numVertices( )
: Returns the number of vertices of the graph.
•
vertices( )
: Returns an iteration of all the vertices of the graph.
•
numEdges( )
: Returns the number of edges of the graph.
•
edges( )
: Returns an iteration of all the edges of the graph.
•
getEdge(
u
,
v
)
: Returns the edge from vertex
u
to vertex
v
, if one
exists; otherwise return null. For an undirected graph, there is no
difference between getEdge(
u
,
v
) and getEdge(
v
,
u
).
Ali Akbar Mohammadi
15
G
r
a
p
h
A
D
T
•
endVertices(
e
)
: Returns an array containing the two endpoint vertices of
edge
e
. If the graph is directed, the first vertex is the origin and the second
is the destination.
•
opposite(
v
,
e
)
: For edge
e
incident to vertex
v
, returns the other vertex of
the edge; an error occurs if
e
is not incident to
v
.
•
outDegree(
v
)
: Returns the number of outgoing edges from vertex
v
.
•
inDegree(
v
)
: Returns the number of incoming edges to vertex
v
. For an
undirected graph, this returns the same value as does outDegree(
v
).
•
outgoingEdges(
v
)
: Returns an iteration of all outgoing edges from vertex
v
.
Ali Akbar Mohammadi
16
G
r
a
p
h
A
D
T
•
incomingEdges(
v
)
: Returns an iteration of all incoming edges to vertex
v
. For an undirected graph, this returns the same collection as does
outgoingEdges(
v
).
•
insertVertex(
x
)
: Creates and returns a new Vertex storing element
x
.
•
insertEdge(
u
,
v
,
x
)
: Creates and returns a new Edge from vertex
u
to
vertex
v
, storing element
x
; an error occurs if there already exists an
edge from
u
to
v
.
•
removeVertex(
v
)
: Removes vertex
v
and all its incident edges from the
graph.
•
removeEdge(
e
)
: Removes edge
e
from the graph.
Ali Akbar Mohammadi
17
D
a
t
a
S
t
r
u
c
t
u
r
e
s
f
o
r
G
r
a
p
h
s
•
In an
edge list
, we maintain an unordered list of all edges.
•
In an
adjacency list
, we additionally maintain, for each vertex, a
separate list containing those edges that are incident to the vertex.
•
An
adjacency map
is similar to an adjacency list, but the secondary
container of all edges incident to a vertex is organized as a map,
rather than as a list, with the adjacent vertex serving as a key.
•
An
adjacency matrix
provides worst-case
O
(1) access to a specific
edge (
u
,
v
) by maintaining an
n
×
n
matrix, for a graph with
n
vertices.
Ali Akbar Mohammadi
18
R
u
n
n
i
n
g
T
i
m
e
s
Ali Akbar Mohammadi
19
This content delves into the foundational concepts of graph data structures, covering topics such as graph traversal, transitive closure, minimum spanning trees, and more. Ali Akbar Mohammadi provides insight into the world of graphs, emphasizing the importance of vertices, edges, and the relationships they form. The content also explores the classification of graphs into undirected, directed, and mixed types, with real-world examples like electrical wiring networks and city maps. Definitions of key terms like endpoints, origin, destination, adjacent, incident, outgoing and incoming edges are also detailed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Graph Graph
Table of Content Table of Content Definitions Graph ADT Data Structure for Graph Graph Traversal Transitive Closure Directed Acyclic Graphs Shortest Paths Minimum Spanning Trees Ali Akbar Mohammadi 2
Graph Graph A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them, called edges. Ali Akbar Mohammadi 3
Graph Graph Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges. Thus, a graph is a way of representing connections or relationships between pairs of objects from some set V. Ali Akbar Mohammadi 4
Edge Edge Edges in a graph are either directed or undirected. An edge (u,v) is said to be directed from u to v if the pair (u,v) is ordered, with u preceding v. An edge (u,v) is said to be undirected if the pair (u,v) is not ordered. Ali Akbar Mohammadi 5
Graph Graph Ali Akbar Mohammadi 6
Undirected, Directed and Mixed Graph Undirected, Directed and Mixed Graph If all the edges in a graph are undirected, then we say the graph is an undirected graph. Likewise, a directed graph, also called a digraph, is a graph whose edges are all directed. A graph that has both directed and undirected edges is often called a mixed graph. Ali Akbar Mohammadi 7
Example Example Electrical wiring networks Plumbing networks City map Ali Akbar Mohammadi 8
Definitions Definitions End vertices (or Endpoints): The two vertices joined by an edge. Origin: If an edge is directed, its first endpoint is its origin. Destination: the other is the destination of the edge. Adjacent: Two vertices u and v are said to be adjacent if there is an edge whose end vertices are u and v. Incident: An edge is said to be incident to a vertex if the vertex is one of the edge s endpoints. Outgoing edges: The outgoing edges of a vertex are the directed edges whose origin is that vertex. Incoming edges: The incoming edges of a vertex are the directed edges whose destination is that vertex. Ali Akbar Mohammadi 9
Definitions Definitions Degree: The degree of a vertex v, denoted edeg(v), is the number of incident edges of v. In-degree and Out-degree: The in-degree and out-degree of a vertex v are the number of the incoming and outgoing edges of v, and are denoted indeg(v) and outdeg(v), respectively. Parallel edges or Multiple edges: The definition of a graph refers to the group of edges as a collection, not a set, thus allowing two undirected edges to have the same end vertices, and for two directed edges to have the same origin and the same destination. Such edges are called parallel edges or multiple edges. Ali Akbar Mohammadi 10
Definitions Definitions Self-loop: An edge (undirected or directed) is a self-loop if its two endpoints coincide. SimpleGraph: Graphs do not have parallel edges or self-loops. Path: A path is a sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to its predecessor and successor vertex. Cycle: a path that starts and ends at the same vertex, and that includes at least one edge. Simple Path: If each vertex in the path is distinct. Simple Cycle: if each vertex in the cycle is distinct, except for the first and last one. Ali Akbar Mohammadi 11
Definitions Definitions Directed Path: A path such that all edges are directed and are traversed along their direction. Directed Cycle: A cycle such that all edges are directed and are traversed along their direction. Acyclic: A directed graph is acyclic if it has no directed cycles. Reachable: we say that u reaches v, and that v is reachable from u, if G has a (directed) path from u to v. Connected: A graph is connected if, for any two vertices, there is a path between them. Ali Akbar Mohammadi 12
Definitions Definitions Strongly Connected: A directed graph ~G is strongly connected if for any two vertices u and v of ~G, u reaches v and v reaches u. Subgraph: A graph H whose vertices and edges are subsets of the vertices and edges of G, respectively. Spanning Subgraph: A spanning subgraph of G is a subgraph of G that contains all the vertices of the graph G. Forest: A graph without cycles. Tree: A connected forest, that is, a connected graph without cycles. Spanning Tree: A graph is a spanning subgraph that is a tree. Ali Akbar Mohammadi 13
A Directed Graph A Directed Graph Representing a Representing a Flight Network Flight Network Ali Akbar Mohammadi 14
Graph ADT Graph ADT numVertices( ): Returns the number of vertices of the graph. vertices( ): Returns an iteration of all the vertices of the graph. numEdges( ): Returns the number of edges of the graph. edges( ): Returns an iteration of all the edges of the graph. getEdge(u, v): Returns the edge from vertex u to vertex v, if one exists; otherwise return null. For an undirected graph, there is no difference between getEdge(u, v) and getEdge(v, u). Ali Akbar Mohammadi 15
Graph ADT Graph ADT endVertices(e): Returns an array containing the two endpoint vertices of edge e. If the graph is directed, the first vertex is the origin and the second is the destination. opposite(v, e): For edge e incident to vertex v, returns the other vertex of the edge; an error occurs if e is not incident to v. outDegree(v): Returns the number of outgoing edges from vertex v. inDegree(v): Returns the number of incoming edges to vertex v. For an undirected graph, this returns the same value as does outDegree(v). outgoingEdges(v): Returns an iteration of all outgoing edges from vertex v. Ali Akbar Mohammadi 16
Graph ADT Graph ADT incomingEdges(v): Returns an iteration of all incoming edges to vertex v. For an undirected graph, this returns the same collection as does outgoingEdges(v). insertVertex(x): Creates and returns a new Vertex storing element x. insertEdge(u, v, x): Creates and returns a new Edge from vertex u to vertex v, storing element x; an error occurs if there already exists an edge from u to v. removeVertex(v): Removes vertex v and all its incident edges from the graph. removeEdge(e): Removes edge e from the graph. Ali Akbar Mohammadi 17
Data Structures for Graphs Data Structures for Graphs In an edge list, we maintain an unordered list of all edges. In an adjacency list, we additionally maintain, for each vertex, a separate list containing those edges that are incident to the vertex. An adjacency map is similar to an adjacency list, but the secondary container of all edges incident to a vertex is organized as a map, rather than as a list, with the adjacent vertex serving as a key. An adjacency matrix provides worst-case O(1) access to a specific edge (u,v) by maintaining an n n matrix, for a graph with n vertices. Ali Akbar Mohammadi 18
Running Times Running Times Ali Akbar Mohammadi 19
