程序代写代做代考 C algorithm Bayesian Bayesian network graph Graphs

Graphs
Based on slides by David Kauchak
COSC 336 1

Graphs
What is a graph?
A
B
F
G
D
E
C
COSC 336
2

Graphs
A graph is a set of vertices V and a set of edges (u,v)  E where u,v  V
A
B
F
G
D
E
C
COSC 336
3

Graphs
How do graphs differ? What are graph characteristics we might care about?
A
B
F
G
D
E
C
COSC 336
4

Different types of graphs
Undirected – edges do not have a direction
A
B
F
G
D
E
C
COSC 336
5

Different types of graphs
Directed – edges do have a direction
A
B
F
G
D
E
C
COSC 336
6

Different types of graphs
Weighted – edges have an associated weight
A 8
B
2
C
7
D1
F 7
E
20 2
COSC 336
7
G

Different types of graphs
Weighted – edges have an associated weight
A 8
B
2
C
7
D1
F 7
E
20 2
COSC 336
8
G

Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1)  E
A
B
F
D
E
CG
COSC 336 9

Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1)  E
{A, B, D, E, F}
B
A
D
F E
CG
COSC 336 10

Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1)  E
{C, D}
B
A
D
F E
CG
COSC 336 11

Terminology
Path – A path is a list of vertices p1,p2,…pk where there exists an edge (pi,pi+1)  E
A simple path contains no repeated vertices (often this is implied)
F
D
E
CG
COSC 336 12
A
B

Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
B
F
D
E
CG
COSC 336 13

Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
{A, B, D} B
A
D
CG
COSC 336 14
F
E

Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
not a cycle
B
F
D
E
CG
COSC 336 15

Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
B
F
D
E
CG
COSC 336 16

Terminology
Cycle – A subset of the edges that form a path such that the first and last node are the same
A
not a cycle
B
F
D
E
CG
COSC 336 17

Terminology
Cycle – A path p1,p2,…pk where p1 = pk
cycle
A
B
F
D
E
CG
COSC 336 18

Terminology
Connected – every pair of vertices is connected by a path
connected
B
A
F
D
E
CG
COSC 336 19

Terminology
Connected – every pair of vertices is connected by a path
connected
B
A
F
D
E
CG
COSC 336 20

Terminology
Connected (undirected graphs) – every pair of vertices is connected by a path
not connected
B
A
F
D
E
CG
COSC 336 21

Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
not strongly connected
B
A
F
D
E
CG
COSC 336 22

Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
not strongly connected
B
A
D
F E
G 23
COSC 336

Terminology
Strongly connected (directed graphs) – Every two vertices are reachable by a path
strongly connected
B
A
D
F E
G 24
COSC 336

Different types of graphs
What is a tree (in our terminology)?
F
B
A
D
C
H E
G
COSC 336
25

Different types of graphs
Tree – connected, undirected graph without any cycles
F
B
A
D
C
H E
G
COSC 336
26

Different types of graphs
Tree – connected, undirected graph without any cycles
F
C
B
A
D
H E
G
need to specify root
COSC 336
27

Different types of graphs
Tree – connected, undirected graph without any cycles
F
A
B
H E
G
D
C
COSC 336
28

Different types of graphs
DAG – directed, acyclic graph
F
B
A
D
C
H E
G
COSC 336
29

Different types of graphs
Complete graph – an edge exists between every node
B
A
F
D
C
COSC 336
30

Different types of graphs
Bipartite graph – a graph where every vertex can be partitioned into two sets X and Y such that all edges connect a vertex u  X and a vertex v  Y
A B C
D
E
F G
COSC 336
31

When do we see graphs in real life problems?
• Transportation networks (flights, roads, etc.) • Communication networks
• Web
• Social networks
• Circuit design
• Bayesian networks
COSC 336 32

Standard notation for graphs
• Agraphisgivenbytwosets:thesetVofnodes(orvertices)andthesetEofedges. • Notation: G = (V,E)
• Notation for the number of nodes: |V| or n
• Notation for the number of edges: |V| or m
COSC 336 33

Node degree
In an undirected graph:
For a node v, deg(v) = no. of v’s neighbors
∑ 􏲨∈􏲩 deg 𝑣 = 2 𝐸
(because in the sum we count each edge twice) In a directed graph:
in-deg(v) = no of edges incoming in v out-deg(v) = no of edges outgoing from v
∑ 􏲨∈􏲩 in-deg(v) = ∑ 􏲨∈􏲩 out-deg(v) = |E|
COSC 336 34

