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.
Here is the listing of Python programming examples on Graphs:
- Python Programs on Graph
- Python Programs on Shortest Path Algorithms
- Python Programs on Minimum Spanning Tree
- Python Programs on Bipartite Graph
- Python Programs on BFS Graph
- 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 |
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 |