Lecture 13: Intro to Graphs

CSE 373: Data Structures and Algorithms

CSE 373 21 SP – CHAMPION

1

Administrivia

• P3 Heaps due August 3rd
• ex2 grades released yesterday
• reminder on regrades:
• you have 1 week to submit regrade requests on gradescope
• LOCKED regrade request submissions after
• TAs will look after the 1-week deadline to answer regrade requests
• Exercise 3 due today
• ex 4 out today
• extra credit survey 2 due tuesday 11:59PM

​

• if you still need more time for P2 Maps PLEASE REACH OUT TO US!!!
• don’t suffer in silence
• email cse373-instructors@cs.washington.edu

The Trie: A Specialized Data Structure - Runtime

3

CSE332, Spring 2021

L02: Dictionary ADT, Tries

• Tries view its keys as:
• a sequence of characters
• some (hopefully many!) sequences share common prefixes

a

m

d

p

e

w

l

s

Trie

s

a

​

• sap
• sad
• awls
• a
• same
• sam

Set ADT

Introduction to Graphs

• no check in question today

CSE 373 SP 18 - KASEY CHAMPION

4

Inter-data Relationships

• Arrays
• Categorically associated
• Sometimes ordered
• Typically independent
• Elements only store pure data, no connection info

CSE 373 SP 18 - KASEY CHAMPION

5

• Trees
• Directional Relationships
• Ordered for easy access
• Limited connections
• Elements store data and connection info

• Graphs
• Multiple relationship connections
• Relationships dictate structure
• Connection freedom!
• Both elements and connections can store data

A

B

C

Inter-data Relationships

• Elements only store pure data, no connection info
• Only relationship between data is order

Arrays

• Elements store data and connection info
• Directional relationships between nodes; limited connections

Trees

• Elements AND connections can store data
• Relationships dictate structure; huge freedom with connections

Graphs

Graphs

• Everything is graphs.
• Most things we’ve studied this quarter can be represented by graphs.
• BSTs are graphs
• Linked lists? Graphs.
• Heaps? Also can be represented as graphs.
• Those trees we drew in the tree method? Graphs.
• But it’s not just data structures that we’ve discussed…
• Google Maps database? Graph.
• Facebook? They have a “graph search” team. Because it’s a graph
• Gitlab’s history of a repository? Graph.
• Those pictures of prerequisites in your program? Graphs.
• Family tree? That’s a graph

​

​

​

Applications

• Physical Maps
• Airline maps
• Vertices are airports, edges are flight paths
• Traffic
• Vertices are addresses, edges are streets

​

CSE 373 SP 18 - KASEY CHAMPION

8

• Relationships
• Social media graphs
• Vertices are accounts, edges are follower relationships
• Code bases
• Vertices are classes, edges are usage

​

• Influence
• Biology
• Vertices are cancer cell destinations, edges are migration paths

​

• Related topics
• Web Page Ranking
• Vertices are web pages, edges are hyperlinks
• Wikipedia
• Vertices are articles, edges are links

​

​

SO MANY MORREEEE

www.allthingsgraphed.com

Graph: Formal Definition

• A graph is defined by a pair of sets G = (V, E) where…

CSE 373 SP 18 - KASEY CHAMPION

9

V = { A, B, C, D, E, F, G, H }

E = { (A, B), (A, C), (A, D), (A, H),

(C, B), (B, D), (D, E), (D, F),

(F, G), (G, H)}

• V is a set of vertices
• A vertex or “node” is a data entity

• E is a set of edges
• An edge is a connection between two vertices

Graph Vocabulary

• Graph Direction
• Undirected graph – edges have no direction and are two-way

CSE 373 SP 20 - KASEY CHAMPION

10

V = { Karen, Jim, Pam }

E = { (Jim, Pam), (Jim, Karen) } inferred (Karen, Jim) and (Pam, Jim)

V = { Gunther, Rachel, Ross }

E = { (Gunther, Rachel), (Rachel, Ross), (Ross, Rachel) }

