Graph Algorithms
Representation of Graphs • Adjacency Matrix
• Prefer when the graph is dense—|E| is
• Adjacency List
close to |V|2.
• a compact way to represent sparse
• The adjacency matrix of a graph requires
graphs—those for which |E| is much
(V2) memory, independent of the number
less than |V|2 of edges in the graph.
• The amount of memory required is
Adjacency List Representation Undirected Graph
Adjacency Matrix Representation
Directed Graph
Adjacency List Representation
Adjacency Matrix Representation
Breadth First Search
• Given a graph G=(V,E) and a distinguished source vertex s, breadth-first search
systematically explores the edges of G to “discover” every vertex that is reachable from s.
• the algorithm discovers all vertices at distance k from s before discovering any vertices at
distance k + 1
• It computes the distance (smallest number of edges) from s to each reachable vertex.
• It also produces a “breadth-first tree” with root s that contains all reachable vertices. For
any vertex reachable from s, the simple path in the breadth-first tree from s to
corresponds to a “shortest path” from s to in G, that is, a path containing the smallest
number of edges.
• The algorithm works on both directed and undirected graphs.
Assumptions:
• The input graph G=(V,E) is represented using
adjacency lists.
• the color of each vertex u V is stored in the
attribute u.color and the predecessor of u in
the attribute u..
• If u has no predecessor then u.= NIL.
• The attribute u.d holds the distance from the
source s to vertex u computed by the
algorithm.
• The algorithm also uses a first-in, first-out
queue Q to manage the set of gray vertices.
Analysis
• After initialization, breadth-first search never whitens a vertex, and thus the test in line 13 ensures that each vertex is
enqueued at most once, and hence dequeued at most once.
• The operations of enqueuing and dequeuing take O(1) time, and so the total time devoted to queue operations is O(V).
• Because the procedure scans the adjacency list of each vertex only when the vertex is dequeued, it scans each adjacency
list at most once.
• Since the sum of the lengths of all the adjacency lists is ‚(E), the total time spent in scanning adjacency lists is O(E).
• The overhead for initialization is O(V), and thus the total running time of the BFS procedure is O(V+E).
• Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G.
• Time complexity : O(bd)
• Space Complexity: O(bd)
Depth First Search
• To search “deeper” in the graph whenever possible.
• Depth-first search explores edges out of the most recently discovered vertex that still has
unexplored edges leaving it.
• Once all of ’s edges have been explored, the search “backtracks” to explore edges leaving the
vertex from which was discovered.
• This process continues until we have discovered all the vertices that are reachable from the
original source vertex.
• If any undiscovered vertices remain, then depth-first search selects one of them as a new source,
and it repeats the search from that source.
• The algorithm repeats this entire process until it has discovered every vertex
Analysis
• The loops on lines 1–3 and lines 5–7 of DFS take time (V), exclusive of the time to execute the
calls to DFS-VISIT.
• The procedure DFS-VISIT is called exactly once for each vertex vV , since the vertex u on which
DFS-VISIT is invoked must be white and the first thing DFS-VISIT does is paint vertex u gray.
• During an execution of DFS-VISIT(G,V), the loop on lines 4–7 executes |Adj[E]|times.
• Since
the total cost of executing lines 4–7 of DFS-VISIT is ‚ (E).
• The running time of DFS is therefore (V + E).
• Time complexity: O(bm), where m is the maximum depth of any nodeSpace
• Complexity: O(bm), linear space
