what is graph in data structure with example and graphs in data structures and algorithms pdf fee download
Data structures for graphs
There are two reasonable data structures to store graphs:
• adjacency matrix
• adjacency list
An adjacency matrix: letV = v ,v ,...,v .
1 2 n
• We store information about the edges of the graph in an
n⇥ n arrayA where
1 if(v,v )2 E
What do we know about the matrix for undirected graphs?
the matrix will be symmetric (Ai,j andAj,i will always hold the same value).
• If the graph is weighted, Ai,j stores the weight of the
edge (v,v ) if that edge exists, and either 0 or 1 if the
edge doesn’t exist–depends on the application.
• Complexity of the adjacency matrix data structure?
– Storage requires ⇥( n ) space
– Edge Queries are ⇥(1) .
51An adjacency list: Use a1-dimensional arrayA of sizen.
• At entryAi, we store a linked-list of neighbours ofv
• If the graph is directed, we store only the out-neighbours.
• Each edge (v,v ) of the graph is represented by exactly
one linked-list node in the directed case, and
• by exactly two linked-list nodes in the undirected case
– Storage required is ⇥( n+m)
– Edgequeriescanbemadein⇥(log( maximum degree))).
How? the lists are stored as balanced trees.
We now look at two common ways to traverse a graph.
52Breadth-First Search (BFS)
To start, all vertices are unmarked.
• Start atv. Visitv and mark as visited.
• Visit every unmarked neighbour u of v and mark each u
• Markv ﬁnished.
• Recurse on each vertex marked as visited in the order they
BFS of an undirected Graph
• the shortest path fromv to any other vertexu and this distanced(v).
• Whether the graph is connected. Number of connected components.
Q: What does the BFS construct?
a BFS tree that visits every node connected tov, we call this a spanning-tree.
jacencylistrepresentationofagraph? a FIFO (ﬁrst in, ﬁrst out) queue.
which has the operations:
Q: What information will we need to store along the way?
• the current node
• the predecessor
• the distance so far from v
54The BFS Algorithm
We will use pv to represent the predecessor of v, dv to
represent the number of edges from v (i.e., the distance from v)
andov to represent the order ofv in the search.
Start BFS on G at vertex v
for u in V: Initialize arrays
coloru = black
ou = -1 not in the BFS yet
du = infinity we use infinity to denote
pu = NIL "not connected"
new queue Q
colorv = green
ov = i; dv = 0; pv = NIL
while not ISEMPTY(Q):
u = DEQUEUE(Q)
for each edge (u,w) in E:
if (colorw == black):
colorw = green
i += 1
ow = i
dw = du + 1
pw = u
coloru := red;
55Complexity of BFS(G,v)
Q: How many times is each nodeENQUEUEed?
at most once, when it is black, at which point it is coloured green.
Therefore, the adjacency list of each node is examined at most
once, so that the total running time ofBFS is O(n+m)
or linear in the size of the adjacency list.
• BFS will visit only those vertices that are reachable fromv.
connected (in the directed case), then this will be all the
vertex in order to see the whole graph.
Q: Prove that du really does represent the length of the short-
est path (in terms of number of edges) fromv tou.
All vertices and edges start out unmarked.
• Walk as far as possible away from v visiting vertices
• If the current vertex has not been visited,
• Otherwise, if the vertex has been visited,
• When the current vertex has only visited neighbours left
mark as ﬁnished (white).
• Backtrack to the ﬁrst vertex that is not ﬁnished.
Just like BFS, DFS constructs a spanning-tree and gives con-
nected component information.
Q: Does it ﬁnd the shortest path between v and all other ver-
58Implementing a DFS
Q: Which ADT would be the most helpful for implementing DFS
given an adjacency list representation ofG?
A stackS to store edges
with the operations
• PUSH(S, (u,v))
to easily determine whether an edge is a back-edge or a DFS-
• dv will indicate the discovery time
• fv will indicate the ﬁnish time.
for v in V:
colorv = black
dv = infinity
fv =i nfinity
pv = NIL
new stack S
colors = green; ds = 0; ps = NIL
time = 0
for edge (s,v) in E:
while not ISEMPTY(S):
(u,v) = POP(S);
if (v == NIL): // Done with u
time += 1
fu = time
coloru = white
else if (colorv == black):
colorv = green
time += 1
dv = time
pv = u
PUSH(S,(v,NIL)) // Marks the end of v’s neighbors
for edge (v,w) in E:
60Complexity of DFS(G,s)
Q: How many times does DFS visit the neighbours of a node?
• once...when the node is green and the neighbour is black
• Therefore, the adjacency list of each vertex is visited at
• SothetotalrunningtimeisjustlikeforBFS,⇥( n+m)i.e.,
linear in the size of the adjacency list.
Note that the gold edges, or the DFS edges form a tree called
Q: Is the DFS tree unique for a given graphG starting ats?
types of edges inE.
61We can specify edges on DFS-tree according to how they are
traversed during the search.
• Tree-Edges are the edges in the DFS tree.
• Back-Edges are edges from a vertexu to an ancestor ofu
in the DFS tree.
• Forward-Edges are edges from a vertex u to a descen-
dent ofu in the DFS tree.
• Cross-Edges are all the other edges that are not part of
the DFS tree (from a vertex u to another vertex v that is
Only apply to directed graphs.
(Note: A cycle is a path from a vertexu to itself.)
It is not hard to see that there is a cycle inG if and only if there are any back-edges when DFS is run.
Q: How can we detect back-edges during a DFS?
Add a test after the line marked by () in DFS. If the color ofv is green instead of black, then we know that we have seenv before on the current path from the sources. This means that the edge(u,v) is a back edge and therefore forms a cycle.
We can rewrite the DFS algorithm recursively which “hides” the
stack notion in the recursion.
dfs(vertex v, int time)
v.start = time
for each neighbor w of v
if w is unvisited
add edge vw to tree T
v.finish = time
the nodes which allows us to easily preform a topological sort.