ARTICLE: Data Structure: Graphs and Its Types

The ordered set (V, E) where v is the set of vertices and E is the set of edges is a graph. The edges of the graph connect two vertices. There are two types of graphs, directed or undirected. In the latter form of a graph, the edges do not have any specific location.

If you want to read the topic, ‘operations of data structure, and queues,’ click on the link.

SIMPLE GRAPH

It is a type of graph which neither has any the parallel edges, nor the self-loops and is called a simple graph.

DIGRAPH

The type of graph which consists of directional edges is called a digraph. Those edges, e= (u, v) can be traversed in the order ‘u’ to ‘v’, not from the order from v to ‘u’, the initial vertex of e is ‘u’, and the terminal vertex is v.

SIMPLE DIRECTED GRAPH

As the name suggests, it is a graph in which the edges of the simple graph have directions.

WEIGHTED GRAPH

There is some weight on each edge of the graph, and that graph is called the weighted graph. Let us take an example; we have a roadmap, say from the city A to B. The distance of the cities is 20 Km. The road or the edge which as providing a connection between the two vertices can be numbered as 20. This figure is the weight of the particular edge.

In the non-weighted graph, there is an assumption of the equal weight of the edges. In the default cases, one is taken as the positive number.

CONNECTED GRAPH

When there is an availability of at least one path between every pair of the vertices, then it is called a connected graph.

COMPLETE GRAPH

Here in the complete graph, there is a connection between the edges of the graph between each pair of the vertices.

NULL GRAPH

When there is an edge between them, in that case, the two vertices of the graph are called to be adjacent. The isolated vertex is that in which there is no adjacency of the edges of the graph. The null graph is the one where the graph only contains only the isolated vertices.

HAMILTONIAN CYCLES

There is a graph called G, and it has n vertices. The nature of the graph can be anything from the directed, or it may be undirected as well. The Hamiltonian cycle is the one in which there is a circular path of n edges as well as it explores all the vertices of the graph for once and then returns to the starting point.

GRAPH TRAVERSAL

There are two techniques to traverse a graph in a systematic order-

a) Breadth First Search
b) Depth First Search

Breadth First Search (BFS)

The task of the breadth-first search begins with node A of the graph. After this, all the neighbours of the node A of the graph G are to be visited. You can accompany the process in the form of a queue. When we are done with the examination of the neighbours of the node A, then all of its neighbours are to be inserted into the queue. After this, the node has to be deleted from the queue.

Depth First Search (DFS)

The process in which all the vertices of the graph are explored is called traversing in a graph. It happens in a one by one manner and the systematic order. The procedure of the depth-first search on traversing the graph from node A begins with A. Then after initiation of the traversing, the inspection of the neighbour has to be done. Suppose we find the neighbour as B and the process goes on. Once after going through this, we would enter a dead state. Here you would find no vertex to explore. In this situation, examining another neighbour for the already explored vertex is the option. It has to be done until all the nodes get explored. In this form of searching, the process of backtracking takes place with the maintenance of the stack in the memory of the already processed vertices. It can either be directed or undirected graph.

MINIMUM COST SPANNING TREES

When we have a graph G which is undirected, then there is a sub-graph of that graph G. It would be a spanning tree if an only if when it contains all the vertices of the vertices of G.

When the graph G is a weighted graph, then the sum of the weights of all the edges of the graph is the weight of the graph. The minimum cost spanning tree is the spanning tree which contains the minimum weight in the graph.

TOPOLOGICAL SORT

When we have a graph G which have the nodes N represented as the jobs to be done. The edges of that graph are directed. This shows that until we complete the job a, the job b cannot be begun.

If there is a graph where neither of the jobs could be completed, then the linear ordering of the nodes come under the topological order. The condition is that the job ‘a’ of the edge e must appear before job b in the ordering which is linear. The topological sort shows the order of the completion of the graph. But there should not be any cycle in the graph, and there can be more than one topological sort for a graph.