Graphs: BFS and DFS

A set of vertices and edges can be

  1. Directed/Undirected - Edges can wither go one way or both ways

  2. Weighted/Unweighted - Strength

  3. Cyclic/Acyclic - Can I have triadic enclosure or nah


First discover, then visit


BFS

Used to find the shortest path from a vertex s to a vertex v in an un weighted graph, find the length of such a path, find out if a graph contains cycles, 

  • Start several paths at a time, and advance in each one step at a time

  • Uses FIFO queue


White vertex have not been explored

Grey has been explored but not fully

Black have been fully explored



DFS

Used for finding bridges of a graph, cycle detection, finding connecting components, topological sorting.

  • Once a possible path is found, continue the search until the end of the path

  • Uses LIFO Stack


  1. Pick a source vertex S to start

  2. Discover the vertices that are adjacent to S

BFS - Pick each child of S in turn and discover their vertices adjacent to that child

DFS - visit all neighbors down the entire path


Analysis of DFS for a graph G = (V,E) and n =abs(V) and m =abs(E)

  • When adjacency list is used, complexity is O(m+n)

  • When adjacency matrix is used scanning each row for checking the connectivity of a vertex is in order O(n)

  • Total complexity if O(n²)

  • DFS uses space O(abs(V))

  1. Push root node in stack

  2. Loop until stack is empty

  3. Peek the node of the stack

  4. something else 



A connected graph has a path from every vertex to another

A disconnected graph is a graph that does not have a link to every other node


Searching

Given a graph, ultimately build a a tree on the graph

  • Pick a vertex as the root

  • Choose certain edges to produce a tree

  • Might also build a forest if graph is not connected


Topological sort

  • linear ordering off all vertices in graph G such that vertex u comes before vertex v if edge (u,v) exists in G

  • Critical path is the order of things that should be done first (sequential dependencies)

  • can sort into a list that takes the subgroups of these possibly disconnected graphs and sorting them


Strongly connected components have multiple ways to get to them. 

A group of strongly connected nodes is a cliche


A component graph is basically a subgraph of strongly connected components.


An acyclic graph does not have any cycles.