Graph Data Structure
Graph
• A graph is a pictorial representation of a set of objects where
some pairs of objects are connected by links.
• The interconnected objects are represented by points termed as
vertices, and the links that connect the vertices are called
edges.
• Formally, a graph is a pair of sets (V, E), where V is the set of
vertices and E is the set of edges, connecting the pairs of
vertices.
In the above graph,
V = {a, b, c, d, e} E = {ab, ac, bd, cd, de}
Graph Data Structure
• Mathematical graphs can be represented in data-structure. We
can represent a graph using an array of vertices and a two
dimensional array of edges.
• Before we proceed further, let's familiarize with some
important terms −
• Vertex − Each node of the graph is represented as a vertex.
• Edge − Edge represents a path between two vertices or a line
between two vertices.
• Adjacency − Two node or vertices are adjacent if they are
connected to each other through an edge.
• Path − Path represents a sequence of edges between two
vertices.
• Cycle: A path that starts and ends on the same vertex
• Directed Graph: A graph that entail edges with ordered pair
of vertices and has direction indicated with an arrow.
• Undirected Graph: A graph that entail edges with ordered
pair of vertices, however it does not have direction define.
• Weighted Graph: A graph in which each edge carries a value.
• Complete Graph: A graph in which every vertex is directly
connected to every other vertex.
• In a complete graph every vertex is adjacent to every other
vertex.
• If there are N vertices then there will be N(N-1) edges in case
of complete directed graph and N(N-1)/2 in case of complete
undirected graph.
• Degree
• In an undirected graph degree of a vertex V is number of edges
connected to vertex V.
• In a directed graph out-degree of a vertex V is number of edges
leaving vertex V. It’s in-degree is number of edges ending at
vertex V.
• Subgraph: If graph G=(V, E) Then Graph G'=(V',E') is
a subgraph of G if V' ⊆ V and E' ⊆ E
• Tree: undirected, connected graph with no cycles
• Spanning tree: A spanning tree of G is a connected subgraph of
G that is a tree
Graph Representations
• Following two are the most commonly used representations of
graph.
1. Adjacency Matrix
2. Adjacency List
• There are other representations also like, Incidence Matrix and
Incidence List.
Adjacency Matrix
• Adjacency Matrix is a 2D array of size V x V where V is the
number of vertices in a graph.
• Let the 2D array be adj[][],
a slot adj[i][j] = 1 indicates that there is an edge from
vertex i to vertex j.
• Adjacency matrix for undirected graph is always symmetric.
• Adjacency Matrix is also used to represent weighted graphs.
• If adj[i][j] = w, then there is an edge from vertex i to vertex j
with weight w.
The adjacency matrix for the above example graph is:
Adjacency List:
• An array of linked lists is used.
• Size of the array is equal to number of vertices.
• Let the array be array[]. An entry array[i] represents the linked
list of vertices adjacent to the ith vertex.
• This representation can also be used to represent a weighted
graph.
• The weights of edges can be stored in nodes of linked lists.
• Following is adjacency list representation of the above graph.
Graph Traversals
• There are two possible traversal methods for a graph:
1. Depth-First Traversal
2. Breadth-First Traversal
Depth First Search Traversal
• Depth First Search algorithm(DFS) traverses a graph in a
depth ward motion and uses a stack to remember to get the
next vertex to start a search when a dead end occurs in any
iteration.
• Algorithm
1. Visit adjacent unvisited vertex. Mark it visited.
Display it. Push it in a stack.
2. If no adjacent vertex found, pop up a vertex from
stack. (It will pop up all the vertices from the stack
which do not have adjacent vertices.)
3. Repeat step 1 and 2 until stack is empty.
DFS Example
1. Initialize the stack
2. Mark S as visited and put it onto the stack.
• Explore any unvisited adjacent node from S.
• We have three nodes and we can pick any of
them.
• For this example, we shall take the
node in alphabetical order.
Output - S
3. Mark A as visited and put it onto the stack.
• Explore any unvisited adjacent node from A.
• Both S and D are adjacent to A but we are concerned
for unvisited nodes only.
Output – S-A
4. Visit D and mark it visited and put onto the stack.
• Here we have B and C nodes which are
adjacent to D and both are unvisited.
• But we shall again choose in alphabetical
order.
Output – S-A-D
5. We choose B, mark it visited and put onto stack.
• Here B does not have any unvisited adjacent
node. So we pop B from the stack.
Output – S-A-D-B
6. We check stack top for return to previous node and
check if it has any unvisited nodes.
• Here, we find D to be on the top of stack.
Output – S-A-D-B
7. Only unvisited adjacent node is from D is C now.
So we visit C, mark it visited and put it onto the stack.
Output – S-A-D-B-C
8. As C does not have any unvisited adjacent node so we keep
popping the stack until we find a node which has unvisited
adjacent node.
• In this case, there's none and we keep popping until stack is
empty.
Breadth First Search Traversal
• Breadth First Search algorithm(BFS) traverses a graph in a
breadthwards motion and uses a queue to remember to get the
next vertex to start a search when a dead end occurs in any
iteration.
• Algorithm
1. Visit adjacent unvisited vertex. Mark it visited. Display it.
Insert it in a queue.
2. If no adjacent vertex found, remove the first vertex from
queue.
3. Repeat step 1 and 2 until queue is empty.
BFS Example
1. Initialize the queue.
2. We start from visiting S (starting node), and mark it
visited.
Output – S
3. We then see unvisited adjacent node from S.
In this example, we have three nodes but alphabetically
we choose A mark it visited and enqueue it.
Output – S - A
4. Next unvisited adjacent node from S is B.
We mark it visited and enqueue it.
Output – S – A – B
5. Next unvisited adjacent node from S is C.
We mark it visited and enqueue it.
Output – S – A – B – C
6. Now S is left with no unvisited adjacent nodes.
So we dequeue and find A.
7. From A we have D as unvisited adjacent node.
We mark it visited and enqueue it.
Output – S – A – B – C – D
8. At this stage we are left with no unmarked (unvisited) nodes.
But as per algorithm we keep on dequeuing in order to get all
unvisited nodes.
• When the queue gets emptied the program is over.
