Graphs

Question 1

Graphs Definitions/Notations

Answer 1

Implication: it is a different type of input, so it is a different model of input that instead we might of head a string or something.

Graph: have elements or nodes and some are connected to each other aka edges and some aren’t

Can have properties to the graph like weights on each edge ETC

Notation:
V is set of vertices and assume that it is nonempty

V over 2 means two vertices on the set V where the two vertices not the same, or a set of edges

How to write an edge depends if it is directed or undirected

Undirected:
- no direction so no care, pair G = (V, E) (a node and edge) where the Edge is in the subset of V over 2.
ex:
Gu = ({1,2,3},{{1,2}.{2,1}})

Directed:
if edges are in the set of V X V (cart. product) then G = (V, E) is directed
EX:
Gd = ({1,2,3},{(1,2).(3,2),(3,2)})

n = size of set V (nodes)
m = size of set E (edges)

Question 2

Graph Representation

Answer 2

How we can represent a graph

Adjacency Matric :
- n by n matrix that M[i,j] is 1 when {i,j} has an edge
- O(n^2) Space
- if G is dense it is useful or lots of edges or about THETA(n^2)
- check if (i,j) in the set of edges constant time

Adjacency List:
1D array
each i the set of the array from 1 to n store the list of adjacent neighbors of the vertex i Adj(i)
- O(m) space total
-Good if G is sparse or edges are about THETA(n)
- Time to check if (i,j) in the set of edges takes time proportional of the list of the adjacent vectors. BIG O

Question 3

Breadth First Search Problem

Answer 3

Input: is an undirected graph and a vertex that is the source

Output: an Array d, such that for any node (u) in V, d[u] = length of the shortest path from s to u.

• when would you need this?

Question 4

Breadth First Search General

Answer 4

First compute all vertexes in the graph where the distance is 1 aka neighbor of the source s vertex.

BFS never computes distance of longer distance before the distance of the shorter. This is Key

Question 5

Breadth First Search PseudoCode

Answer 5

BFS(G, s)
d[s] <- 0
for u in set of V over {s} do
d[u] gets undetermine
Q.enqueue(s)
while Q.empty() is false do:
u get Q.dequeue()
for v in set Adj(u) do
if d[v] = undetermine then
d[v] gets d[u] + 1
Q.endqueue(v)