Representing graphs
Adjacency list – Each vertex u  V contains an adjacency list of the set of vertices v such that there exists an edge (u,v)  E
A
A: B D B: A D
C: D
D: A B C E
D35
B
D
E C
COSC 3
36
E:

Representing graphs
Adjacency list – Each vertex u  V contains an adjacency list of the set of vertices v such that there exists an edge (u,v)  E
A
A: B B:
C: D
D: A B
COSC 3 D 36
B
D
E C
36
E:

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
1 if(i,j)E
otherwise
A
B
D
C
aij  0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
COSC 336
37

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij  0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
38

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij  0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
39

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij  0 E
ABCDE
A01010 B10010 C00010 D11101 E00010
1 if(i,j)E
otherwise
COSC 336
40

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
1 if(i,j)E aij  0 otherwise
A
B
D
Is it always symmetric?
ABCDE A01010
B10010 C00010 D11101 E00010
E C
COSC 336
41

Representing graphs
Adjacency matrix – A |V|x|V| matrix A such that:
A
B
D
C
aij  0 E
ABCDE
A01000 B00000 C00010 D11000 E00010
1 if(i,j)E
otherwise
COSC 336
42

Adjacency list vs. adjacency matrix
Adjacency list
Sparse graphs (e.g. web) Space efficient
Must traverse the adjacency list to discover is an edge exists
Adjacency matrix
Dense graphs
Constant time lookup to discover if an edge exists
Simple to implement
For non-weighted graphs, only requires boolean matrix
Can we get the best of both worlds?
COSC 336 43

Sparse adjacency matrix
Rather than using an adjacency list, use an adjacency hashtable
A
B
D
C
E
A: hashtable [B,D]
B: hashtable [A,D]
C: hashtable [D]
D: hashtable [A,B,C,E]
hashtable [D] 44
COSC 3
36
E:

Sparse adjacency matrix
Constant time lookup
Space efficient
Not good for dense graphs, why?
A
B
D
C
E
A: hashtable [B,D]
B: hashtable [A,D]
C: hashtable [D]
D: hashtable [A,B,C,E]
hashtable [D] 45
COSC 3
36
E:

Weighted graphs
Adjacency list
• store the weight as an additional field in the list
A:
B:8
D:3
8 B
A
3
13 2
D 10
E
C
COSC 336 46

Weighted graphs
Adjacency matrix
aij weight if(i,j)E
8 B
A
3

otherwise
ABCDE A∞8∞3∞
B8∞∞2∞ C ∞ ∞ 010 ∞ D 3 2 10 ∞ 13 E∞∞ ∞13∞
13 2
D 10
E
C
COSC 336
47

Graph algorithms which we’ll cover
• Topological sorting of a DAG
• Graph traversal (BFS, DFS)
• Shortest path from a to b • unweighted
• weighted positive weights • negative/positive weights
• Minimum spanning trees • Flows in networks
COSC 336 48

Topological Sort
Givenagraph,G = (V, E),outputallthe vertices in V such that no vertex is output before any other vertex with an edge to it.
call taxi
pack bags
reserve flight
check in airport
taxi to airport
take flight
locate gate
COSC 336
49

Topological Sort
call pack taxi to reserve check in
locate take gate flight
taxi bags airport flight
airport
COSC 336
50

