CS计算机代考程序代写 data structure c++ algorithm 19_Graph_Introduction.pdf

19_Graph_Introduction.pdf

Lecture 19
Graphs and Graph Algorithms

EECS 281: Data Structures & Algorithms

Data Structures & Algorithms

Defining Graphs

Formal Definition: Graph
• Definition: A graph G = (V, E) is a set of

vertices V = {v1, v2, …} together with a set
of edges E = {e1, e2, …} that connect pairs
of vertices.

• Edges are often represented as ordered
pairs, such as em = (vs, vt).

Is this a graph?

7850

8848

Is this a graph?

7850

8848

Graph: More Detail
• In general

– Parallel edges are allowed
– Self-loops are allowed

• However, graphs without parallel edges
and without self-loops are called simple
graphs

• In general, assume a graph is simple
unless explicitly specified

Is this a simple graph?

7850

8848

Is this a simple graph?

7850

8848

Graphs: Definitions
• Simple Path: sequence of edges leading

from one vertex to another with no vertex
appearing twice

• Connected Graph: a simple path exists
between any pair of vertices

• Cycle: simple path, except that first and
final nodes are the same

Graphs: Directed vs. Undirected
• Directed Graph or “digraph”

– Edges have direction (one-way)
– Nodes on edges form ordered pairs

• Order of vertices in edge is important
• en = (u, v) means there is an edge from u to v

• Undirected Graph
– Nodes on edges form unordered pairs

• Order of vertices in edge is not important
• en = (u, v) means there is an edge between u and v

Directed vs. Undirected

2 1

Undirected Graph Directed Graph

Graphs: Weighted Graphs
Edges may be ‘weighted’
• Think of weight as the “distance between

nodes” or “cost to traverse the edge”
• In undirected graphs, weights may be

different for sets of parallel edges
• Algorithms often search a graph for a path

(unweighted), or least cost path (weighted)

Directed or Undirected?
Weighted or Unweighted?

Data Structures & Algorithms

Defining Graphs

A Board Game

https://www.daysofwonder.com/tickettoride/en/usa/
15

Data Structures & Algorithms

Graph Implementations

Graphs: Data Structures
• Complete Graph

– All possible edges (|E| = |V| * |V – 1| / 2 » |V|2)
• Dense Graph

– Many edges (|E| » |V|2)
– Represent as adjacency matrix (adjmat)

• Sparse Graph
– Few edges (|E| << |V|2) or (|E| » |V|) – Represent as adjacency list (adjlist) 20 Complete vs. Dense vs. Sparse 21 1 5 43 2 Sparse GraphDense Graph 1 5 43 2 Complete Graph 1 5 43 2 Complete, Dense, or Sparse? 22 44 17 7850 8848 62 54 Adjacency Matrix SFO LAX DFW ORD MIA JFK BOS SFO 0 1 1 1 0 0 1 LAX 1 0 1 0 1 0 0 DFW 1 1 0 1 1 0 0 ORD 1 0 1 0 0 1 1 MIA 0 1 1 0 0 1 1 JFK 0 0 0 1 1 0 1 BOS 1 0 0 1 1 1 0 23 Distance Matrix SFO LAX DFW ORD MIA JFK BOS SFO 0 337 1464 1846 0 0 2704 LAX 337 0 1235 0 2342 0 0 DFW 1464 1235 0 802 1121 0 0 ORD 1846 0 802 0 0 740 867 MIA 0 2342 1121 0 0 1090 1258 JFK 0 0 0 740 1090 0 187 BOS 2704 0 0 867 1258 187 0 24 Adjacency List Note: Adjacency list nodes can contain distances 25 SFO LAX … LAX DFW SFO DFW … ORD BOS MIA DFW SFO LAX ORD MIA Graphs: Data Structures Adjacency Matrix Implementation • |V| x |V| matrix representing graph • Directed vs. undirected – Directed adjmat has to/from – Undirected adjmat only needs ~V2/2 space • Unweighted vs. weighted – Unweighted: 0 = no edge, 1 = edge – Weighted: ¥ = no edge, value = edge 26 Undirected Distance Matrix SFO LAX DFW ORD MIA JFK BOS SFO ¥ 337 1464 1846 ¥ ¥ 2704 LAX 337 ¥ 1235 ¥ 2342 ¥ ¥ DFW 1464 1235 ¥ 802 1121 ¥ ¥ ORD 1846 ¥ 802 ¥ ¥ 740 867 MIA ¥ 2342 1121 ¥ ¥ 1090 1258 JFK ¥ ¥ ¥ 740 1090 ¥ 187 BOS 2704 ¥ ¥ 867 1258 187 ¥ 27 Representing Infinity in C++ • #include • Use numeric_limits::infinity()

