Scribd
Upload
7 views

M4_graphsearchalgo

Uploaded by

ananaeygarg
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views

M4_graphsearchalgo

Uploaded by

ananaeygarg
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

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 vV , 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

You might also like