# Data Structure – codewindow.in

## Related Topics ## Data Structure

#### Here's an example of an adjacency matrix for an undirected graph with four vertices:

``````    0  1  2  3
-------------
0 | 0  1  1  0
1 | 1  0  1  1
2 | 1  1  0  1
3 | 0  1  1  0
``````

#### Here’s an example of an adjacency list for the same graph as above:

``````0 -> [1, 2]
1 -> [0, 2, 3]
2 -> [0, 1, 3]
3 -> [1, 2]
``````

#### Here's a Python implementation of the above algorithm:

``````from collections import deque

def topological_sort(graph):
# Step 1
topological_order = []

# Step 2
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1

# Step 3
source_nodes = deque([node for node in in_degree if in_degree[node] == 0])

# Step 4-7
while source_nodes:
node = source_nodes.popleft()
topological_order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
source_nodes.append(neighbor)

# Step 8
if len(topological_order) != len(graph):
raise ValueError("Graph contains a cycle")
``````

#### These are just a few examples of the many applications of graphs in computer science and software engineering. #### Questions on Chapter 10  #### Questions on Chapter 11  ## We Loveto Support you

Go through our study material. Your Job is awaiting.