Data Structure and Algorithm - Graph

1. Graph Definition

A graph is a collection of vertices (also known as nodes) and edges, where each edge connects two vertices. It is a mathematical structure that is commonly used to model relationships between objects. Graphs can be represented visually as diagrams or as a set of data structures in computer science.

In a directed graph, each edge has a direction and is represented by an arrow that points from one vertex to another. In an undirected graph, edges have no direction and are simply represented as lines connecting vertices.

Graphs can be used to model a wide range of real-world situations, including social networks, transportation networks, electrical circuits, and more. They are an important concept in mathematics, computer science, and various other fields.

2. Storage of Graph

2.1 Adjacency Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;

// Define the number of vertices in the graph
const int V = 5;

int main() {
    // Initialize the adjacency matrix with zeros
    int adj_matrix[V][V] = {0};

    // Add edges to the graph
    int edges[][2] = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
    int num_edges = sizeof(edges)/sizeof(edges[0]);
    for (int i = 0; i < num_edges; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }

    // Print the adjacency matrix
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

2.2 Adjacency List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <list>
using namespace std;

// Define the number of vertices in the graph
const int V = 5;

int main() {
    // Initialize the adjacency list with empty lists
    list<int> adj_list[V];

    // Add edges to the graph
    int edges[][2] = {{0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}};
    int num_edges = sizeof(edges)/sizeof(edges[0]);
    for (int i = 0; i < num_edges; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    // Print the adjacency list
    for (int i = 0; i < V; i++) {
        cout << "Vertex " << i << " is adjacent to: ";
        for (int j : adj_list[i]) {
            cout << j << " ";
        }
        cout << endl;
    }

    return 0;
}

3. Graph Traversal

3.1 Depth First Search (DFS)

1
2
3
4
5
6
7
8
void DFS(Vertex V){
    visit[V] = true;
	for ( W in Each adjacent point of V ) {
	    if (!visit[W]) {
		    DFS(W);
		}
	}
}

3.2 Breadth First Search (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Define the number of vertices in the graph
const int V = 5;

void bfs(vector<int> adj_list[], int start_vertex) {
    // Initialize a queue for BFS traversal
    queue<int> q;

    // Initialize a vector to keep track of visited vertices
    vector<int> visited(V, 0);

    // Mark the start vertex as visited and enqueue it
    visited[start_vertex] = true;
    q.push(start_vertex);

    while (!q.empty()) {
        // Dequeue a vertex from the queue and print it
        int u = q.front();
        cout << u << " ";
        q.pop();

        // Enqueue all adjacent vertices of the dequeued vertex that have not been visited
        for (int v : adj_list[u]) {
            if (!visited[v]) {
                visited[v] = 1;
                q.push(v);
            }
        }
    }
}

4. Application of Graph

4.1 Minimum Spanning Tree

A Minimum Spanning Tree (MST) of a connected, undirected graph is a spanning tree that connects all the vertices of the graph with the minimum possible total edge weight. In other words, an MST is a tree that connects all the vertices in the graph and has the minimum sum of edge weights among all possible trees that can be formed from the graph.

A spanning tree of a graph is a subgraph that is a tree and connects all the vertices of the original graph. Since an MST is also a spanning tree, it must have the same number of edges as the original graph (i.e., n-1 edges for a graph with n vertices). However, an MST may have edges with non-unique weights, and in such cases, the tree may not be unique.

MSTs have applications in various fields, such as network design, circuit design, and image segmentation. There are various algorithms to find the MST of a given graph, including Kruskal‘s algorithm, Prim‘s algorithm, and Boruvka‘s algorithm.

4.1.1 Prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
using namespace std;

#define MAX 10001
#define INF 1000000

vector<pair<int, int>> adj[MAX];
int parent[MAX]; // To store parent of each vertex in MST
bool visited[MAX]; // To keep track of visited vertices
int key[MAX]; // To store the minimum weight edge connected to each vertex in MST

void prim(int source, int n)
{
	// Init key and visited arrays
	for (int i = 0; i < n; i++)
	{
		key[i] = INF;
		visited[i] = false;
	}
	key[source] = 0;
	parent[source] = -1;
	for (int i = 0; i < n; i++)
	{
		// var u to store the vertex with the smallest key value
		int u = -1;

		// Find the unvisited vertex u with the smallest key value
		for (int j = 0; j < n; j++)
		{
			if (!visited[j] && (u == -1 || key[j] < key[u]))
			{
				u = j;
			}
		}
		// Mark the vertex u as visited
		visited[u] = true;

		// Update the key and parent of each unvisited neighbor of u, if necessary
		for (int j = 0; j < adj[u].size(); j++)
		{
			int v = adj[u][j].first;
			int weight = adj[u][j].second;
			if (!visited[v] && weight < key[v])
			{
				key[v] = weight;
				parent[v] = u;
			}
		}
	}
}

int main()
{
	int n, e, u, v, w;
	cin >> n >> e; // n is no of vertices and e is no of edges
	for (int i = 0; i < e; i++)
	{
		cin >> u >> v >> w; // edge from u to v with weight w
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w)); // for undirected graph
	}
	int source;
	cin >> source; // source vertex

	prim(source, n);  // Run Prim's algorithm from the source vertex

	int mst_weight = 0;
	for (int i = 0; i < n; i++)
	{
		if (key[i] != INF) // Add the weight of each edge in the MST to the total weight
			mst_weight += key[i];
	}
	cout << "Minimum Spanning Tree weight: " << mst_weight << endl;
	return 0;
}

Input Example:

1
2
3
4
5
6
7
8
9
10
11
6 9
0 1 3
0 3 1
1 2 5
1 3 4
1 4 6
2 4 7
2 5 8
3 4 2
4 5 9
0

4.1.2 Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 10001

int parent[MAX]; // Parent array for Union-Find
int rank_arr[MAX]; // Rank array for Union-Find

vector<pair<int, pair<int, int>>> edges; // Vector to store all edges in the graph

int find(int u)
{
	// Find the parent of u and perform path compression
	if (parent[u] != u)
		parent[u] = find(parent[u]);
	return parent[u];
}

void Union(int u, int v)
{
	// Perform Union by rank
	if (rank_arr[u] < rank_arr[v])
		parent[u] = v;
	else if (rank_arr[v] < rank_arr[u])
		parent[v] = u;
	else
	{
		parent[u] = v;
		rank_arr[v]++;
	}
}

int kruskal(int n)
{
	sort(edges.begin(), edges.end()); // Sort all edges in non-decreasing order of their weights

	for (int i = 0; i < n; i++)
	{
		parent[i] = i; // Initialize parent and rank arrays for Union-Find
		rank_arr[i] = 0;
	}

	int mst_weight = 0; // Variable to store the weight of the minimum spanning tree
	int edges_in_mst = 0; // Variable to keep track of the number of edges in the MST

	// Iterate through all edges in non-decreasing order of their weights
	for (int i = 0; i < edges.size(); i++)
	{
		int u = edges[i].second.first;
		int v = edges[i].second.second;
		int weight = edges[i].first;

		int pu = find(u);
		int pv = find(v);

		// Check if u and v are in the same connected component
		if (pu != pv)
		{
			mst_weight += weight; // Add the weight of the edge to the MST weight
			edges_in_mst++; // Increment the number of edges in the MST
			Union(pu, pv); // Merge the connected components of u and v using Union-Find

			// Check if all n-1 edges have been included in the MST
			if (edges_in_mst == n - 1)
				break;
		}
	}

	return mst_weight; // Return the weight of the minimum spanning tree
}

int main()
{
	int n, e, u, v, w;
	cin >> n >> e; // Input the number of vertices and edges

	// Input each edge as a pair of vertices and its weight
	for (int i = 0; i < e; i++)
	{
		cin >> u >> v >> w;
		edges.push_back(make_pair(w, make_pair(u, v))); // Add the edge to the vector of edges
	}

	int mst_weight = kruskal(n); // Run Kruskal's algorithm to find the MST weight

	cout << "Minimum Spanning Tree weight: " << mst_weight << endl; // Output the weight of the MST

	return 0;
}

4.2 Shortest Path

4.2.1 Dijskra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int visited[500] = { 0 };
int last = source;
min_len_cost[last] = 0;

for (int i = 0; i < N; i++) {
	visited[last] = 1;
	// UPDATE LEN
	for (auto j : edges[last])
		min_len_cost[j] = min(min_len_cost[j], min_len_cost[last] + len_cost[last][j]);
	int k = -1;
	for (int j = 0; j < N; j++)
		if (!visited[j] && (k < 0 || min_len_cost[k] > min_len_cost[j]))
			k = j;
	last = k;
}

4.2.2 Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>

using namespace std;

#define INF 1e9 // A very large value to represent infinity
#define MAX 101 // Maximum number of vertices in the graph

int dist[MAX][MAX]; // dist[i][j] stores the shortest distance between vertices i and j

void floyd_warshall(int n)
{
    // Iterate over all vertices k, then all pairs (i,j)
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // If the path from i to k and the path from k to j both exist
                if (dist[i][k] != INF && dist[k][j] != INF)
                    // Update the shortest distance between i and j through k
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main()
{
    int n, e, u, v, w;
    cin >> n >> e;

    // Initialize dist[i][j] to infinity, except when i=j
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
    }

    // Read the input graph and update dist accordingly
    for (int i = 0; i < e; i++)
    {
        cin >> u >> v >> w;
        dist[u][v] = w;
        // If the graph is undirected, add the following line as well:
        // dist[v][u]=w;
    }

    // Find the shortest paths between all pairs of vertices using Floyd-Warshall algorithm
    floyd_warshall(n);

    // Print the resulting distances
    cout << "All pairs shortest path:" << endl;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (dist[i][j] == INF)
                cout << "INF" << " ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Input Example:

1
2
3
4
5
6
4 5
0 1 5
0 2 10
1 2 3
2 3 1
1 3 8
#cpp
Data Structure and Algorithm - Graph
https://www.hardyhu.cn/2023/01/05/Data-Structure-and-Algorithm-Graph/
Author
John Doe
Posted on
January 5, 2023
Licensed under