A Graph is a non-linear data structure that consists of nodes and edges. The nodes are sometimes referred to as vertices and edges are the lines that connect any two nodes or vertices in the graph.
A more technical definition could be :
“ A Graph is a pair of sets. G = (V,E)
. V is the set of vertices. E is a set of edges. E is made up of pairs of elements from V (unordered pair)”
Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like LinkedIn, Facebook.
Graph Terminology
- Path: It is the sequence of vertices in which each pair of successive vertices is connected by an edge.
- Cycle: It is a path that starts and ends on the same vertex.
- Simple Path: It is a path that does not cross itself that is, no vertex is repeated (except the first and the last). Also, simple paths do not contain cycles.
- Length of a Path: It is the number of edges in the path. Sometimes it’s the sum of weights of the edges also in case of weighted graphs.
- Degree of a Vertex: It is the number of edges that are incident to the vertex.
Now when we have understood about what graph data structure is and it’s terminology, so let’s move ahead and see how we can represent graphs.