graph representation.pdf

Graph

1. Graph and its representations
A graph is a data structure that consists of the following two components:
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge.
ordered because (u, v) is not the same as (v, u) in case of a directed
graph(di-graph). The pair of the form (u, v) indicates that there is an edge
from vertex u to vertex v. The e
Graphs are used to represent many real
to represent networks. The networks may include paths in a city or
telephone network or circuit network. Graphs are also used in social
networks like linkedIn, Facebook. For example, in Facebook, each person
is represented with a vertex(or node). Each node is a structure and
contains information like person id, name, gender, and locale. See
more applications of graph.
Following is an example of an undirected graph with 5 vertices.
The following two are the most commonly used representations of a
graph.
1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence
List. The choice of graph representation is situation
depends on the type of operations to be performed and ease of use.
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
Graph and its representations
A graph is a data structure that consists of the following two components:
A finite set of vertices also called as nodes.
A finite set of ordered pair of the form (u, v) called as edge.
ordered because (u, v) is not the same as (v, u) in case of a directed
graph). The pair of the form (u, v) indicates that there is an edge
from vertex u to vertex v. The edges may contain weight/value/cost.
Graphs are used to represent many real-life applications: Graphs are used
to represent networks. The networks may include paths in a city or
telephone network or circuit network. Graphs are also used in social
ike linkedIn, Facebook. For example, in Facebook, each person
is represented with a vertex(or node). Each node is a structure and
contains information like person id, name, gender, and locale. See
more applications of graph.
Following is an example of an undirected graph with 5 vertices.

The following two are the most commonly used representations of a
There are other representations also like, Incidence Matrix and Incidence
List. The choice of graph representation is situation-specific. It totally
depends on the type of operations to be performed and ease of use.
Adjacency Matrix is a 2D array of size V x V where V is the number of
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
A graph is a data structure that consists of the following two components:
A finite set of ordered pair of the form (u, v) called as edge. The pair is
ordered because (u, v) is not the same as (v, u) in case of a directed
graph). The pair of the form (u, v) indicates that there is an edge
dges may contain weight/value/cost.
life applications: Graphs are used
to represent networks. The networks may include paths in a city or
telephone network or circuit network. Graphs are also used in social
ike linkedIn, Facebook. For example, in Facebook, each person
is represented with a vertex(or node). Each node is a structure and
contains information like person id, name, gender, and locale. See this for
Following is an example of an undirected graph with 5 vertices.
The following two are the most commonly used representations of a
There are other representations also like, Incidence Matrix and Incidence
specific. It totally
depends on the type of operations to be performed and ease of use.
Adjacency Matrix is a 2D array of size V x V where V is the number of
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

2. for undirected graph is always symmetric. Adjacency Matrix is also used
to represent weighted graphs. If adj[i][j] = w, then there is
vertex i to vertex j with weight w.



The adjacency matrix for the above example graph is:

Pros: Representation is easier to implement and follow. Removing an
edge takes O(1) time. Queries like whether there is an edge from vertex
‘u’ to vertex ‘v’ are efficient and can be done O(1).
Cons: Consumes more space O(V^2). Even if the graph is
sparse(contains less number of edges), it consumes the same space.
Adding a vertex is O(V^2) time.
Please see this for a sample Python implementation of adjacency matrix.


Adjacency List:
An array of lists is used. The size of the array is equal to the number of
vertices. Let the array be an array[]. An entry array[i] represents the list
for undirected graph is always symmetric. Adjacency Matrix is also used
to represent weighted graphs. If adj[i][j] = w, then there is
vertex i to vertex j with weight w.
The adjacency matrix for the above example graph is:

Representation is easier to implement and follow. Removing an
edge takes O(1) time. Queries like whether there is an edge from vertex
ertex ‘v’ are efficient and can be done O(1).
Consumes more space O(V^2). Even if the graph is
sparse(contains less number of edges), it consumes the same space.
Adding a vertex is O(V^2) time.
for a sample Python implementation of adjacency matrix.
An array of lists is used. The size of the array is equal to the number of
vertices. Let the array be an array[]. An entry array[i] represents the list
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

Representation is easier to implement and follow. Removing an
edge takes O(1) time. Queries like whether there is an edge from vertex
Consumes more space O(V^2). Even if the graph is
sparse(contains less number of edges), it consumes the same space.
for a sample Python implementation of adjacency matrix.
An array of lists is used. The size of the array is equal to the number of
vertices. Let the array be an array[]. An entry array[i] represents the list

3. of vertices adjacent to the
to represent a weighted graph. The weights of edges can be represented
as lists of pairs. Following is the adjacency list representation of the
above graph.




Graph traversal is a technique used for searching a vertex in a graph. The
graph traversal is also used to
search process. A graph traversal finds the edges to be used in the search
process without creating loops. That means using graph traversal we visit
all the vertices of the graph without getting into looping

There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
BFS (Breadth First Search)
BFS traversal of a graph produces a
result. Spanning Tree is a graph without loops. We use
djacent to the ith vertex. This representation can also be used
to represent a weighted graph. The weights of edges can be represented
as lists of pairs. Following is the adjacency list representation of the
Graph traversal is a technique used for searching a vertex in a graph. The
graph traversal is also used to decide the order of vertices is visited in the
search process. A graph traversal finds the edges to be used in the search
process without creating loops. That means using graph traversal we visit
all the vertices of the graph without getting into looping
There are two graph traversal techniques and they are as follows...
DFS (Depth First Search)
BFS (Breadth First Search)
BFS (Breadth First Search)
BFS traversal of a graph produces a spanning tree as final
is a graph without loops. We use
th vertex. This representation can also be used
to represent a weighted graph. The weights of edges can be represented
as lists of pairs. Following is the adjacency list representation of the

Graph traversal is a technique used for searching a vertex in a graph. The
decide the order of vertices is visited in the
search process. A graph traversal finds the edges to be used in the search
process without creating loops. That means using graph traversal we visit
all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
as final
is a graph without loops. We use Queue data

4. structure with maximum size of total number of vertices in the graph to
implement BFS traversal.

We use the following steps to implement BFS traversal...
• Step 1 - Define a Queue of size total number of vertices in the
graph.
• Step 2 - Select any vertex as starting point for traversal. Visit that
vertex and insert it into the Queue.
• Step 3 - Visit all the non-visited adjacent vertices of the vertex
which is at front of the Queue and insert them into the Queue.
• Step 4 - When there is no new vertex to be visited from the vertex
which is at front of the Queue then delete that vertex.
• Step 5 - Repeat steps 3 and 4 until queue becomes empty.
• Step 6 - When queue becomes empty, then produce final spanning
tree by removing unused edges from the graph

6. DFS (Depth First Search)
DFS traversal of a graph produces a spanning tree as final
result. Spanning Tree is a graph without loops. We use Stack data
structure with maximum size of total number of vertices in the graph to
implement DFS traversal.

We use the following steps to implement DFS traversal...
• Step 1 - Define a Stack of size total number of vertices in the graph.
• Step 2 - Select any vertex as starting point for traversal. Visit that
vertex and push it on to the Stack.
• Step 3 - Visit any one of the non-visited adjacent vertices of a
vertex which is at the top of stack and push it on to the stack.
• Step 4 - Repeat step 3 until there is no new vertex to be visited from
the vertex which is at the top of the stack.
• Step 5 - When there is no new vertex to visit then use back
tracking and pop one vertex from the stack.
• Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
• Step 7 - When stack becomes Empty, then produce final spanning
tree by removing unused edges from the graph