Graph Algorithms and Priority Queues
(Heaps) - W3Schools Notes
Graph Algorithms
Introduction to Graphs
A Graph is a non-linear data structure that consists of vertices (nodes) and edges.
A vertex, also called a node, is a point or an object in the Graph, and an edge is used to
connect two vertices with each other. * Internet: Can be represented as a Graph, with
web pages as vertices and hyperlinks as edges. * Biology: Graphs can model systems
like neural networks or the spread of diseases.
Graph Properties
Weighted Graph: Edges have values (e.g., distance, capacity, time, probability).
Connected Graph: All vertices are connected through edges. A graph that is not
connected has isolated subgraphs or single isolated vertices.
Directed Graph (Digraph): Edges between vertex pairs have a direction (e.g.,
hierarchy, flow).
Cyclic Graph:
Directed Cyclic: A path along directed edges goes in circles.
Undirected Cyclic: Can return to the starting vertex without using the same
edge more than once.
Loop (Self-loop): An edge that begins and ends on the same vertex.
Graph Representations
Graph representations tell us how a Graph is stored in memory. Different
representations can affect space usage, search/manipulation speed, and suitability for
different graph types.
Adjacency Matrix: A 2D array where (i,j) stores information about the edge
from vertex i to vertex j . Values can represent presence (1) or weight. For
directed graphs, it may not be symmetric. Easy to understand and implement.
* Adjacency List: An array containing all vertices, where each vertex has a Linked
List (or Array) with its edges. More space-efficient for 'sparse' graphs (graphs
where each vertex has edges to a small portion of other vertices).
Graph Traversal
To traverse a Graph means to start in one vertex and go along the edges to visit other
vertices until all, or as many as possible, have been visited. The two most common
ways are Depth First Search (DFS) and Breadth First Search (BFS).
Depth First Search (DFS):
Goes "deep" by visiting a vertex, then an adjacent vertex, and so on.
Distance from the starting vertex increases with each recursive iteration.
Usually implemented using a Stack or recursion (which utilizes the call
stack).
How it works: Start DFS traversal on a vertex. Recursively traverse each
adjacent unvisited vertex.
Breadth First Search (BFS):
Visits all adjacent vertices of a vertex before visiting neighboring vertices to
the adjacent ones. Vertices with the same distance from the starting vertex
are visited first.
Usually implemented using a Queue.
How it works: Put the starting vertex into the queue. For each vertex taken
from the queue, visit it, then put all unvisited adjacent vertices into the
queue. Continue as long as there are vertices in the queue.
Topological Sort
Topological sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices
such that for every directed edge u-v , vertex u comes before v in the ordering.
Topological sorting is not possible if the graph is not a DAG (i.e., it contains cycles or is
undirected).
Why only for DAGs? * Undirected Edges: An undirected edge between u and v
implies both u to v and v to u edges, creating a mutual dependency that prevents a
linear ordering. * Cycles: In a cycle, all vertices are indirectly dependent on each other,
making it impossible to establish a linear order without contradiction.
Topological order may not be unique; multiple valid topological orderings can exist
for a given DAG.
Algorithm for Topological Sorting using DFS: 1. Create a graph with n vertices and
m directed edges. 2. Initialize a stack and a visited array of size n . 3. For each
unvisited vertex in the graph: * Call a DFS function with the vertex as a parameter. * In
the DFS function, mark the vertex as visited and recursively call DFS for all unvisited
neighbors. * Once all neighbors have been visited, push the vertex onto the stack. 4.
After all vertices have been visited, pop elements from the stack and append them to
an output list until the stack is empty. The resulting list is the topologically sorted
order.
Time Complexity: O(V+E) (same as DFS). Auxiliary Space: O(V) (due to the stack).
Topological Sorting Using BFS (Kahn's Algorithm): An alternative algorithm with the
same time complexity.
Advantages of Topological Sort: * Helps in scheduling tasks or events based on
dependencies. * Detects cycles in a directed graph. * Efficient for solving problems
with precedence constraints.
Disadvantages of Topological Sort: * Only applicable to directed acyclic graphs
(DAGs). * May not be unique.
Applications of Topological Sort: * Task scheduling and project management. *
Software deployment tools (e.g., Makefile). * Dependency resolution in package
management systems. * Determining compilation order in software build systems. *
Deadlock detection in operating systems. * Course scheduling in universities. * Finding
shortest paths in weighted directed acyclic graphs.
Shortest-Path Algorithms
The shortest path problem involves finding the shortest possible route or path
between two vertices (or nodes) in a Graph. The 'shortest' path is determined by the
lowest possible combined weight (path cost/weight) along the edges.
Algorithms like Dijkstra's and Bellman-Ford find the shortest path from one starting
vertex to all other vertices. Initially, the distance from the start vertex to all others is set
to infinity. As the algorithms run, edges are repeatedly checked and shorter paths are
found and updated. This process of finding and updating a shorter distance is called
relaxation.
Positive and Negative Edge Weights: * Positive Edge Weights: Some algorithms, like
Dijkstra's, can only find shortest paths in graphs where all edges have positive weights.
These are easier to understand as they can represent real-world distances. * Negative
Edge Weights: Graphs can also have negative edge weights. For such graphs, the
Bellman-Ford algorithm can be used. Negative edge weights can represent scenarios
like earning money instead of losing it.
Negative Cycles in Shortest Path Problems: * Finding shortest paths becomes
impossible if a graph has negative cycles. A negative cycle is a path where you can go
in circles, and the edges in this cycle have a total path weight that is negative. * If a
negative cycle exists, it's always possible to find an even shorter path by traversing the
cycle again, meaning the true shortest distance can never be found. * The Bellman-
Ford algorithm can detect negative cycles.
Minimum Spanning Tree (MST)
A Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-
weighted undirected graph that connects all the vertices together, without any cycles
and with the minimum possible total edge weight.
Prim's Algorithm: * Finds the MST in a connected and undirected graph. * The MST
found by Prim's algorithm is the collection of edges that connects all vertices with a
minimum sum of edge weights. * How it works (Greedy Approach): 1. Choose a
random vertex as the starting point and include it as the first vertex in the MST. 2.
Compare the edges going out from the current MST. Choose the edge with the lowest
weight that connects a vertex within the MST to a vertex outside the MST. 3. Add that
edge and the new vertex to the MST. 4. Repeat steps 2 and 3 until all vertices are
included in the MST. * Note: Since the starting vertex is chosen at random, different
edges might be included in the MST for the same graph, but the total edge weight of
the MST will always be the same minimum value. * For unconnected graphs, Kruskal's
algorithm can be used instead.
Priority Queues (Heaps)
Queues (General)
A queue is a data structure that can hold many elements, operating on a FIFO (First In
First Out) principle, similar to a line in a supermarket. The first element added is the
first one to be removed.
Basic operations: * Enqueue: Adds a new element to the queue. * Dequeue: Removes
and returns the first (front) element from the queue. * Peek: Returns the first element
in the queue without removing it. * isEmpty: Checks if the queue is empty. * Size:
Returns the number of elements in the queue.
Queues can be implemented using arrays or linked lists, each with their own
advantages and disadvantages regarding memory efficiency, dynamic sizing, and
shifting costs.
Binary Heaps
Priority Queues are commonly implemented using trees, such as binary heaps.
Binary Trees: Each node has up to two children, a left child node and a right child
node. This structure is the foundation for more complex tree types like Binary Search
Trees and AVL Trees.
D-Heaps
A d-ary heap or d-heap is a generalization of the binary heap where each node can
have d children instead of just 2. A binary heap is a special case of a d-heap where
d=2 .
Key characteristics: * Structure: Like binary heaps, d-heaps are complete d-ary trees,
meaning all levels are fully filled except possibly the last, which is filled from left to
right. * Heap Property: They maintain the heap property (min-heap or max-heap),
where the value of a parent node is always less than or equal to (for min-heap) or
greater than or equal to (for max-heap) the values of its children. * Advantages: D-
heaps can be more efficient than binary heaps in certain scenarios, particularly when
d is chosen optimally. For example, in Dijkstra's algorithm, a d-heap can offer
performance improvements over a binary heap, especially for dense graphs. The
height of a d-heap is log_d(n) , which is smaller than log_2(n) for a binary heap,
leading to fewer comparisons in some operations. * Applications: Used in priority
queues, graph algorithms (like Dijkstra's), and other areas where efficient retrieval of
minimum or maximum elements is crucial.
Dijkstra's Algorithm
Purpose: Finds the shortest path from a single source vertex to all other vertices
in a graph with non-negative edge weights.
Working Principle: It operates by iteratively selecting the unvisited vertex with
the smallest known distance from the source and updating the distances of its
neighbors. It uses a greedy approach.
Steps (High-level):
1. Initialize distances: Set the distance to the source vertex as 0 and all other
vertices as infinity.
2. Maintain a set of visited vertices and a priority queue (or similar structure)
of unvisited vertices, ordered by their current shortest distance.
3. While there are unvisited vertices: a. Extract the unvisited vertex u with the
smallest distance. b. Mark u as visited. c. For each neighbor v of u : i. If the
path from the source to v through u is shorter than the current known
distance to v , update v 's distance.
Bellman-Ford Algorithm
Purpose: Finds the shortest path from a single source vertex to all other vertices
in a graph that can have negative edge weights. It can also detect negative
cycles.
Working Principle: It relaxes all edges V-1 times (where V is the number of
vertices). In each iteration, it checks if a shorter path to a vertex can be found by
going through one of its incoming edges. If, after V-1 iterations, a further
relaxation is possible, it indicates the presence of a negative cycle.
Steps (High-level):
1. Initialize distances: Set the distance to the source vertex as 0 and all other
vertices as infinity.
2. Repeat V-1 times: a. For each edge (u, v) with weight w : i. If
distance[u] + w < distance[v] , then update distance[v] =
distance[u] + w .
3. Check for negative cycles: Iterate through all edges one more time. If any
distance can still be reduced, a negative cycle exists.
Kruskal's Algorithm
Purpose: Finds the Minimum Spanning Tree (MST) in an undirected, weighted
graph.
Working Principle: It's a greedy algorithm that builds the MST by adding edges
in increasing order of their weights, as long as adding the edge does not form a
cycle.
Steps (High-level):
1. Sort all edges in the graph in non-decreasing order of their weights.
2. Initialize an empty MST (a forest where each vertex is its own component).
3. Iterate through the sorted edges: a. For each edge (u, v) : i. If u and v are
not already in the same component (i.e., adding this edge does not form a
cycle), add the edge to the MST and merge the components of u and v .
4. Continue until V-1 edges have been added to the MST (where V is the
number of vertices), or all edges have been considered.
Data Structure: Typically uses a Disjoint Set Union (DSU) data structure to
efficiently check for cycles and merge components.