Graph Algorithms in C++
Introduction to Graphs
A graph is a data structure that consists of a set of nodes (or vertices) and a set of edges that connect pairs of nodes. Graphs are used to model relationships between objects, such as the connections between cities in a map or the links between web pages.
Example of a simple undirected graph:
A -- B
| |
C -- D
Graph Representation
Graphs can be represented in several ways. The two most common representations are:
- Adjacency Matrix
- Adjacency List
Adjacency Matrix
An adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph. If there is an edge between vertex i and vertex j, then the value of the element at row i and column j is 1; otherwise, it is 0.
Example:
Adjacency Matrix for the above graph:
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
Adjacency List
An adjacency list is an array of lists. The size of the array is equal to the number of vertices. Each element of the array is a list that contains the nodes that are adjacent to the corresponding vertex.
Example:
Adjacency List for the above graph:
A: B, C
B: A, D
C: A, D
D: B, C
Breadth-First Search (BFS)
Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node) and explores the neighbor nodes at the present depth level before moving on to nodes at the next depth level.
Algorithm
The BFS algorithm works as follows:
- Start by putting any one of the graph's vertices at the back of a queue.
- Take the front item of the queue and add it to the visited list.
- Create a list of that vertex's adjacent nodes. Add those which are not in the visited list to the back of the queue.
- Keep repeating steps 2 and 3 until the queue is empty.
Example in C++
#include#include #include
using namespace std; // Graph class represents a directed graph using adjacency list representation class Graph { int V; // No. of vertices list *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // Function to add an edge to graph void BFS(int s); // Prints BFS traversal from a given source s }; Graph::Graph(int V) { this->V = V; adj = new list [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::BFS(int s) { // Mark all the vertices as not visited vector visited(V, false); // Create a queue for BFS list queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent vertices of a vertex list ::iterator i; while (!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << " "; queue.pop_front(); // Get all adjacent vertices of the dequeued vertex s // If an adjacent has not been visited, then mark it // visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Breadth First Traversal (starting from vertex 2) \n"; g.BFS(2); return 0; }
Depth-First Search (DFS)
Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
Algorithm
The DFS algorithm works as follows:
- Start by putting any one of the graph's vertices on top of a stack.
- Take the top item of the stack and add it to the visited list.
- Create a list of that vertex's adjacent nodes. Add those which are not in the visited list to the top of the stack.
- Keep repeating steps 2 and 3 until the stack is empty.
Example in C++
#include#include #include
using namespace std; class Graph { int V; // No. of vertices list *adj; // Pointer to an array containing adjacency lists void DFSUtil(int v, vector &visited); // A function used by DFS public: Graph(int V); // Constructor void addEdge(int v, int w); // Function to add an edge to graph void DFS(int v); // DFS traversal of the vertices reachable from v }; Graph::Graph(int V) { this->V = V; adj = new list [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::DFSUtil(int v, vector &visited) { // Mark the current node as visited and print it visited[v] = true; cout << v << " "; // Recur for all the vertices adjacent to this vertex list ::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); } void Graph::DFS(int v) { // Mark all the vertices as not visited vector visited(V, false); // Call the recursive helper function to print DFS traversal DFSUtil(v, visited); } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Depth First Traversal (starting from vertex 2) \n"; g.DFS(2); return 0; }
Dijkstra's Algorithm
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It works by assigning a tentative distance value to every node: set it to zero for the initial node and to infinity for all other nodes. Then, it visits the node with the smallest tentative distance, updates the distance values for its neighbors, and repeats until all nodes have been visited.
Algorithm
The Dijkstra's algorithm works as follows:
- Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- While the unvisited set is not empty:
- Select the unvisited node with the smallest tentative distance.
- For the current node, consider all its unvisited neighbors and calculate their tentative distances.
- Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
- When we are done considering all the neighbors of the current node, mark the current node as visited and remove it from the unvisited set.
Example in C++
#include#include #include using namespace std; #define V 9 int minDistance(int dist[], bool sptSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } void printSolution(int dist[]) { cout << "Vertex \t Distance from Source\n"; for (int i = 0; i < V; i++) cout << i << " \t\t " << dist[i] << "\n"; } void dijkstra(int graph[V][V], int src) { int dist[V]; bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } printSolution(dist); } int main() { int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0} }; dijkstra(graph, 0); return 0; }
Conclusion
Graph algorithms are fundamental in the field of computer science and are used in various applications such as network routing, social network analysis, and geographical mapping. Understanding these basic algorithms is crucial for solving complex problems related to graphs and networks.