1. Introduction to Operations on Graphs
Graph theory, a fundamental part of computer science and mathematics, has seen its applications spread across diverse fields ranging from communications networks, social media, bioinformatics, to transportation systems. The concept of operations on graphs lies at the core of these applications, forming the backbone of the structural and algorithmic properties of graphs.
2. Fundamentals of Graph
A graph is a non-linear data structure consisting of nodes (vertices) and edges. The edges may be directed (digraphs) or undirected, and may carry weights. Operations on graphs are manipulations that allow us to extract meaningful conclusions from these structures.
3. Primary Operations on Graphs
3.1 Traversals
Graph traversal involves visiting each node in a graph in a systematic way. The two most common traversal methods are Depth First Search (DFS) and Breadth First Search (BFS).
3.1.1 Depth First Search (DFS)
The DFS traversal visits vertices as far ahead as possible along each branch before backtracking. It can be implemented using a stack data structure.
void DFS(int v, bool visited[], list<int> adj[]) {
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i, visited, adj);
}
3.1.2 Breadth First Search (BFS)
The BFS traversal visits all vertices at the current depth before moving on to vertices at the next depth level. It can be implemented using a queue data structure.
void BFS(int v, bool visited[], list<int> adj[]) {
list<int> queue;
visited[v] = true;
queue.push_back(v);
while(!queue.empty())
{
v = queue.front();
cout << v << " ";
queue.pop_front();
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
{
if (!visited[*i])
{
queue.push_back(*i);
visited[*i] = true;
}
}
}
}
3.2 Path Finding
Path finding algorithms help determine the shortest path between two vertices in a graph. Some of the notable path finding algorithms are Dijkstra's algorithm and the Bellman-Ford algorithm.
3.2.1 Dijkstra's Algorithm
Dijkstra's algorithm is used for finding the shortest paths from a single source vertex to all other vertices in a graph. The graph can't contain any edges with negative weight.
void dijkstra(vector<vector<int>>& adj, int src, int V) {
priority_queue< pair<int,int>, vector >, greater> > pq;
vector<int> dist(V, INT_MAX);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
for (auto x : adj[u])
{
int v = x.first;
int weight = x.second;
if (dist[v] > dist[u] + weight)
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
printSolution(dist, V);
}
3.2.2 Bellman-Ford Algorithm
Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights.
void bellmanFord(vector<vector<int>>& adj, int src, int V) {
vector<int> dist(V, INT_MAX);
dist[src] = 0;
for (int i=1; i<=V-1; i++)
{
for (auto edge : adj)
{
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
printSolution(dist, V);
}
3.3 Topological Sorting
Topological Sorting is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering. It can only be performed on directed acyclic graphs (DAGs).
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack, list<int> adj[]) {
visited[v] = true;
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack, adj);
Stack.push(v);
}
void topologicalSort(list<int> adj[], int V) {
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack, adj);
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
3.4 Minimum Spanning Tree
A minimum spanning tree (MST) for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree. Notable algorithms for finding the MST are Prim's algorithm and Kruskal's algorithm.
3.4.1 Prim's Algorithm
Prim's algorithm builds the spanning tree by adding the nearest vertex to the built tree. It starts with an arbitrary node, then expands the tree by adding the minimum-weight edge that connects the tree to nodes not yet in the tree.
void primMST(vector<vector<int>>& adj, int V) {
vector
<int> parent(V);
vector<int> key(V, INT_MAX);
vector<bool> mstSet(V, false);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet, V);
mstSet[u] = true;
for (auto v : adj[u])
if (mstSet[v.first] == false && v.second < key[v.first])
key[v.first] = v.second, parent[v.first] = u;
}
printMST(parent, V, adj);
}
3.4.2 Kruskal's Algorithm
Kruskal's algorithm builds the spanning tree by adding the lowest-cost edge that connects any two trees in the forest. It treats each node as an independent tree and connects one with another only if it has the lowest cost among all available options.
void KruskalMST(vector<vector<int>>& adj, int V) {
sort(adj.begin(), adj.end());
vector<int> parent(V);
for (int i = 0; i < V; i++)
parent[i] = i;
vector<vector<int>> mst;
for (auto u : adj)
{
int v = u[0], w = u[1], weight = u[2];
if (find(v, parent) != find(w, parent))
{
mst.push_back({v, w, weight});
union(v, w, parent);
}
}
printMST(mst);
}
4. Conclusion
From data analytics to network routing, operations on graphs unlock a wealth of possibilities. Grasping these fundamental operations provides a solid foundation for more complex graph-related tasks. Indeed, the sky is the limit when it comes to the innovative applications and further potential for optimization of these operations.
5. Onwards to Greener Pastures: Dynamic Graph Algorithms
Graphs aren't always static. With constantly changing vertices and edges, dynamic graphs are the real-world standard. Next, we'll delve into the dynamic world of graphs, exploring efficient algorithms and data structures that handle the ever-changing nature of practical applications. Ready for the dynamic ride?