In this chapter we shall learn about:
1.1 Graph Definition
1.2 Types of graph
1.3 Usage of graph
1.1 Graph Definition
Graph like trees is a non-linear data structure. Like trees, graph is also made of collection of nodes/vertices and edges. But unlike trees, graph will not have any root node. In fact, you can start to traverse from any node and move in any direction.
Below is an example of a graph.
As you can see in above image:
1. All the nodes are connected with each other by using edges
2. There is no root node, hence we can start visiting from any node.
3. There is no hierarchical data, hence we can visit from any node to any node having an edge between those 2 nodes.
4. There can be multiple ways to reach 2 points.
Graph Definition:
A graph G is an ordered pair of a set of “V” vertices and a set of “E” edges.
G = (V, E)
Identify the vertices from the below graph image
Vertices V = { A, B, C, D, E}
Identify the EDGES from the above graph image
An edge can be defined as the path between 2 vertices. Here edges can be of 2 types. Directed edge and Un-Directed edge. The above image is of un-directed type. In further chapter we shall study about directed edges.
Edges E = {{A,B}, {B,C}, {C, D}, {D,E}, {E,A}, {A,D}, {B,E}}
If the edge is of undirected type, here {A,B} = {B,A}.
1.2 Types of graph:
1. Undirected Graph:
A graph with undirected edges is called as undirected graph. The edges are called as undirected edges.
2. Directed Graph:
A graph with all the directed edges is called as directed graph or di graph.
3. Weighted Graph
If the edges are labelled, then it is called as weighted graph. Both directed and undirected graph can have a weighted edge.
4. Cyclic Graph
A directed graph with at least one cycle is called as cyclic graph.
5. Acyclic Graph
A directed graph with no cycle is called as acyclic graph
6. Connected Graph
A graph will be called as connected graph, if there exist one path that connects all the vertices.
7. Self-Loop Graph
A graph is called as self-loop graph, if there is only 1 vertex and has a cycle, then it is called as self-loop graph.
8. Disconnected Graph
A graph will be called as disconnected graph, if there is no path between 2 vertices.
Note:
A graph can have both directed and undirected edges at the same time. But in this series, we shall learn about the graph that are either directed or undirected.
1.3 Usage of Graphs:
1. To find the minimum distance between 2 cities.
2. To connect different places in a map.
3. Graph can be extremely useful in social media.