## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# DSA Graphs Implementation

## A Basic Graph Implementation

Before we can run algorithms on a Graph, we must first implement it somehow.

To implement a Graph we will use an Adjacency Matrix, like the one below.

To store data for each vertex, in this case the letters A, B, C, and D, the data is put in a separate array that matches the indexes in the adjacency matrix, like this:

``vertexData = [ 'A', 'B', 'C', 'D']``

For an undirected and not weighted Graph, like in the image above, an edge between vertices `i` and `j` is stored with value `1`. It is stored as `1` on both places `(j,i)` and `(i,j)` because the edge goes in both directions. As you can see, the matrix becomes diagonally symmetric for such undirected Graphs.

Let's look at something more specific. In the adjacency matrix above, vertex A is on index `0`, and vertex D is on index `3`, so we get the edge between A and D stored as value `1` in position `(0,3)` and `(3,0)`, because the edge goes in both directions.

Below is a basic implementation of the undirected Graph from the image above.

### Example

Python:

``````vertexData = ['A', 'B', 'C', 'D']

[0, 1, 1, 1],  # Edges for A
[1, 0, 1, 0],  # Edges for B
[1, 1, 0, 0],  # Edges for C
[1, 0, 0, 0]   # Edges for D
]

for row in matrix:
print(row)

print('vertexData:',vertexData)
Run Example »

This implementation is basically just a two dimensional array, but to get a better sense of how the vertices are connected by edges in the Graph we have just implemented, we can run this function:

### Example

Python:

``````def print_connections(matrix, vertices):
print("\nConnections for each vertex:")
for i in range(len(vertices)):
print(f"{vertices[i]}: ", end="")
for j in range(len(vertices)):
if matrix[i][j]:  # if there is a connection
print(vertices[j], end=" ")
print()  # new line``````
Run Example »

## Graph Implementation Using Classes

A more proper way to store a Graph is to add an abstraction layer using classes so that a Graph's vertices, edges, and relevant methods, like algorithms that we will implement later, are contained in one place.

Programming languages with built-in object-oriented functionality like Python and Java, make implementation of Graphs using classes much easier than languages like C, without this built-in functionality.

Here is how the undirected Graph above can be implemented using classes.

### Example

Python:

``````class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size

if 0 <= u < self.size and 0 <= v < self.size:

if 0 <= vertex < self.size:
self.vertex_data[vertex] = data

def print_graph(self):
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

g = Graph(4)
g.add_edge(0, 1)  # A - B
g.add_edge(0, 2)  # A - C
g.add_edge(0, 3)  # A - D
g.add_edge(1, 2)  # B - C

g.print_graph()``````
Run Example »

In the code above, the matrix symmetry we get for undirected Graphs is provided for on line 9 and 10, and this saves us some code when initializing the edges in the Graph on lines 29-32.

## Implementation of Directed and Weighted Graphs

To implement a Graph that is directed and weighted, we just need to do a few changes to previous implementation of the undirected Graph.

To create directed Graphs, we just need to remove line 10 in the previous example code, so that the matrix is not automatically symmetric anymore.

The second change we need to do is to add a `weight` argument to the `add_edge()` method, so that instead of just having value `1` to indicate that there is an edge between two vertices, we use the actual weight value to define the edge.

Below is the implementation of the directed and weighted Graph above.

### Example

Python:

``````class Graph:
def __init__(self, size):
self.adj_matrix = [[None] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size

if 0 <= u < self.size and 0 <= v < self.size:

if 0 <= vertex < self.size:
self.vertex_data[vertex] = data

def print_graph(self):
print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

g = Graph(4)
g.add_edge(0, 1, 3)  # A -> B with weight 3
g.add_edge(0, 2, 2)  # A -> C with weight 2
g.add_edge(3, 0, 4)  # D -> A with weight 4
g.add_edge(2, 1, 1)  # C -> B with weight 1

g.print_graph()``````
Run Example »

Line 3: All edges are set to `None` initially.

Line 7: The weight can now be added to an edge with the additional `weight` argument.

Line 10: By removing line 10, the Graph can now be set up as being directed.

On the next page we will see how Graphs can be traversed, and on the next pages after that we will look at different algorithms that can run on the Graph data structure.

## Exercise:

How are the edges in a graph implemented?

```The edges, and edge weights,
in a graph are normally
implemented in an  matrix.
```

Start the Exercise

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com