ics 46: graphs

graph definition

Set of vertices V connected by edges E

Difference between tree vs graph

• Tree CANT have cycles 

• Graphs can have cycles

What's the max amount of nodes a graph can have?

• n(n-1)/2

• n=total number of notes

• n-1=each node has this total max 

• /2=avoid counting duplicates

Whats the min amount of nodes a graph can have?

0

directed vs undirected graph

• Directed: has 1 specific direction of the edges 

• Undirected: can go both directions from edges

Adjacency matrix Space complexity

• v^2

• bc v rows x v cols 

adjacency matrix Time complexity of lookup of edge

• O(1)

• always constant time for lookups in 2d arrays

adjacency matrix time complexity for adding edge

• O(1)

• always constant time adding in 2d arrays

adjacency matrix time complexity for iterating over vertices adjacent to v

• O(V)

• need to iterate thru that corresponding vertex’s row to find the 1’s/the vertices that are adjacent to v  

adjacency list space complexity

• Array holding vertices: v

• Linked lists holding edges: e

• O(v + e)

adjacency list time complexity of lookup of edge

• Based on the number of children of the vertex ur looking up an edge for (basically degree of the vertex)

• Once ur in linked list, searching in a linked list is always O(n)

• O(degree(v))

adjacency list time complexity for adding edge

• O(1): inserting to the head of linked list (not checking for duplicate edges)

• If checking for duplicate edges, must traverse thru the linked list first, so O(degree(v))

adjacency list time complexity for iterating over vertices adjacent to v

O(degree(v))