Question: Define a graph. What are the methods to represent a graph?
0

Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: Dec 2014

 modified 3.1 years ago  • written 3.1 years ago by Yashbeer ★ 160
0
• Graph is a non-linear data structure that is same as the mathematical (discrete mathematics) concept of graphs.
• It is a collection of nodes(also called as vertices) and edges that connect these vertices.
• Graphs are used to represent arbitrary relationship among objects.
• A graph can be directed (where each edge has direction assigned to it with arrow-head) or undirected(no direction associated)
• There are mainly two methods of representing graphs:

a. Sequential Representation

• This kind of representation is achieved by using the adjacency matrix.
• Adjacency matrix is used to represent which nodes are adjacent to each other i.e is there a edge connecting two nodes on a graph.
• The adjacency matrix is of dimension n×n where n is number of nodes.
• If a edge is present from i to j then $A_{ij} =1$ else the value will be set to 0. If it is a weighted graph, we replace 1 with the weight of that edge.
• The memory use of an adjacency matrix is $O(n^2)$ where is the number of nodes.
• An example of adjacency matrix is shown below