Skip to content

Latest commit

 

History

History
68 lines (41 loc) · 3.8 KB

adj_list_rep.md

File metadata and controls

68 lines (41 loc) · 3.8 KB

Adjacency List Representation of a Graph

Introduction

In graph theory, an adjacency list is a common way to represent a graph. It is an efficient and flexible method that helps in handling sparse graphs (graphs with fewer edges). The adjacency list represents the graph as a collection of linked lists or arrays, where each vertex in the graph has its own list of adjacent vertices.

This document explains how to implement an adjacency list using both single and double linked lists, the differences between them, and how they can be applied to various graph algorithms.

Components of the Implementation

Vertices and Edges

  • Vertices: Represent the nodes in the graph.
  • Edges: Represent the connections (or relationships) between nodes. In an undirected graph, an edge (A, B) means there is a connection from A to B and from B to A. In a directed graph, an edge (A, B) means there is a connection from A to B but not necessarily from B to A.

Adjacency List

  • Linked List: Each vertex has its own linked list where the head node is the vertex itself, and all adjacent vertices are stored in this list.
  • Double Linked List: Similar to a linked list, but each node in the list has a reference to both the next and the previous nodes. This is useful for undirected graphs where you might want to traverse in both directions.

When to Use Single and Double Linked Lists

Single Linked List

  • Use Case: Directed graphs where edges have a direction, meaning the connection goes one way.
  • Advantages:
    • Simple and efficient for operations where you need to traverse the graph in one direction.
    • Requires less memory compared to double linked lists.

Double Linked List

  • Use Case: Undirected graphs where edges do not have a direction, meaning the connection goes both ways.
  • Advantages:
    • Allows bidirectional traversal of the graph.
    • Useful for algorithms that require backward traversal, like finding strongly connected components.

Implementation in adj_list.py

The adj_list.py file contains the implementation of an adjacency list using both single and double linked lists. Here’s how it works:

  1. Initialization:

    • The Graph class takes a list of vertices and edges and initializes the adjacency list for each vertex.
    • You can choose whether to use a LinkedList for directed graphs or a DoubleLinkedList for undirected graphs.

  2. Adding Edges:

    • The add_edge method inserts an edge into the adjacency list. If a double linked list is used, it inserts the reverse edge as well, representing the undirected nature of the graph.

  3. Printing the Graph:

    • The print_graph method prints the adjacency list, showing the connections for each vertex.

Graph Search Algorithms

Depth-First Search (DFS)

In DFS, we start at a root node and explore as far as possible along each branch before backtracking. A linked list representation is particularly efficient for DFS because it allows easy traversal of each vertex’s adjacent nodes.

Breadth-First Search (BFS)

BFS starts at a root node and explores all neighbors at the present depth level before moving on to nodes at the next depth level. An adjacency list is efficient for BFS because it allows quick access to all adjacent vertices.

Choosing the Right Data Structure

  • Single Linked List: Suitable for DFS in directed graphs where you only need to traverse in one direction.
  • Double Linked List: Suitable for BFS and DFS in undirected graphs, especially when you need to traverse back and forth between vertices.

Conclusion

Using linked lists (single or double) for adjacency lists provides a flexible and memory-efficient way to represent graphs. Choosing between single and double linked lists depends on the specific needs of your graph and the algorithms you plan to implement.