Graph Representation in Computers

Introduction

• Discussion on representing graphs in computers.
• Focus on two popular methods:
  1. Adjacency Matrix
  2. Adjacency List

Adjacency Matrix

• Definition: An n x n matrix where n is the number of vertices.
• Example: For a graph with 5 vertices, it results in a 5 x 5 matrix.

Filling the Adjacency Matrix

• Diagonal elements represent loops (self-connections).
• Element a[i][j] = 1 if there is an edge between vertex i and vertex j; otherwise, it is 0.
• For an undirected graph, both a[i][j] and a[j][i] are set to 1.

Time and Space Complexity

• Space complexity: Θ(n²) because of the n x n matrix.

Adjacency List

• Definition: A collection of linked lists, where each list corresponds to a vertex and contains its adjacent vertices.
• Example with 5 vertices: Each vertex has its own linked list.

Filling the Adjacency List

• Each list contains all nodes connected to the corresponding vertex.
• Edges are represented twice (for undirected graphs).

Time and Space Complexity

• Space complexity: Θ(n + 2e), where e is the number of edges.

When to Use Each Representation

• Adjacency Matrix:
  • Better for dense graphs (many edges) where almost all nodes are inter-connected.
• Adjacency List:
  • Preferred for sparse graphs (few edges) where there are fewer connections between nodes.

Conclusion

• Recap of the two methods of graph representation.
• Acknowledgment that other methods exist but focus is on these two.
• Reminder about the importance of choosing the right representation based on graph density.

Notes

• These methods are foundational and widely used in computer science for graph representation.

Next Steps

• Look forward to future discussions on graph algorithms and applications.

Closing

• Instructor will see students in the next session.
• Encouragement to reach out with questions.