2024-02-22

Thursday, February 22nd, 2024

ECS122A Lecture: Intro to Graph

• graph
  • directed vs undirected
  • dense graph: $E=V\times V$ (an edge is an ordered pair of vertices) so $E=O(V^2)$
    • example: disease/infection, genome analysis
    • adjacency matrix
      • time: $O(1)$ to check edge
      • space: $O(V^2)$
  • sparse graph: $E=O(V)$
    • example: social interaction
    • adjacency list
      • time to look up edge: $O(V)$ (a vertex can be connected to all other vertices in the worst case, and we need to check one by one, unless it’s a sorted list, then it’s $O(\log V)$)
      • time to list all edges: $O(V+E)$
      • space: $O(V+E)$ (e.g. a hash map entry for each vertex, and the entire map contains $E$ edges)
• breadth-first search distance algorithm analysis
  • input: unweighted graph, start vertex s
  • output: dist, where dist[v] is the distance between s and v
  • code
    • initialize dist[:] to infinity
    • d[s] = 0
    • create a queue that initially contains start node
    • while queue is not empty
      • pop node u from queue
      • for each node v adjacent to u
        • if v has not been visited (d[v] == inf)
          • d[v] = d[u] + 1
          • push v into the queue
  • example
    • input
      • Graph G as a
        • S: A, C, G
        • A: S, B
        • B: A
        • C: S, D, E, F
        • D: C
        • E: C, H
        • F: C, G
        • G: S, F, H
        • H: E, G
  • runtime:
    • if graph is stored as adjacency list: $O(V+E)$, ($O(V)$ for max vertices in queue, $O(E)$ since each edge is processed exactly once)
    • if graph is stored as adjacency matrix: $O(V^2)$ ($O(V)$ for max vertices in queue, then $O(V)$ to get the adjacent nodes for each node)

BFS runtime comparison:

Storage	Space	Dense Graph Runtime	Sparse Graph Runtime
adjacency list	$O(V+E)$	$O(V^2)$	$O(V)$ ($E<V$)
adjacency matrix	$O(V^2)$	$O(V^2)$	$O(V^2)$

• depth-first search
  • allows detecting cycle in $O(V+E)$ time
  • create a tree out of an (directed) acyclic graph (by removing edges when necessary to prevent a node from having more than one parents)
  • code
    • color[v] = White
    • for each node u in graph
      • if color[u] == White
        • color[u] = Gray
        • start_time[u] = time
        • for each adjacent node v in graph:
          • dfs(v)
        • color[v] = Black
        • finish_time[u] = time
  • function of setting colors
    • if there’s an edge white → gray, then it’s a tree node
    • if there’s an edge gray → gray, then it’s a “backward node”, which means there’s a cycle
    • if there’s an edge gray → black, then it’s a forward edge (an edge from ancestor to dependent)