– Adding, subtracting, multiplying and dividing finite
values often does nothing to it

– Multiplying by 0 results in 0 (Visual Studio) or nan (not
a number) in g++

– Dividing infinity by itself results in 1 (Visual Studio) or
nan (g++)

– Subtracting infinity from itself results in 0 (Visual
Studio) or nan (g++)

• Don’t use numeric_limits::max()
28

Graphs: Data Structures
Adjacency List
• Assume random distribution of edges
• ~E/V edges on each vertex list
• Access vertex list: O(1)
• Find edge on vertex list: O(E/V)
• Average cost for individual vertex is O(1 + E/V)
• Cost for all vertices is V x O(1 + E/V) = O(V + E)

Graphs: Data Structures
Adjacency List
• Directed vs. undirected

– Directed adjlist contains each edge once in edge set
– Undirected adjlist contains each edge twice in edge

set
• Unweighted vs. weighted

– Unweighted: nothing = no edge, = edge
– Weighted: nothing = no edge, =

edge

O(1) to access a vertex list?

SFO

LAX

LAX DFW

SFO DFW …

ORD BOS

MIA

DFW SFO LAX ORD MIA

ORD

MIA

SFO DFW

LAX DFW …

JFK BOS

JFK

JFK ORD MIA BOS

BOS SFO ORD MIA JFK

BOS

Data Structures & Algorithms

Graph Implementations

Data Structures & Algorithms

Graph Algorithms

Graphs: Complexity
Complexity of graph algorithms is typically
defined in terms of:
• Number of edges |E|, or
• Number of vertices |V|, or
• Both

Graph Algorithm Questions
• Task: Determine whether non-stop flight from X to Y exists.
• Worst/best/average complexity for both representations?

SFO LAX DFW ORD MIA JFK BOS

SFO ¥ 337 1464 1846 ¥ ¥ 2704
LAX 337 ¥ 1235 ¥ 2342 ¥ ¥
DFW 1464 1235 ¥ 802 1121 ¥ ¥
ORD 1846 ¥ 802 ¥ ¥ 740 867
MIA ¥ 2342 1121 ¥ ¥ 1090 1258
JFK ¥ ¥ ¥ 740 1090 ¥ 187
BOS 2704 ¥ ¥ 867 1258 187 ¥

A
dj

ac
en

M
at

rix
A

dj
ac

en
cy

Worst: O(1)
Best: O(1)
Avg: O(1)

Worst: O(V)
Best: O(1)
Avg: O(1 + E/V)

Graph Algorithm Questions
• Task: What is the closest other airport starting at X?
• Worst/best/average complexity for both representations?

SFO LAX DFW ORD MIA JFK BOS

A
dj

ac
en

M
at

rix
A

dj
ac

en
cy

Worst: O(V)
Best: O(V)
Avg: O(V)

Worst: O(V)
Best: O(1)
Avg: O(1 + E/V)

Graph Algorithm Questions
• Task: Determine if ANY flights depart from airport X.
• Worst/best/average complexity for both representations?

SFO LAX DFW ORD MIA JFK BOS

A
dj

ac
en

M
at

rix
A

dj
ac

en
cy

Worst: O(V)
Best: O(1)
Avg: O(V)

Worst: O(1)
Best: O(1)
Avg: O(1)

Graph Algorithm Questions
• Associate a distance with each edge
• Associate a cost with each edge
• Describe an algorithm to determine

greatest distance for least cost (ratio) that
can be flown from JFK on a non-stop flight

• Give complexity

JFK
ORD
740
$200

MIA
1090
$600

BOS
187
$400

