Graph Algorithms
Graph algorithms are the algorithms used to solve problems on graphs. These algorithms help in finding shortest paths, minimum spanning trees, and various other properties of graphs.
Here are some common graph algorithms:
Dijkstra's Algorithm: This algorithm finds the shortest path between two vertices in a graph. It works for both weighted and unweighted graphs.
Kruskal's Algorithm: This algorithm finds the minimum spanning tree of a graph. It selects edges in increasing order of their weights and adds them to the spanning tree without creating a cycle.
You can implement these algorithms in C++ using various data structures and algorithms. Here's an example of how you can implement Dijkstra's algorithm:
TEXT/X-C++SRC
1#include <iostream>
2#include <limits>
3#include <vector>
4using namespace std;
5
6const int INF = INT_MAX;
7
8// Function to implement Dijkstra's algorithm
9vector<int> dijkstra(vector<vector<pair<int, int>>>&graph, int start) {
10 int n = graph.size();
11 vector<int> distance(n, INF);
12 vector<bool> visited(n, false);
13
14 distance[start] = 0;
15
16 for (int i = 0; i < n; i++) {
17 int minDistance = INF;
18 int u;
19
20 // Find the vertex with the minimum distance
21 for (int j = 0; j < n; j++) {
22 if (!visited[j] && distance[j] < minDistance) {
23 minDistance = distance[j];
24 u = j;
25 }
26 }
27
28 visited[u] = true;
29
30 // Update the distance of adjacent vertices
31 for (auto edge : graph[u]) {
32 int v = edge.first;
33 int weight = edge.second;
34
35 if (!visited[v] && distance[u] + weight < distance[v]) {
36 distance[v] = distance[u] + weight;
37 }
38 }
39 }
40
41 return distance;
42}
43
44int main() {
45 // Create a graph
46 vector<vector<pair<int, int>>> graph = {
47 {{1, 4}, {2, 1}},
48 {{3, 3}},
49 {},
50 {{2, 2}},
51 };
52
53 // Find the shortest distances from vertex 0
54 vector<int> shortestDistances = dijkstra(graph, 0);
55
56 // Print the shortest distances
57 for (int i = 0; i < shortestDistances.size(); i++) {
58 cout << "Shortest distance from vertex 0 to vertex " << i << ": " << shortestDistances[i] << endl;
59 }
60
61 return 0;
62}