Graph Representations 🎯

Welcome to our deep dive into Graph Representations! This lesson is designed for both beginners and intermediates, so let's embark on this exciting journey together.

What are Graphs? 📝

Graphs are a fundamental data structure used to represent various relationships and connections in real-world scenarios. Think of a map showing roads connecting cities, or a social network with friends connected by relationships.

Why Graphs?

Graphs help us model complex relationships, make decisions, and solve problems efficiently. They are essential in fields like computer science, data science, machine learning, and artificial intelligence.

Graph Representation Types 💡

There are several ways to represent graphs. We will explore two primary types in this lesson:

Adjacency Matrix
Adjacency List

Adjacency Matrix

An adjacency matrix is a two-dimensional array where each cell represents the presence (1) or absence (0) of an edge between two vertices.

💡 Pro Tip: The size of the matrix is n x n, where n is the number of vertices.

python

# Example of an Adjacency Matrix for a simple graph

vertices = 5

graph = [[0, 1, 0, 0, 0],
         [1, 0, 1, 1, 0],
         [0, 1, 0, 0, 1],
         [0, 1, 0, 0, 1],
         [0, 0, 1, 1, 0]]

# Commented code for clarity:
# graph[i][j] = 1 if there is an edge between vertex i and j
# graph[i][j] = 0 if there is no edge between vertex i and j

Adjacency List

An adjacency list is a collection of linked lists, where each linked list represents the neighbors of a vertex.

💡 Pro Tip: Each vertex has its own linked list, and the lists are connected through the vertices' indices.

python

# Example of an Adjacency List for a simple graph

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
        for i in range(vertices):
            self.graph.append([])

    # Adding an edge to the graph
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

# Creating a simple graph
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

# Printing the adjacency list
for i in range(g.V):
    print(f"Vertex {i}: {g.graph[i]}")

With these basics in place, you're now ready to dive deeper into the world of graph algorithms! Stay tuned for our upcoming lessons on Graph Traversals, Shortest Paths, and more. Happy learning! 🚀