Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E).
Graph Basics
Graph Algorithms
Graph algorithms are methods used to manipulate and analyze graphs, solving various range of problems like finding the shortest path, cycles detection.
BFS and DFS
1. Breadth First Search:
Breadth First Search (BFS) is a fundamental graph traversal algorithm. It begins with a node, then first traverses all its adjacent nodes. Once all adjacent are visited, then their adjacent are traversed.
- BFS is different from DFS in a way that closest vertices are visited before others. We mainly traverse vertices level by level.
- Popular graph algorithms like Dijkstra’s shortest path, Kahn’s Algorithm, and Prim’s algorithm are based on BFS.
- BFS itself can be used to detect cycle in a directed and undirected graph, find shortest path in an unweighted graph and many more problems.
Explore in detail about Breadth First Search in Python
2. Depth First Search:
In Depth First Search (or DFS) for a graph, we traverse all adjacent vertices one by one. When we traverse an adjacent vertex, we completely finish the traversal of all vertices reachable through that adjacent vertex. This is similar to a tree, where we first completely traverse the left subtree and then move to the right subtree. The key difference is that, unlike trees, graphs may contain cycles (a node may be visited more than once). To avoid processing a node multiple times, we use a boolean visited array.
Explore in detail about Depth First Search in Python
Shortest Path
1. Dijkstra’s shortest path algorithm:
Dijkstra’s algorithm finds the shortest path between nodes in a graph. It starts from a chosen node and explores the shortest known distance to other nodes, updating as it finds better paths. It keeps track of visited nodes to avoid unnecessary checks. The process continues until the shortest path to all nodes is found. It works well for graphs with non-negative weights, like road maps and network routing.
Explore in detail about Dijkstra’s shortest path algorithm in Python
2. Bellman–Ford Algorithm:
The Bellman-Ford algorithm finds the shortest path from a starting node to all other nodes in a graph. It works by repeatedly updating distances for all edges, allowing it to handle graphs with negative weights. Unlike Dijkstra’s algorithm, it can detect negative weight cycles. It is useful for routing and network analysis but slower than Dijkstra’s for large graphs.
Explore in detail about Bellman–Ford Algorithm in Python
3. Floyd Warshall Algorithm:
The Floyd Warshall Algorithm is an all-pair shortest path algorithm that uses Dynamic Programming to find the shortest distances between every pair of vertices in a graph, unlike Dijkstra and Bellman-Ford which are single source shortest path algorithms. This algorithm works for both the directed and undirected weighted graphs and can handle graphs with both positive and negative weight edges.
Explore in detail about Floyd Warshall Algorithm in Python
Minimum Spanning Tree
1. Prim's Algorithm:
Prim’s algorithm is a Greedy algorithm. This algorithm always starts with a single node and moves through several adjacent nodes, in order to explore all of the connected edges along the way.
- The algorithm starts with an empty spanning tree.
- The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, and the other set contains the vertices not yet included.
- At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
Explore in detail about Prim's Algorithm in Python
2. Kruskal's Algorithm:
Kruskal’s algorithm finds the Minimum Spanning Tree (MST) of a graph, which connects all nodes with the least total edge weight. It sorts all edges by weight and adds the smallest edge to the MST, ensuring no cycles form. This continues until all nodes are connected. It is useful for network design, like laying cables or roads with minimal cost.
Explore in detail about Kruskal’s Algorithm in Python
Topological Sorting
1. Topological Sorting:
Topological sorting is used to arrange directed acyclic graph (DAG) nodes in a sequence where each node appears before the nodes it points to. It is mainly used in task scheduling, dependency resolution, and course prerequisites.
Explore in detail about Topological Sorting in Python
2. Kahn’s algorithm:
Kahn’s Algorithm for Topological Sorting is a method used to order the vertices of a directed graph in a linear order such that for every directed edge from vertex A to vertex B, A comes before B in the order. The algorithm works by repeatedly finding vertices with no incoming edges, removing them from the graph, and updating the incoming edges of the remaining vertices. This process continues until all vertices have been ordered.
Explore in detail about Kahn's Algorithm in Python
Maximum Flow in Graph
1. Maximum Flow Problem:
The maximum flow problem is a classic optimization problem in network theory, where the goal is to determine the maximum possible flow from a source node to a sink node in a flow network. A flow network is represented as a directed graph with each edge having a capacity, which is the maximum amount of flow that can pass through it. The problem finds applications in various fields such as computer networks, logistics, and transportation systems.
Explore in detail about Maximum Flow Problem in Python
2. Ford-Fulkerson Algorithm:
The Ford-Fulkerson algorithm is a widely used algorithm to solve the maximum flow problem in a flow network. The maximum flow problem involves determining the maximum amount of flow that can be sent from a source vertex to a sink vertex in a directed weighted graph, subject to capacity constraints on the edges.
The algorithm works by iteratively finding an augmenting path, which is a path from the source to the sink in the residual graph, i.e., the graph obtained by subtracting the current flow from the capacity of each edge. The algorithm then increases the flow along this path by the maximum possible amount, which is the minimum capacity of the edges along the path.
Explore in detail about Ford-Fulkerson Algorithm in Python
Similar Reads
Python Glossary
Python is a beginner-friendly programming language, widely used for web development, data analysis, automation and more. Whether you're new to coding or need a quick reference, this glossary provides clear, easy-to-understand definitions of essential Python terms—listed alphabetically for quick acce
5 min read
Python Program for Detect Cycle in a Directed Graph
Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true. Recomme
2 min read
Python Program for Detect Cycle in Graph using DSU
Prerequisite: Introduction to Disjoint Set Given an undirected graph, The task is to detect if there is a cycle in the given graph. Example: Input:Â N = 4, E = 4Â Output: Yes Explanation: The diagram clearly shows a cycle 0 to 2 to 1 to 0 Input: N = 4, E = 3 Output: No Explanation: There is no cycle
4 min read
Python Tutorial | Learn Python Programming Language
Python Tutorial – Python is one of the most popular programming languages. It’s simple to use, packed with features and supported by a wide range of libraries and frameworks. Its clean syntax makes it beginner-friendly. Python is: A high-level language, used in web development, data science, automat
10 min read
Python Fundamentals Coding Practice Problems
Welcome to this article on Python basic problems, featuring essential exercises on coding, number swapping, type conversion, conditional statements, loops and more. These problems help beginners build a strong foundation in Python fundamentals and problem-solving skills. Let’s start coding! Python B
1 min read
Plot multiple separate graphs for same data from one Python script
It is very easy to plot different kinds of maps and plots of different data using Python. One such useful library in Python is Matplotlib which is very useful for creating different types of plots using the same data. The easiest way to install Matplotlib is by using the pip command in the command-l
6 min read
Python | Visualizing O(n) using Python
Introduction Algorithm complexity can be a difficult concept to grasp, even presented with compelling mathematical arguments. This article presents a tiny Python program that shows the relative complexity of several typical functions. It can be easily adapted to other functions. Complexity. Why it m
3 min read
Output of Python programs | Set 9 (Dictionary)
Prerequisite: Dictionary 1) What is the output of the following program? [GFGTABS] Python dictionary = {'GFG' : 'geeksforgeeks.org', 'google' : 'google.com', 'facebook' : 'facebook.com' } del dictionary['google']; for key, values in dictionary.
3 min read
Python for Kids - Fun Tutorial to Learn Python Programming
Python for Kids - Python is an easy-to-understand and good-to-start programming language. In this Python tutorial for kids or beginners, you will learn Python and know why it is a perfect fit for kids to start. Whether the child is interested in building simple games, creating art, or solving puzzle
15+ min read
Python Program for Depth First Search or DFS for a Graph
Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a Boolean visited array. A graph can have more than one DFS tr
4 min read