We use an unordered_map to store nodes and their neighbors with edge weights.
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class Graph {
// adjacency list: map<node, list<pair<neighbor, weight>>>
unordered_map<string, list<pair<string, int>>> adj;
public:
void addEdge(string u, string v, int weight, bool directed = false) {
adj[u].push_back({v, weight});
if (!directed) {
adj[v].push_back({u, weight});
}
}
};
BFS uses a Queue to explore neighbors level by level. Ideal for unweighted shortest paths.
#include <queue>
#include <set>
void bfs(string startNode) {
queue<string> q;
set<string> visited;
q.push(startNode);
visited.insert(startNode);
while (!q.empty()) {
string curr = q.front();
q.pop();
cout << curr << " ";
for (auto neighbor : adj[curr]) {
if (visited.find(neighbor.first) == visited.end()) {
visited.insert(neighbor.first);
q.push(neighbor.first);
}
}
}
}
Finding the shortest path in a weighted graph using a Priority Queue.
#include <map>
void dijkstra(string start) {
map<string, int> dist;
for(auto const& [node, neighbors] : adj) dist[node] = 1e9;
dist[start] = 0;
set<pair<int, string>> pq;
pq.insert({0, start});
while(!pq.empty()){
auto top = *(pq.begin());
string curr = top.second;
int d = top.first;
pq.erase(pq.begin());
for(auto neighbor : adj[curr]){
if(d + neighbor.second < dist[neighbor.first]){
pq.erase({dist[neighbor.first], neighbor.first});
dist[neighbor.first] = d + neighbor.second;
pq.insert({dist[neighbor.first], neighbor.first});
}
}
}
}
DFS explores as far as possible along each branch before backtracking. It uses Recursion (which internally uses a Stack).
#include <set>
// Helper function for recursion
void dfsHelper(string node, set<string>& visited) {
// Mark the current node as visited
visited.insert(node);
cout << node << " ";
// Recur for all the neighbors
for (auto neighbor : adj[node]) {
if (visited.find(neighbor.first) == visited.end()) {
dfsHelper(neighbor.first, visited);
}
}
}
void dfs(string startNode) {
set<string> visited;
dfsHelper(startNode, visited);
}