程序代写代做代考 concurrency Java algorithm C graph game compiler COMP 250

COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 13-3 : Graphs
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s

WHAT ARE WE GOING TO DO IN THIS VIDEO?
 Graphs
 Definitions

EXAMPLE
a
cf
eg
d
b
h

SAME EXAMPLE – DIFFERENT NOTATION
a
cf
d
eg
b
h

WEIGHTED GRAPH
a 7c
d
9 5
eg
4
h
12
f
11 7
2
5 4
b

DEFINITION
A directed graph is a set of vertices 𝑉={𝑣𝑖 ∶ 𝑖∈ {1,…,𝑛}}
and set of ordered pairs of these vertices called edges. 𝐸={𝑣,𝑣 ∶𝑖,𝑗∈{1,…,𝑛}}
In an undirected graph, the edges are unordered pairs.
𝐸= 𝑣,𝑣 ∶𝑖,𝑗∈{1,…,𝑛} 𝑖𝑗
𝑖𝑗

EXAMPLES
Vertices Edges
airports web pages Java objects

EXAMPLES
Vertices Edges
airports flights web pages
Java objects

EXAMPLES
Vertices
airports web pages Java objects
Edges
flights
links (URLs)

EXAMPLES
Vertices
airports web pages Java objects
Edges
flights
links (URLs) references

linked lists
trees
graphs

TERMINOLOGY: “IN DEGREE”
e cf
a
v in degree
a1 b2 c2 d0 e1 f3 g0 h1
d
g
b h

TERMINOLOGY: “OUT DEGREE”
e
a
cf
v out degree
a1 b1 c1 d2 e2 f2 g1 h0
d
g
b h

EXAMPLE: WEBPAGES
e cf
In degree: How many web pages link to some web page (e.g. f ) ?
Out degree: How many web pages does some web page (e.g. f ) link to ?
a
d
g
h
b

TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
a
d
g
b h

TERMINOLOGY: PATH
e cf
A path is a sequence of edges such that the end vertex of one edge is the start vertex of the next edge and no vertex is repeated except maybe first and last.
Examples • acfeb
a
d
g
b
h

GRAPH ALGORITHMS IN COMP 251 (DIJKSTRA’S ALGORITHM)
Given a graph, what is the shortest (weighted) path between two vertices?

TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b h

TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
h

TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
• efe
h

TERMINOLOGY: CYCLE
a
d
g
e
A cycle is a path such that the last vertex is the same as the first vertex.
c
f
b
Examples • febf
• efe
• fbf •…
h

“TRAVELLINGSALESMAN” COMP360 -(HAMILTONIANCIRCUIT)
a 11 c 12
Find the shortest cycle that visits all vertices once.
How many potential cycles are there in a graph of n vertices ?
7 7
2
d4g

DIRECTED ACYCLIC GRAPH no cycles
b a
c
Used to capture dependencies.
d
There are three paths from a to d.

MATH
(prereqs for many upper level COMP courses)
240 Disc. Str. 1
222 Cal III
323 Prob.
SYSTEMS (compilers, networks,
distributedsys, concurrency, web,..)
APPLICATIONS (graphics, vision, bioinf,games, machine learning..)
THEORY
(crypto, optimization, game theory, logic, correctness,computability..)
202 Intro Program
206 Software Sys
250 Intro CompSci
223 Linear Alg.
273 Comp. Sys.
303 Software Design
302 Program Lang
251 Data Str & Alg
350 Num. Meth
310 Oper. Sys.
421 Data- bases
424 Artif. Intel.
360 Alg. Design
330 Theory Comp.

GRAPH ADT
addVertex( ), addEdge( ) containsVertex( ), containsEdge( ) getVertex( ), getEdge( ) removeVertex( ), removeEdge( ) numVertices( ), numEdges( )
…
How to implement a Graph class?
A graph is a generalization of a tree, so …

RECALL: HOWTOIMPLEMENTAROOTEDTREEINJAVA?
// alternatively….
class Tree{
TreeNode root;
:
class TreeNode{
T element;
ArrayList> children;
TreeNode parent; // optional
} }
class Tree{
TreeNode root;
:
class TreeNode{
T element;
TreeNode firstChild;
TreeNode nextSibling; }
}

ADJACENCY LIST
(GENERALIZATION OF CHILDREN FOR GRAPHS)
a
cf
e
v v.adjList
ac bf cf
d a, c
e b, f
f b, e
gh
h
Here each adjacency list is sorted, but that is not always possible (or necessary).
d
g
b
h

HOW TO IMPLEMENT A GRAPH CLASS IN JAVA?
A very basic Graph class:
class Graph {
class Vertex {// We could have called it GNode
ArrayList adjList;
T element; }
}

HOW TO IMPLEMENT A GRAPH CLASS IN JAVA?
class Graph { class Vertex {
ArrayList adjList;
T element;
boolean visited;
}
class Edge {
Vertex endVertex;
double weight;
: }
}
Note that, unlike a rooted tree, there is no notion of a root vertex in a graph.

HOW TO REFERENCE VERTICES?
class Graph {
ArrayList< Vertex > vertexList;
:
class Vertex { … } class Edge { … }
}

HOW MANY OBJECTS ?
e f
b

HOW MANY OBJECTS ?
Graph
ArrayList
e f
b
Vertex
Vertex
Vertex
Edge
Edge
Edge
Edge
Edge
ArrayList
ArrayList
ArrayList

ADJACENCY MATRIX
a d
e cf
001000 000001 000001 101000 010001 010010
abcdef
a b c d e f
boolean[][] adjMatrix = new boolean[6][6]
b
Assume we have a mapping from vertex names to 0, 1, …. , n-1.

ADJACENCY MATRIX
loop
a d
abcdef
a b c d e f
boolean[][] adjMatrix = new Boolean[6][6]
e cf
101000 000001 000001 101000 010011 010010
b
Assume we have a mapping from vertex names to 0, 1, …. , n-1.

“DEFINITIONS”
Consider a graph with 𝑛 vertices.
We say that the graph is dense if the number of edges is close to 𝑛2. We say that the graph is sparse if the number of edges is close to 𝑛.
(These are not formal definitions.)

EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
 The graph has 10,000 vertices and 20,000,000 edges, and it is important to use as little space as possible.
 You need to answer the query areAdjacent() as quickly as possible, no matter how much space you use.
 You need to perform operation insertVertex.
 You need to perform operation removeVertex.

EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
 The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to use as little space as possible.
 You need to answer the query areAdjacent() as quickly as possible, no matter how much space you use.
 You need to perform operation insertVertex.
 You need to perform operation removeVertex.

EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
 The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
 Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
 You need to perform operation insertVertex.
 You need to perform operation removeVertex.

EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
 The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
 Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
 Perform operation insertVertex( v ).
 You need to perform operation removeVertex.

EXERCISE
Would you use an adjacency list or adjacency matrix for each of the following? The graph is sparse e.g. 10,000 vertices and 20,000 edges and we want to use
as little space as possible.
 The graph is dense e.g. 10,000 vertices and 20,000,000 edges, and we want to
use as little space as possible. .
 Answer the query areAdjacent() as quickly as possible, no matter how much
space you use.
 Perform operation insertVertex( v ).
 Perform operation removeVertex( v ).

COMING UP!
Recursive graph traversal depth first
Non-recursive graph traversal depth first
breadth first

In the next videos: More on graphs

Related Posts