Graph Representation

Graphs can be represented in memory using different data structures. One common representation is the adjacency matrix.

An adjacency matrix is a two-dimensional array that represents a graph. Each element in the array signifies the presence or absence of an edge between two vertices. In an undirected graph, the adjacency matrix is symmetric, meaning matrix[i][j] is equal to matrix[j][i].

Let's take a look at an example of representing a graph using an adjacency matrix in Python:

1if __name__ == '__main__':
2    class AdjacencyMatrixGraph:
3        def __init__(self, num_vertices):
4            self.num_vertices = num_vertices
5            self.graph = [[0] * num_vertices for _ in range(num_vertices)]
6
7        def add_edge(self, source, destination):
8            if source < self.num_vertices and destination < self.num_vertices:
9                self.graph[source][destination] = 1
10                self.graph[destination][source] = 1
11
12    # Create an adjacency matrix graph with 4 vertices
13    amg = AdjacencyMatrixGraph(4)
14
15    # Add edges to the graph
16    amg.add_edge(0, 1)
17    amg.add_edge(1, 2)
18    amg.add_edge(2, 3)
19
20    # Print the adjacency matrix
21    for row in amg.graph:
22        print(row)

In the above example, we define a AdjacencyMatrixGraph class that initializes an empty matrix with num_vertices rows and columns. The add_edge method allows us to add edges between vertices by setting the corresponding matrix values to 1. Finally, we print the adjacency matrix to visualize the graph.

The adjacency matrix representation is useful when the graph is dense and the number of vertices is relatively small. However, it requires a lot of memory when the graph is sparse or when the number of vertices is large. In such cases, alternative representations like adjacency list or edge list may be more efficient.

Understanding the different graph representations is essential when working with algorithms that operate on graphs. Each representation has its own advantages and trade-offs, and the choice depends on the specific requirements and constraints of the problem at hand.

xxxxxxxxxx

if __name__ == '__main__':

    class AdjacencyMatrixGraph:

        def __init__(self, num_vertices):

            self.num_vertices = num_vertices

            self.graph = [[0] * num_vertices for _ in range(num_vertices)]

​

        def add_edge(self, source, destination):

            if source < self.num_vertices and destination < self.num_vertices:

                self.graph[source][destination] = 1

                self.graph[destination][source] = 1

​

    # Create an adjacency matrix graph with 4 vertices

    amg = AdjacencyMatrixGraph(4)

​

    # Add edges to the graph

    amg.add_edge(0, 1)

    amg.add_edge(1, 2)

    amg.add_edge(2, 3)

​

    # Print the adjacency matrix

    for row in amg.graph:

        print(row)