Undirected Graph:

Directed Graph:

• Degree of a Vertex
• Degree – the number of edges connected to that vertex

Karen : 1, Jim : 2, Pam : 1

• In-degree – the number of directed edges that point to a vertex

Gunther : 0, Rachel : 2, Ross : 1

• Out-degree – the number of directed edges that start at a vertex

Gunther : 1, Rachel : 1, Ross : 1

• Directed graphs – edges have direction and are thus one-way

More More Graph Terminology

• Two vertices are connected if there is a path between them
• If all the vertices are connected, we say the graph is connected
• The number of edges leaving a vertex is its degree�
• A path is a sequence of vertices connected by edges
• A simple path is a path without repeated vertices
• A cycle is a path whose first and last vertices are the same
• A graph with a cycle is cyclic

​

a

b

c

f

e

g

d

j

p

m

n

i

o

p

m

n

i

o

Directed vs Undirected; Acyclic vs Cyclic

a

b

d

c

a

b

d

c

e

a

b

d

c

a

b

d

c

Acyclic:

Cyclic:

Directed:

Undirected:

Labeled and Weighted Graphs

Vertex & Edge Labels

Edge Labels

Vertex Labels

Numeric Edge Labels�(Edge Weights)

Some examples

• For each of the following think about what you should choose for vertices and edges.
• The internet
• Vertices: webpages. Edges from a to b if a has a hyperlink to b.
• Directed, since hyperlinks go in one direction
• Family tree
• Vertices: people. Edges: relationships
• Undirected, bidirectional relationships
• Input data for the “6 Degrees of Kevin Bacon” game
• Vertices: actors. Edges: movies
• Undirected, a both actor would need to be in the movie for the edge to be added
• Course Prerequisites
• Vertices: courses. Edge: from a to b if a is a prereq for b.
• Directed, since one course comes before the other
• Ways to walk between UW buildings
• Vertices: buildings. Edges: A street name or walkway that connects 2 buildings
• Undirected, since each route can be walked both ways

CSE 373 SU 19 – ROBBIE WEBBER

Multi-Variable Analysis

• So far, we thought of everything as being in terms of some single argument “n” (sometimes its own parameter, other times a size)
• But there’s no reason we can’t do reasoning in terms of multiple inputs!
• Why multi-variable?
• Remember, algorithmic analysis is just a tool to help us understand code. Sometimes, it helps our understanding more to build a Oh/Omega/Theta bound for multiple factors, rather than handling those factors in case analysis.

​

• With graphs, we usually do our reasoning in terms of:
• n (or |V|): total number of vertices (sometimes just call it V)
• m (or |E|): total number of edges (sometimes just call it E)
• deg(u): degree of node u (how many outgoing edges it has)

Adjacency Matrix

CSE 373 SU 19 – ROBBIE WEBBER

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(1)

𝚯(1)

𝚯(n)

𝚯(n)

𝚯(n * n)

Adjacency List

CSE 373 SP 20 - KASEY CHAMPION

17

Linked Lists

D

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(deg(u) )

𝚯(deg (u) )

𝚯(deg(u) )

𝚯(n + m)

𝚯(n + m)

Adjacency List

CSE 373 SP 20 - KASEY CHAMPION

18

Hash Tables

In an adjacency matrix a[u][v] is 1 if there is an edge (u,v), and 0 otherwise.

Worst-case Time Complexity �(|V| = n, |E| = m):

Add Edge:

Remove Edge:

Check edge exists from (u,v):

Get outneighbors of u:

Get inneighbors of u:

​

Space Complexity:

𝚯(1)

𝚯(1)

𝚯(1)

𝚯(deg(u) )

𝚯(n)

𝚯(n + m)

Tradeoffs

373: Graph Implementations

Questions / clarifications on anything?

relevant ideas for today

• vertices, edges, definitions
• graphs model relationships between real data (you can choose your vertices and edges to
• different graph implementations exist

​