Route Planning
Task: determine the most efficient route (i.e.
lowest cost) flown from X to Y on any trip,
non-stop or connecting

Single-Source Shortest Path
• Find the shortest path to get to any vertex from

some given starting point
• Depth First Search (DFS)

Only works on trees; may find the wrong answer due to
multiple paths in graphs

• Breadth First Search (BFS)
Works for unweighted edges or where all weights are
considered the same

• Dijkstra’s Algorithm
Works for weighted edges

Depth-First vs. Breath-First

Depth-First Search Breadth-First Search

Depth-First Search
Given a graph G = (V, E), explore the edges
of G to discover if any path exists from the
source s to the goal g

• Use a stack
• Algorithm works on graphs and digraphs
• Path discovered may be a shortest path,

but it is not guaranteed to be the shortest

Depth-First Search
Given a graph G = (V, E), explore the edges
of G to discover if any path exists from the
source s to the goal g

BOS:2704SFO:0

ORD:1846

DFW:1464

LAX:337MIA:2342

Stack

DFS Total:3769JFK:1090

JFK:1090

Depth-First Search
Algorithm GraphDFS

Mark source as visited
Push source to Stack
While Stack is not empty

Get/Pop candidate from top of Stack
For each child of candidate

If child is unvisited
Mark child visited
Push child to top of Stack
If child is goal

Return success
Return failure

Example

discovery edge
back edge

A discovered vertex
A undiscovered vertex

unexplored edge

Use Depth-First
Search to discover if a
path exists from A to E.

1)
C D

Example (cont.)

B C

B
C

B C

B
C
D

B
C

C D

DFS: Analysis of Adjacency List
• DFS:

– Called for each vertex at most once – O(V)
– adjlist for each vertex is visited at most once

and set of edges is distributed over set of
vertices – O(1 + E/V)

• O(V + E): linear with number of vertices
and edges

DFS: Analysis of Adjacency Matrix
• DFS:

– Called for each vertex at most once – O(V)
– adjmat row for each vertex is visited at most

once – O(V)

• O(V2): quadratic with number of vertices

Breadth-First Search
Given an unweighted graph G = (V, E),
explore the edges of G to discover a
shortest path from source s to goal g, if any
exists

• Use a queue
• Algorithm works on graphs and digraphs
• Discovers a shortest path only on

unweighted graphs or where all edges
have equal weight

Breadth-First Search
Given an unweighted graph G = (V, E),
explore the edges of G to discover a
shortest path from source s to goal g

BOS:2704SFO:0

ORD:1846

DFW:1464

LAX:337

MIA:2342

Queue (Front)
BFS Total:2891JFK:187

JFK:1090

Breadth-First Search
Algorithm GraphBFS

Mark source as visited
Push source to back of Queue
While Queue is not empty

Get/Pop candidate from front of Queue
For each child of candidate

If child is unvisited
Mark child visited
Push child to back of Queue
If child is goal

Return success
Return failure

Example

discovery edge
back edge

A discovered vertex
A undiscovered vertex

unexplored edge

Use Breadth-First
Search to discover if a
path exists from A to F.

1)
CB

Example (cont.)

3)
CB

F
L2

5)
CB

F
L2

Example (cont.)

F
L2

BFS: Analysis of Adjacency List
• BFS:

– Called for each vertex at most once – O(V)
– adjlist for each vertex is visited at most once

and set of edges is distributed over set of
vertices – O(1 + E/V)

• O(V + E): linear with number of vertices
and edges

BFS: Analysis of Adjacency Matrix
• BFS:

– Called for each vertex at most once – O(V)
– Adjmat row for each vertex is visited at most

once – O(V)

• O(V2): quadratic with number of vertices

Dijkstra’s Algorithm
Given a weighted graph G = (V, E), explore
the edges of G to discover a shortest path
from source s to goal g

Data Structures & Algorithms

Graph Algorithms

Graph Search Algorithms Summary
• Background and Definitions
• Implementation

– As adjacency matrix
– As adjacency list

• Depth-First Search
– Implement with stack

• Breadth-First Search
– Implement with queue
– Optimal in unweighted graph

• Dijkstra’s Algorithm
– Optimal for weighted graphs (in an upcoming lecture)

Related Posts