Graph

A graph is a data structure that consists of a set of nodes (also called vertices) and a set of edges that connect pairs of nodes. Graphs can be directed or undirected, depending on whether the edges have a direction associated with them. They are used to represent various types of relationships and connections, such as social networks, transportation systems, and communication networks.

Types of Graphs

  1. Directed Graph (Digraph): A graph where each edge has a direction, indicating a one-way relationship between nodes.
  2. Undirected Graph: A graph where edges have no direction, indicating a two-way relationship between nodes.
  3. Weighted Graph: A graph where each edge has an associated weight or cost, representing the strength or distance of the connection between nodes.
  4. Unweighted Graph: A graph where edges do not have associated weights or costs.
  5. Connected Graph: A graph where there is a path between every pair of nodes.
  6. Disconnected Graph: A graph where there are isolated nodes or groups of nodes that are not connected to the rest of the graph.
  7. Cyclic Graph: A graph that contains at least one cycle, which is a path that starts and ends at the same node.
  8. Acyclic Graph: A graph that does not contain any cycles.

Graph Representation

  1. Adjacency Matrix: A 2D array where the value at row i and column j indicates the presence or weight of an edge between nodes i and j.
  2. Adjacency List: A list where each node has a list of its adjacent nodes, along with the weights of the edges if applicable.
  3. Edge List: A list of all edges in the graph, where each edge is represented as a pair of nodes (and optionally the weight).

Graph Traversal

Graph traversal refers to the process of visiting each node in a graph in a specific order. The common graph traversal methods include:

  1. Depth-First Search (DFS): A traversal method that explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack.
  2. Breadth-First Search (BFS): A traversal method that explores all the neighbors of a node before moving on to the neighbors’ neighbors. It can be implemented using a queue.
  3. Dijkstra’s Algorithm: A traversal method used to find the shortest path between nodes in a weighted graph.
  4. A* Search Algorithm: A traversal method that uses heuristics to find the shortest path between nodes in a weighted graph, often used in pathfinding and graph traversal.
  5. Topological Sort: A traversal method used to order the nodes of a directed acyclic graph (DAG) in a linear sequence based on their dependencies.

    Graph Example

    1
    2
    3
    4
    5
        A
       / \
      B   C
     / \   \  
    D   E   F
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_edge(self, u, v, weight=1):
        if u not in self.adjacency_list:
            self.adjacency_list[u] = []
        if v not in self.adjacency_list:
            self.adjacency_list[v] = []
        self.adjacency_list[u].append((v, weight))
        self.adjacency_list[v].append((u, weight))  # For undirected graph

    def bfs(self, start):
        visited = set()
        queue = [start]
        while queue:
            node = queue.pop(0)
            if node not in visited:
                print(node)
                visited.add(node)
                for neighbor, _ in self.adjacency_list.get(node, []):
                    if neighbor not in visited:
                        queue.append(neighbor)

    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        if start not in visited:
            print(start)
            visited.add(start)
            for neighbor, _ in self.adjacency_list.get(start, []):
                self.dfs(neighbor, visited)
        
graph = Graph()
graph.add_edge('A', 'B')