Topo-Sort Take One
Label each vertex’s in-degree (# of inbound edges) While there are vertices remaining
Pick a vertex with in-degree of zero and output it Reduce the in-degree of all vertices adjacent to it Remove it from the list of vertices
runtime: O(|V|2)
COSC 336 51

Topo-Sort Take Two
Label each vertex’s in-degree
Initialize a queue to contain all in-degree zero vertices
While there are vertices remaining in the queue
Remove a vertex v with in-degree of zero and output it Reduce the in-degree of all vertices adjacent to v
Put any of these with new in-degree zero on the queue
runtime: O(|V| + |E|)
Can we use a stack instead of a queue ?
COSC 336 52

Topo-Sort
• Topo-Sort takes linear time: O(|V|+|E|)
COSC 336 53

Recall: Tree Traversals
a
bcd fg
e hij
kl
abfgkcdhilje
COSC 336 54

Depth-First Search
• Pre/Post/In – order traversals are examples of depth-first search
• Nodes are visited deeply on the left-most branches before any nodes are visited on the right-most branches
• Visitingtherightbranchesdeeplybeforetheleftwouldstillbe depth-first! Crucial idea is “go deep first!”
• In DFS the nodes “being worked on” are kept on a stack
COSC 336 55

DFS(not quite right)
void DFS(Node startNode) { Stack s = new Stack;
s.push(startNode);
while (!s.empty()) { x = s.pop();
/* process x */
for y in x.children() do
s.push(y); }
COSC 336 56

DFS on Trees
a
a
b
f
g
bcd fg
e hij
k
kl
COSC 336 57

DFS on Graphs
a
a
b
f
g
bcd fg
e hij
a
Problem with cycles: may run into an infinite loop
kl
COSC 336 58

DFS- for connected graphs
Running time:
O(|V| + |E|)
Key observation: each node enters the stack at most its indegree times
59
for v in Nodes do v.visited = false;
DFS(startNode);
void DFS(Node v) { Stack s = new Stack; s.push(v);
while (!s.empty()) {
x = s.pop();
if (!x.visited) {
x.visited = true;
process( x ) }
for y in x.children() do
if (!y.visited) s.push(y);
}
COSC 336

DFS- for general graphs
for v in V do
v.visited = false;
for v in V do
if (!v.visited) DFS(v);
COSC 336
60
Running time:

Breadth-First Search
• Traversing tree level by level from top to bottom
(alphabetic order)
a
bcd fg
e hij
kl
COSC 336
61

Breadth-First Search
BFS characteristics
• Nodes being worked on maintained in a FIFO Queue, not a stack
• Iterative style procedures often easier to design than recursive procedures
COSC 336 62

Breadth-First Search- for connected graphs
for v in Nodes do v.visited = false;
DFS(startNode);
void DFS(Node v) { Stack s = new Stack; s.push(v);
while (!s.empty()) {
x = s.pop(); if (!x.visited)
x.visited = true; process (x)
for y in x.children() do if (!y.visited) s.push(y);
}
for v in Nodes do v.visited = false;
BFS(startNode);
void BFS(Node v) { Queue s = new Queue; s.enqueue(startNode); while (!s.empty()) {
x = s.dequeue(); if (!x.visited)
x.visited = true; process (x)
for y in x.children() do
if (!y.visited) s.enqueue(y); }
COSC 336 63

QUEUE
a
bcde cdefg defg efghij fghij ghij hijk ijk
jkl
kl
l
a
bcd fg
e hij
kl
COSC 336
64

Graph Traversals
DFS and BFS
• Either can be used to determine connectivity: • Is there a path between two given vertices?
• Is the graph (weakly) connected?
• Important difference: Breadth-first search always finds a shortest path from the start vertex to any other (for unweighted graphs)
• Depth first search may not!
COSC 336 65

Breadth First Search (BFS) on Trees
COSC 336 66

Tree BFS
A BDE
CFG
Q:
COSC 336
67

Tree BFS
A BDE
CFG
Q:A
COSC 336
68

Tree BFS
A
BDE CFG
Q:
COSC 336
69

Tree BFS
A
BDE CFG
Q: B, D, E
COSC 336
70

Tree BFS
A
BDE CFG
Q: D, E
COSC 336
71

Tree BFS
A
BDE CFG
Q: D, E, C, F
COSC 336
72

Tree BFS
A BDE
CFG
Q: E, C, F
COSC 336
73

Tree BFS
Q: E, C, F
A BDE
CFG
Frontier: the set of vertices that have been visited so far
COSC 336 74

Tree BFS
A BDE
CFG
COSC 336
75

Tree BFS
A BDE
CFG
COSC 336
76

Tree BFS
A BDE
CFG
COSC 336
77

Tree BFS
A BDE
CFG
COSC 336
78

Tree BFS
What order does the algorithm traverse the nodes?
BFS traversal visits the nodes in increasing distance from the root
COSC 336 79

Tree BFS
Does it visit all of the nodes?
COSC 336 80

Running time of Tree BFS
Adjacency list
• How many times does it visit each vertex? • How many times is each edge traversed? • O(|V|+|E|)
Adjacency matrix
• For each vertex visited, how much work is done? • O(|V|2)
COSC 336 81