Graph in Data Structure

What is a Graph?

A graph is a nonlinear data structure made up of nodes or vertices (V) and edges. It is used to depict the relationship between two objects. Edges are the lines or arcs that connect any two nodes in a graph.

Basic Terminology for Graphs

• Vertex (Node): Each data element is referred to as a vertex or node.
• Edge (Arc): An edge (arc) is a connector between two nodes or vertices.
• Undirected Edge: An undirected edge goes in both directions.
• Directed Edge: A directed edge is one that only goes in one direction.
• Weighted Edge: An edge that has value (cost).
• Degree: The total number of edges connecting a vertex in a graph.
• Indegree: Indegree is the total number of incoming edges connecting to a vertex.
• Outdegree: Outdegree is the total number of outgoing edges connecting to a vertex.
• Self-loop: A self-loop is defined as an edge whose two endpoints coincide.
• Adjacency: When an edge connects two vertices, they are said to be adjacent.

Usages of the Graph

• Telephone and circuit networks.
• GPS systems and Google Maps for finding the shortest paths.
• Google's algorithm for assessing search result relevancy.
• Social networks (LinkedIn, Facebook, Twitter, etc.) used to symbolize user connections

Types of Graphs in Data Structures

Following are the types of Graphs in Data Structures:

• Finite Graph
• Infinite Graph
• Trivial Graph
• Simple Graph
• Multi Graph
• Null Graph
• Complete Graph
• Pseudo Graph
• Regular Graph
• Weighted Graph
• Directed Graph
• Undirected Graph
• Connected Graph
• Disconnected Graph
• Cyclic Graph
• Acyclic Graph
• Directed Acyclic Graph
• Subgraph

Finite Graph

Finite graphs have a finite number of edges and vertices. In other words, the number of vertices and edges in a finite graph are both restricted and countable.

Infinite Graph

An infinite graph is defined as one with an infinite number of edges and vertices.

Trivial Graph

A finite graph G=(V, E) that has only one vertex and no edges is referred to as trivial. It's also called a singleton graph or a graph with only one vertex.

Simple Graph

A simple graph G=(V, E) has only one edge between each pair of nodes or vertices. Only one edge connects two vertices to illustrate one-to-one interactions between them.

Multi Graph

A graph G=(V, E) is called a multigraph if it has parallel edges connecting two vertices but no self-loops. A loop, or self-loop, is a graph edge that begins at one vertex and finishes at the same vertex.

Null Graph

It's an updated version of a simple graph. A null graph contains many vertices but no edges connecting them. A null graph is also known as an edgeless graph, isolated graph, or discrete graph.

Complete Graph

A simple graph G=(V, E) with n vertices is also referred to as a complete graph if the degree of each vertex is n-1, i.e. one vertex is connected to the other vertices in the graph via n-1 edges. A complete graph is also known as a Full Graph.

Pseudo Graph

A pseudograph exists when a graph G= (V, E) includes a self-loop as well as numerous edges.

Regular Graph

A regular graph is a simple graph G= (V, E) with all vertices having the same degree. It is a sort of undirected graph in which each vertex has an equal number of edges or neighbors.

Weighted Graph

A weighted graph is one in which each edge has a cost or weight associated with it.

Directed Graph

A directed graph, also known as a digraph, is a set of nodes connected by edges, each having its own direction.

Undirected Graph

An undirected graph is one in which the edges have no direction, that is, there are no arrows indicating the direction of traversal.

Connected Graph

A graph G = (V, E) is considered to be linked if there is at least one path connecting each pair of vertices in the graph.

Disconnected Graph

A disconnected graph is one in which there is no path connecting at least one pair of vertices in G = (V, E). A null graph with n vertices is a disconnected one.

Cyclic Graph

A graph is considered cyclic if it has at least one cycle.

Acyclic Graph

A graph is referred to as acyclic if it has no cycles.

Directed Acyclic Graph

It's a graph with directed edges and no cycle.

Subgraph

A subgraph is a collection of vertices and edges from one graph that form a subset of another.

Representation of Graph in Data Structures

• Graph representation: Data is organized and visualized using nodes (vertices) and edges.
• Nodes: Nodes are used to represent individual entities.
• Edges: Edges represent linkages or connections between entities.
• Directionality: Edges can be directional or non-directional.
• Memory storage: Uses ways to store graphs in computer memory.

Implementation of Graph in Data Structure

Sequential (Adjacency Matrix)

• The most basic way to describe a graph is using a 2D array of V x V vertices, each row and column representing a vertex.
• The matrix contains "0" or "1".
• 0 indicates that there is no path, but 1 indicates that there is a way.

Linked list (Adjacency List)

• A graph is represented as an array (A) of linked lists.
• The vertices are stored as indexes in a one-dimensional array, whereas the edges are saved as lists.
• It indicates that each element of the array Ai is a list.
• It includes all vertices next to vertex i.

Operations on Graphs in Data Structures

• Insert vertex: This is a simple addition of a vertex (node) in a graph. It does not need to be connected to any other vertex (node) via an edge.
• Delete vertex: To remove a nod, we must also remove all of its connected edges.
• Insert Edge: This method creates an edge between two vertices.
• Delete Edge: An edge can be removed by breaking the link between its vertices or nodes. If all of the edges from a specific vertex(node) are deleted, it becomes an isolated vertex.
• Graph Traversal: Graph traversal is the process of inspecting or updating each vertex in a graph. Such traversals are classed based on the sequence in which the algorithm traverses the vertices. The subset of tree traversal is graph traversal.

Application of Graphs

• Maps & GPS: Graphs are used to represent maps and GPS in computer-based services.
• Task dependencies: Task order is determined using Directed Acyclic Graphs (DAGs).
• Topological Sort: Used to determine task execution order in DAGs.
• State Transition Diagram: Shows legal transitions from present states.
• Computer Networks: Topology shown using graphs, including router and switch links.

Advantages of Graphs

• Versatile Representation: Graphs represent a variety of relationships and data structures.
• Problem-Solving: Used for pathfinding, data clustering, network analysis, and machine learning.
• Efficient: Graph algorithms provide fast and effective solutions to complicated problems.
• Simplified Complexity: Graphs describe complex data structures simply and intuitively, facilitating comprehension and analysis.

Disadvantages of Graphs

• Complexity Challenge: Graphs can be difficult to understand, particularly for non-experts.
• Computational Costs: Creating and managing graphs can be resource-intensive, especially for large or complex ones.
• Algorithm Complexity: Creating and implementing graph algorithms can be error-prone.
• Visualization Challenges: Analysing large or complex graphs can be difficult, limiting insight extraction.