Page Content

Tutorials

What are the Graphs in Data Structure With Code Example

Graphs in Data Structure

Graphs in Data Structure
Graphs in Data Structure

In computer science, graphs a basic non-linear data structure are used to depict the relationships between item pairs. A collection of objects known as vertices (or nodes) and a group of edges which are pairwise connections between these vertices make up this structure. Graphs have a wide range of uses, including modelling computer networks, transportation networks, social networks like Facebook and LinkedIn, and even plumbing and electrical wiring systems. They are essential for the correct operation of many computer algorithms.

Graph Terminology

It’s crucial to know some terms in order to completely comprehend graphs:

Vertices (Nodes): The individual items or things that make up the graph are called vertices, or nodes. Nodes can be used to represent a variety of entities in computer programs, including departments, individuals, file folders, and airports. Usually, arbitrary elements are stored in each vertex.

Edges: The linkages or connections between pairs of vertices are represented by edges. An object like a flight number, journey distance, or cost can be linked to an edge.

Path: Nodes joined by edges form a path. Nodes and edges must have one root path to form a tree. If no vertex returns, the path is straightforward.

Cycle:A cycle is a graph path that starts and ends at the same vertex and has at least one edge. Except for the first and last vertices, a simple cycle has separate vertices. Similar to directed graphs, directed cycles traverse all edges in their designated direction. Cyclic graphs have at least one cycle, where a node returns to itself. Cyclical data structures include circularly linked lists, where the tail points to the head.

Degree: The quantity of edges that are incident on a specific node. The number of incoming edges and departing edges in a directed graph are denoted by the terms in-degree and out-degree, respectively. An undirected graph’s total degrees are twice as many as its edges.

Neighbors (Adjacent Vertices):In graphs, two vertices, “u” and “v,” are neighbours or neighbouring if an edge connects them. They are connected by an edge. A flight between two airports makes them adjacent in a flight network. The origin and destination of an edge from “u” to “v” are “u” and “v”. The edge is “incident” to both ends.

Subgraph: A graph H with subsets of G’s vertices and edges is a subgraph of G. Thus, a subgraph is created by removing some or all vertices and edges from an original graph. A domain like wiley.com would form a subgraph of the Internet if it were a graph with vertices being computers and undirected links being communication connections.

Spanning Subgraph: A spanning subgraph contains all the graph’s vertices. To clarify, a subgraph is a graph with subsets of vertices and edges from a larger graph. Thus, a spanning subgraph retains all vertices but may have just some edges. This technique is often used to create a spanning tree, a linked forest (a graph without cycles) and spanning subgraph.

Forest: A graph without any cycles is called a forest. Since a tree is essentially a connected forest that is, a connected graph devoid of cycles this idea fits within the broad category of trees. Trees are seen as a broader class of graphs.

Tree: A linked graph without any cycles. The definition in Chapter 8 that may suggest a specified root is somewhat different from this one, which views a tree as a connected forest. Trees are examples of graphs, a broader group.

Root: A tree data structure’s top node, the “root”, is essential. Each tree has one root and no parent, distinguishing it from other nodes. Edges from the root lead to all other tree nodes. Other nodes extend downward from the root node, which is usually at the top of the diagram.

Parent/Child: Tree data structures have a hierarchical relationship between “parent” and “child” nodes. Each node in a tree, excluding the top element, has one unique parent and zero or more children. The “parent” is the node immediately connected above another by an edge, while the “children” (also termed “branches”) are the nodes below it. Nodes with the same parent are “siblings”.

Leaf Nodes: Any node without children is a “leaf node” in tree data structures. Also called “external nodes”. Internal nodes have children. A tree with one root might have numerous leaf nodes. There is just one path from the root to any leaf node.

Types of Graphs

Based on their connectedness and edge characteristics, graphs can be categorised as follows:

Directed Graphs: In a directed graph, the link travels vertex (u) to a destination vertex (v). For instance, flights within an airline network or inheritance relations in an object-oriented program are usually directed.

Undirected Graphs: Connections are symmetric and edges lack a defined direction. One instance of an undirected interaction is when researchers co-author.

Weighted Graphs: In a weighted graph, each edge is assigned a number label or “weight” that can be a distance, cost, or other metric. Weighted graphs are frequently used in minimal spanning trees and short path problems. Such numerical values are absent from an unweighted graph.

