A Graph is a collection of Nodes and Edges, and it is a Non-Linear data structure. It is a mathematical concept in which every node shows a relation with another node through edges. It contains a finite number of vertices(nodes) and each node is connected with another node through an edge.
Graph basic Terminologies
- Nodes (Vertices)
- Edges (linkers, link)
- Weight
- Path
- Cycle
Nodes
Node is the main component of a graph structure which contain data and in Graph, every node has a relation with another node. Suppose if a graph has two nodes a and b so there would be an edge or links between these two nodes. The Edge build an undirected relation between two nodes and it could also be represented as bi-directional.
Edges
Edges help to form a relationship between two nodes and it creates a bidirectional relation. Though it creates an undirected relation between two nodes, it can also be represented as a one-way direction.
Weight
Edges that connects two vertices can have some value which is known as Weight, a weight represent a cost to go from one node to another node. Suppose A and B are two nodes representing two cities, and Edge represents a rode which links the cities A and B so the weight of Edge would represent the distance between these cities.
Path
A path is a sequence of vertices connected through edges. A path could also be a subset of a graph when we want to visit from one vertex to another vertex.
Cycle
A Cycle is a special graph which starting and endpoints are the same.
Types of Nodes used in Graph
There are two types of Nodes we often use in the graph.
- Root Node
- Leaf Node
Root Node
The root node is the parent and head node of each node present in the graph. The first node we create in the graph we termed it as a root node. With the help of a root node, we can traverse to each node. Each graph contains a single root node. A root node always has outgoing edges.
Leaf Node
The node in the graph which does not have any successor node connected to it is known as a leaf node. A leaf node does not have any outgoing edges connected to it. Leaf nodes represent the endpoints of a graph.
Types of Graph
- Undirected Graph
- Directed graph
- Weighted Graph
- Cyclic Graph
Undirected Graph
An Undirected Graph could also be represented as a bi-directional graph, in these graph edges does not point to a specific direction
Directed Graph
These graphs could contain both one or bi-directional edges, unlike Undirected graph here edge points to a specific direction.
Weighted Graph
In a Weighted Graph, each node has some value or cost assigned with it. These graphs could be directed or undirected.
Cyclic Graph
In Cyclic graph the starting and ending nodes are same, it forms a closed loop with its all node and here we have no leaf node.
Graph Representation
We represent a graph with mathematic function G(v,w) here v are the vertices and w represent the edges.
Basic Graph Operations
Here are some basic Graph Operations:
- adjacent( G , x , y ): tests whether there is an edge from the vertex x to the vertex y ;
- neighbors ( G , x ): lists all vertices y such that there is an edge from the vertex x to the vertex y ;
- add_vertex( G , x ): adds the vertex x , if it is not there;
- remove_vertex( G , x ): removes the vertex x , if it is there;
- add_edge( G , x , y ): adds the edge from the vertex x to the vertex y , if it is not there;
- remove_edge( G , x , y ): removes the edge from the vertex x to the vertex y , if it is there;
- get_vertex_value( G , x ): returns the value associated with the vertex x ;
- set_vertex_value( G , x , v ): sets the value associated with the vertex x to v .
- get_edge_value( G , x , y ): returns the value associated with the edge ( x , y );
- set_edge_value( G , x , y , v ): sets the value associated with the edge ( x , y ) to v .