Introduction to Graph

Introduction to Graph Data Structure

Introduction

A graph is a non-linear kind of data structure made up of nodes or vertices and edges. The edges connect any two nodes in the graph, and the nodes are also known as vertices.

Video Explanation

Vertex/Node

Vertex or node, which represents elements. In the image below, the circles are the nodes, each node can represent a city, state, country, building, person, or any other object depending upon the problem.

Edge

Edges, which represent relationships between elements. In the image below, the lines are the edges, each edge can represent a connection between two cities, persons, or any other object.

Directed Graph

A directed graph also referred to as a digraph, is a set of nodes connected by edges, each with a direction.

Undirected Graph

An undirected graph comprises a set of nodes and links connecting them. The order of the two connected vertices is irrelevant and has no direction. You can form an undirected graph with a finite number of vertices and edges.

Weighted Graph

A graph G = (V, E) is called a labeled or weighted graph because each edge has a value or weight representing the cost of traversing that edge.

Unweighted Graph

A graph G = (V, E) is called an unweighted graph because the edge only represents a connection between two nodes.

Concluding Types of Graph

Weighted and Directed Vs Weighted and Undirected Graph

Similarly, you can form other combinations of Unweighted and Directed Graph and Unweighted and Undirected Graph.

Path

A path in a graph is a finite or infinite sequence of edges that joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges).

Cycle

A path that starts from a given vertex and ends at the same vertex is called a cycle.

💡

Note: In the Directed Graph shown above, 0 -> 1 -> 2-> 0 is not a cycle.

Indegree

In-degree of a vertex is the number of edges coming to the vertex.

Outdegree

Out-degree of a vertex is the number of edges that are coming out from the vertex.

💡

Note: In the case of the Undirected Graph, the number of Indegree and Outdegree of any vertex are equal.