Cyclic Graph: A graph with at least one cycle is called a cyclic graph. A path that starts and finishes at the same vertex and has at least one edge is called a cycle. Basically, by following the links (edges) in a cyclic graph, one can move from one node to another and eventually return to the original node.

Acyclic Graph: Acyclic graphs lack cycles. Often used to express prerequisites or scheduling constraints, a directed acyclic graph (DAG) is a directed graph devoid of directed cycles.

Connected Graph:A connected graph has a path between any two nodes or vertices. From every graph node, you can navigate to all others. An undirected graph with ‘n’ vertices and’m’ edges must have at least ‘n-1’ edges to be linked. network traversal methods like Depth-First Search (DFS) are essential for network connectivity analysis.

Disconnected Graph: A disconnected graph is unconnected. In such a graph, every pair of nodes cannot be connected. In an unconnected graph, its largest connected subgraphs are called its connected components. The DFS full function may analyse these connected components in an undirected network, returning a discovery dictionary that depicts a DFS forest rather than a tree, revealing the graph’s disconnectedness.

Null Graph: A graph without any edges is called a null graph. This indicates that even while it might include vertices, or nodes, none of them are connected to one another. A null graph can be represented graphically.

Complete Graph: A complete graph is a basic graph with edges connecting each pair of unique vertices. A full graph has an edge for every pair of vertices (nodes). A full simple undirected graph has an edge between every pair of different vertices. Every graph vertex is directly connected.

Multigraph: A multigraph is a graph that allows two or more edges to connect the same two nodes. A multigraph has two or more edges connecting the same nodes. Parallel or numerous edges connect the same end vertices. Due to the fact that graph edges are a collection rather than a set, duplicated connections are allowed.

Representing a Graph in a Program

Programmers can use a variety of data structures to describe graphs, each with pros and cons related to operating performance and space utilisation. Typical portrayals consist of:

Edge List Structure: The simplest form is the edge list structure, which stores all edge objects in an unordered list E and all vertex objects in an unordered list V. While it takes O(1) to add a new vertex or edge, exhaustive examination necessitates O(m) time to discover a single edge or all edges incident to a vertex. The space utilisation is O(n + m).

Adjacency List Structure: By assigning a collection (such as a list or dictionary) of incident edges to every vertex, the Adjacency List Structure groups edges. This enables incident edges to be efficiently retrieved in O(deg(v)) time, where deg(v) is the vertex v’s degree. The space utilisation is O(n + m).

Adjacency Matrix Structure: Makes use of a two-dimensional array with n vertices, or n x n matrix. In the event that the edge (u, v) exists (where u is vertex i and v is vertex j), an item A[i, j] contains a reference to it; if not, it contains None. This gives O(1) access to a certain edge (u,v). For sparse graphs (graphs with few edges in relation to vertices), it may be inefficient because it takes O(n^2) space.

The adjacency map representation is used in many Python implementations, in which each vertex is mapped to its incidence map (a Python dictionary that maps neighbouring vertices to their corresponding edges) by a top-level dictionary. This makes the implementation simpler and frequently results in O(1) expected time for vertex lookups by avoiding the need to explicitly maintain lists for vertices and edges.

The following Python code demonstrates how to create a graph using an adjacency map:

Example:

class GraphAdjacencyList:
    def _init_(self):
        self.graph = {}
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph:
            self.graph[vertex1].append(vertex2)
        if vertex2 in self.graph:
            self.graph[vertex2].append(vertex1)  
    def display(self):
        for vertex, edges in self.graph.items():
            print(f"{vertex}: {edges}")
# Example
g = GraphAdjacencyList()
g.add_vertex(1)
g.add_vertex(2)
g.add_vertex(3)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.display()

Output:

1: [2]
2: [1, 3]
3: [2]

Because vertices and edges have hash methods, they may be utilised as keys in this implementation, which employs nested Vertex and Edge classes with Python dictionaries (outgoing and incoming) to create adjacency maps. Directed or undirected graph initialisation influences edge management.

Computer science is about graphs and methods like minimum spanning tree, shortest path, and graph traversal. With this knowledge, programmers may choose the best data structures and algorithms.

Kowsalya
Kowsalya
Hi, I'm Kowsalya a B.Com graduate and currently working as an Author at Govindhtech Solutions. I'm deeply passionate about publishing the latest tech news and tutorials that bringing insightful updates to readers. I enjoy creating step-by-step guides and making complex topics easier to understand for everyone.
Index