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

0

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

**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.

Please log in to add an answer.