Python Programs on Graphs

Python Programming Examples - Graphs

In Python programming, a graph data structure represents a collection of interlinked objects. Every object is called the vertex, and the link is termed as edge. The basic operations we can perform on graphs are displaying graph vertices, displaying graph edges, adding a vertex, adding an edge, and creating a graph. Graphs can be easily represented using Python dictionary data types and are also used to solve many real-world problems.

Types of Graphs:

Various graphs are created using weights, direction, interconnectivity, and special properties. The most commonly used graphs are:

  • Undirected Graphs: An undirected graph consists of a set of nodes and links connecting them. Here, the edges have no path or direction.
  • Directed Graphs: A directed graph, also called a digraph, is a graph in which the edges have a direction.
  • Weighted Graphs: A weighted graph is a graph with edges labeled by numbers.
  • Unweighted Graphs: Vertices and edges define an unweighted undirected graph.
  • Complete Graphs: Complete graphs have a unique edge between each pair of vertices.
  • Directed Acyclic Graphs: A directed acyclic graph (DAG) is a directed graph that does not include any directed cycles.

Applications of Graphs:

  • Google Maps use graphs to create transportation systems.
  • Users on Facebook are referred to as vertices, and if they are friends, there is an edge linking them. This is an example of an undirected graph.
  • Web pages are referred to as vertices on the World Wide Web.

The following section contains Python programs on graphs, shortest path algorithms, bipartite graphs, BFS and DFS graphs. Each sample program includes a program description, Python code, and program output. All examples have been compiled and tested on Windows and Linux systems.

advertisement
advertisement

Here is the listing of Python programming examples on Graphs:

  1. Python Programs on Graph
  2. Python Programs on Shortest Path Algorithms
  3. Python Programs on Minimum Spanning Tree
  4. Python Programs on Bipartite Graph
  5. Python Programs on BFS Graph
  6. Python Programs on DFS Graph

1. Python Programs on Graph

Program Description
Graph Data Structure in Python Python Program to Implement Graph
Check if Undirected Graph is Connected BFS in Python Python Program to Check the Connectivity of Undirected Graph Using BFS
Check if Undirected Graph is Connected DFS in Python Python Program to Check the Connectivity of Undirected Graph Using DFS
Topological Sort of a DAG using DFS in Python Python Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Transitive Closure of a Graph in Python Python Program to Find the Transitive Closure of a Graph

2. Python Programs on Shortest Path Algorithms

Program Description
Dijkstra’s Shortest Path Algorithm in Python Python Program to Implement Dijkstra’s Shortest Path Algorithm
Bellmanford Algorithm in Python Python Program to Implement Bellman Ford Algorithm
Floyd Warshall Algorithm in Python Python Program to Implement Floyd Warshall Algorithm
Find Shortest Path using BFS in Unweighted Graph in Python Python Program to Find Shortest Path using BFS in Unweighted Graph
Johnson’s Algorithm in Python Python Program to Implement Johnson’s Algorithm

3. Python Programs on Minimum Spanning Tree

Program Description
MST using Kruskal’s Algorithm in Python Python Program to Find Minimum Spanning Tree using Kruskal’s Algorithm
MST using Prim’s Algorithm in Python Python Program to Find Minimum Spanning Tree using Prim’s Algorithm

4. Python Programs on Bipartite Graph

Program Description
Check if Undirected Graph is Bipartite using BFS in Python Python Program to Check if Undirected Graph is Bipartite using BFS
Check if Undirected Graph is Bipartite using DFS in Python Python Program to Check if Undirected Graph is Bipartite using DFS

advertisement

5. Python Programs on BFS Graph

Program Description
Breadth First Search on a Graph in Python Python Program to Implement Breadth-First Search on a Graph
Detect Cycle in Undirected Graph using BFS in Python Python Program to Detect Cycle in Undirected Graph using BFS
Find All Reachable Nodes in Graph using BFS in Python Python Program to Find All Reachable Nodes in a Graph using BFS

6. Python Programs on DFS Graph

Program Description
DFS for a Graph in Python Python Program to Print DFS for a Graph
DFS Graph using Recursion in Python Python Program to Implement Depth First Search on a Graph using Recursion
DFS Graph without Recursion in Python Python Program to Implement Depth First Search on a Graph without Recursion
Detect Cycle in Directed Graph using DFS in Python Python Program to Find if Directed Graph contains Cycle using DFS
Detect Cycle in Undirected Graph using DFS in Python Python Program to Find if Undirected Graph contains Cycle using DFS
Find All Reachable Nodes in Graph using DFS in Python Python Program to Find All Reachable Nodes in a Graph using DFS

advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.