As we have studied in a tree data structure that there is a hierarchical relationship between the parents and their children, where each parent has many children. In a graph, there is a relationship between many parents and many children. The graphs are used extensively in many real-life applications like finding shortest routes, networks, statistical analysis, flowcharts, etc.
Definition of Graph in Data Structures
A graph G is a collection of two sets V and E, where set V consists of the vertices v₀,v₁,v₂,v₃….vₐ₋₁ and set E consists of the edges e₁,e₂,e₃…..eₐ.
The set of vertices is non-empty and the set of edges contains pairs of vertices. If e = (v₁,v₂) is an edge, then v₁ and v₂ are said to lie on the edge e and e is said to be incident with v₁ and v₂.
The graph can be represented as G = (V,E) where,
V(G) = (v₀,v₁,v₂,v₃….vₐ₋₁), the set of vertices
E(G) = (e₁,e₂,e₃…..eₐ), the set of edges.
Adjacency – Vertices u and v are said to be adjacent to each other if (u,v) is the edge set.
Types of Graphs in Data Structures
A graph can be of two types –
- Undirected Graph
- Directed Graph
Undirected Graph
In an undirected graph, the order of the vertices in the pairs in the Edge set does not matter. Thus, the pair of vertices is in an unordered set. The graphs drawn are examples of an undirected graph. The edges of undirected graphs are generally drawn with straight lines between the vertices.
The adjacency relation is symmetric in an undirected graph, therefore, if u – v then it is also the case of v – u.
Directed Graph
In a directed graph the pair of vertices is an ordered set. That is, the order of the vertices in the pairs in the edge set matters. Thus, u is adjacent to v only if the pair <u,v> is the Edge set. The edges between the vertices of directed graphs are generally shown as arrows. An arrow from u to v is drawn only if (u,v) is in the Edge set. The directed graph is given below –
Non-Weighted and Weighted Graphs
In a non-weighted graph, no weights are assigned to its edges. A weighted graph is an edge-labeled graph where the labels can be operated on by usual arithmetic operators, including comparisons like using less than or greater than operators. Usually, they are integers or floats. Some edges may be more or less expensive, and this cost is represented by the edge labels or weight.
Given below, is an example of a Weighted Undirected Graph
Terminologies related to Graph
Adjacent Nodes – A vertex v1 is adjacent to vertex 2v if there is an edge between v1 and v2. In an undirected graph, if (v1,v2) is an edge between the vertices v1 and v2, then v1 is adjacent to v2 and v2 is adjacent to v2. In a directed graph, if <v1,v2> is an edge between the vertices v1 and v2, then v1 is adjacent to v2 and v2 is adjacent to v1.
Incidence – In an undirected graph, an edge (v1,v2) is incident on vertices v1 and v2. In a diagraph, an edge <v1,v2> is incident from vertex v2 and incident to vertex v2.
Length of a Path – The of path is the total number of edges included in the path.
Closed Path – A path is closed if the first and last vertices of the path are same.
Simple Path – It is a path in which all the vertices are distinct except the first and the last one.
Cycle – A simple path in which the first and the last vertices are same is called a called a cycle.
Acyclic Graph – A graph with no cycles is known as an acyclic graph.
Degree – In an undirected graph, the degree of a vertex is the number of edges incident on it.
In a diagraph, there are two degrees of every vertex called indegree and outdegree.
- Indegree – The indegree of a vertex is the number of edges incident to it.
- Outdegree – The outdegree of a node is the number of edges incident from it.
Source – A vertex that has no incoming edges, but has outgoing edges is called the source node.
Sink – A vertex that has no outgoing edges, but has incoming edges is called the sink node.
Multigraph – A graph with loops is called a multi-graph.
In this article, we learned a brief introduction to graphs and types of graphs, and various terminologies that are commonly used in Graphs.
Attempt Free Data Structures MCQ Test
