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

Marks: 3 M

Year: Dec 2014

• 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

b. Linked representation

• It is implemented using a adjacency list
• It contains a linked list of all nodes in the graph.
• Moreover, each node is in turn linked to its own list that contains names of all other nodes that are adjacent to it.
• Such kind of representation is often used for small to moderate sized graphs.
• A main disadvantage of adjacency matrix is that it is difficult to carry out insetion/deletion as it requires a lot of shifting operations in the matrix.
• Here we can easily insert or delete as we use linked lists.
• Such kind of lists are easy to follow and clearly shows the adjacent nodes of a node.