DSA Graphs

Definition

Graphs serve as a versatile framework to model and analyze how different entities are interconnected. Unlike arrays or lists that store items in a sequence, graphs store items called nodes (or vertices) and the connections between them, called edges. These connections can show how things are linked in networks, maps, or social connections.

What is a Graph?

A graph consists of two main parts:

• Vertices (Nodes): They act as the distinct entities or positions within a graph structure.
• Edges: These are the connectors that establish relationships between pairs of vertices.

Graphs can be:

• Undirected : Imagine two friends who mutually share a connection without any hierarchy.
• Directed : Think of a follower system where one user follows another, but the feeling isn’t necessarily returned.

Why Use Graphs?

Graphs are useful to model situations where things are connected in complex ways, such as:

• Road maps (cities connected by roads)
• Online communities where individuals link through mutual friendships or one-way subscriptions.
• Computer networks (devices connected by cables)
• Webpages (linked to other webpages)

How Graphs Are Stored

Programs typically represent graphs using two primary storage methods:

• Adjacency Matrix: A 2D array where the cell at row i and column j shows if there is an edge between vertex i and vertex j. It's simple but uses more memory.
• Adjacency List: Every node keeps track of the nodes directly linked to it in a compact list.

Basic Graph Terminology

• Degree: The count of direct connections a node has with other nodes.
• Path: An ordered set of nodes where each node links directly to the next one in line.
• Cycle: A path that begins and ends at the same vertex, forming a complete loop.
• Connected Graph: A graph where every node can be reached from any other node via some route.
• Weighted Graph: A graph in which each connection carries a numerical value representing factors like cost or length.

Example

Imagine 4 cities connected by roads:

• City A connected to City B and City C
• City B connected to City A and City D
• City C connected to City A
• City D connected to City B

A: B, C B: 
A, D C: 
A D: B 

In an undirected graph, the connections allow movement in both directions between nodes.

Basic Graph Operations

• Traversal: Visiting nodes systematically.

BFS (Breadth-First Search): Navigates through the graph by exploring all neighbors of a node before moving deeper.

DFS (Depth-First Search): Dives deeply into a branch of the graph, progressing until no further nodes can be visited before retracing steps.

• Finding Paths: Determines whether a route exists linking one specific node to another within the graph.
• Detecting Cycles: Check if the graph contains loops.

Example

graph = {    
       'A': ['B', 'C'],     
       'B': ['A', 'D'],     
       'C': ['A'],     
       'D': ['B'] 
}  

def bfs(start):     
        visited = set()     
        queue = [start]      

        while queue:         
                vertex = queue.pop(0)         
                if vertex not in visited:             
                     print(vertex, end=' ')             
                     visited.add(vertex)             
                     queue.extend([v for v in graph[vertex] if v not in visited])  

Bfs('A')  # Output: A B C D