- A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links.
- The interconnected objects are represented by points termed as vertices, and the links that connect the 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. Take a look at the following graph −
In the above graph,
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Graph Data Structure
- Data structures can be used to define mathematical graphs. An array of vertices and a two-dimensional array of edges can be used to represent a graph. Before we go any further, let's make sure we're all on the same page with certain key terminology.
- Vertex − A vertex is a representation of each node in the graph. The labeled circle in the following example represents vertices. As a result, A to G are vertices. As seen in the above image, we can represent them using an array. Index 0 identifies A in this case. Index 1 can be used to identify B, and so forth.
- Edge − A path or a line connecting two vertices is represented by an edge. The lines from A to B, B to C, and so on indicate edges in the following example. As seen in the following graphic, a two-dimensional array can be used to depict an array. AB can be represented as 1 in row 0, column 1, BC in row 1, column 2, and so on, with the rest of the combinations remaining as 0.
- Adjacency − If two nodes or vertices are connected to each other by an edge, they are said to be neighboring. B is adjacent to A in the following example, C is adjacent to B, and so on.Path - Path is a set of edges that connects the two vertices. ABCD depicts a path from A to D in the example below.
Basic Operations
- 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.
