Graphs

Question 1

Name for the elements in a Graph

Answer 1

Node or Vertex (nodes, vertices)

Let V={v1,v2,…}, the set of vertices
|V| = n (number of vertices)

Question 2

Name for the connection btwn two elements in a Graph

Answer 2

Edges/Links

Let E={e1,e2,…} or {(v1,v2),(v4,v7),…}

|E| = m

• can be directed or undirected
• Can be weighted w/ a strength value

Question 3

What’s an Adjacency Matrix

Answer 3

For a graph with n = |V| vertices,

An n×n matrix
Each cell is the relationship of the column vertex and row vertex ñ
* holds 1 (if there’s an edge) or 0 (if not)

Question 4

What’s the performance of an Adjacency Matrix

Answer 4

For a graph with n vertices:

• Takes up O(n^2) space

Speed:

• O(1) to check if an edge exists
• O(1) to create an edge btwn two vertices

Takes a lot of space, but is very fast

Question 5

What’s the performance of an Adjacency List

Answer 5

For a graph with n vertices:

• Takes up O(m) space (m = # of edges)
• Worst-case is O(m^2) but this rarely happens

(Note: n < m < n^2)

Speed:

• O(n) to check if an edge exists
• O(n) to create an edge btwn two vertices (b/c you need to check if one already exists)

Takes less space, but is slower

Question 6

What’s an Adjacency List

Answer 6

An array of pointers (linked list inside each)
Each index is for a node
Linked list inside stores the neighbors (other nodes with edges)

Question 7

When are two nodes Adjacent

Answer 7

When they’re connected by an edge

a – b

Question 8

When are two edges adjacent

Answer 8

If they have a vertex in common

a – b – c

Question 9

What is a Path

Answer 9

A sequence of adjscent edges from one vertex to another

Question 10

What is the small world property?

Answer 10

In most networks, the shortest path between two nodes tend to be pretty short

(If there is a path btwn them, its usually short)

Question 11

What’s a Component / connected component

Answer 11

“A maximal set of vertices such that there exists a path btwn every pair of vertices in the set”

Aka: the largest set of vertices where they all connect

Question 12

How does Breadth First Search (BFS) work

Answer 12

1. Set all vertices to dist(u) = infinity
2. Set current vertex to dist(u) = 0
3. Put current vertex into a queue
4. While queue isn’t empty:
   a) take curr node out of queue
   b) for all neighbors (v) of curr node (u)
   1) if v hasNot been processed yet (dist=infinity)
   a) put v into the queue
   b) make dist(v) = dist(u) + 1

Explicitely uses a queue

WILL FIND THE SHORTEST PATH

Question 13

Breadth First Search (BFS) runtime

Answer 13

O(m + n)

m = # of vertices
n = # of nodes

Question 14

How does Depth First Search (DFS) work

Answer 14

For a node:

1. Set visited(u) = true
2. For each neighbor (v) of curr node (u)
   a) if not visited, explore that node

Implicitely uses a Stack