GRAPH DATA STRUCTURE DATA STRUCTURE & ALGORITHMS

DATA STRUCTURE - GRAPH DATA STRUCTURE DATA STRUCTURE & ALGORITHMS

What is a Graph?

The pictorial representation of the set of objects, where few of them are connected through links is called as Graph. The objects are called as vertices and the links that connect 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. For instance, look at the following graph -

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

What is Graph Data Structure?

Data Structure facilitates representation of mathematical graphs in data structure. Using an array of vertices and array edges, a graph is represented. Some of the important terms used in the concept of Graph Data Structure are:

• Vertex – The node of the graph is represented as vertex. In the below example, the labelled circle represents vertices, A to G are vertices. They are represented by an array. Here A can be identified by index 0. B can be identified using index 1 and so on.
• Edge – The path or a line between the two vertices is represented as Edge. The edges are represented by the lines from A to B, B to C, and so on. An array is represented by using a two-dimensional array. In the following image, AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
• Adjacency – If two nodes are connected to each other through an edge, then the two nodes or vertices are said to be adjacent. In the image below, B is adjacent to A, C is adjacent to B, and so on.
• Path – The sequence of edges between the two vertices is represented by a path. In the image below, ABCD represents a path from A to D.

What are the basic operations supported by Graph Data Structure?

The basic primary operations supported by a Graph are −

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.