Graphs have a wide range of applications in various domains. They can be used to solve real-life problems by modeling and analyzing relationships between different entities. Here are some common applications of graphs:
Social Networks: Graphs can represent social networks, where nodes represent individuals or organizations, and edges represent relationships like friendships or collaborations. They can be used to analyze the structure of social networks, identify influencers, or recommend new connections.
Transportation Networks: Graphs can model transportation networks like roads, railways, or air routes. They can be used to find the shortest path between two locations, calculate travel times, or optimize transportation routes.
Recommendation Systems: Graphs can power recommendation systems that suggest products, movies, or music based on user preferences and item similarities. They can use graph algorithms to find similar items, calculate item rankings, or personalize recommendations.
Web Search: Graphs are used in web search engines to represent the relationships between web pages. They can be used to determine the relevance and importance of web pages, rank search results, or discover new web pages using web crawling algorithms.
C++ code: To demonstrate how graphs can be used to check if there is a path between two vertices, here's an example code snippet:
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Function to check if there is a path between two vertices
6bool isPathExist(vector<vector<int>>& graph, int start, int end) {
7 if (start == end) {
8 return true;
9 }
10
11 int n = graph.size();
12 vector<bool> visited(n, false);
13
14 visited[start] = true;
15
16 // Create a stack for DFS
17 vector<int> stack;
18 stack.push_back(start);
19
20 while (!stack.empty()) {
21 int currVertex = stack.back();
22 stack.pop_back();
23
24 // Visit all the neighbors of the current vertex
25 for (int neighbor : graph[currVertex]) {
26 if (neighbor == end) {
27 return true;
28 }
29
30 if (!visited[neighbor]) {
31 visited[neighbor] = true;
32 stack.push_back(neighbor);
33 }
34 }
35 }
36
37 return false;
38}
39
40int main() {
41 // Create a graph
42 vector<vector<int>> graph = {
43 {1, 3},
44 {2},
45 {3},
46 {4},
47 {2},
48 {}
49 };
50
51 // Check if there is a path between vertex 0 and vertex 4
52 bool pathExists = isPathExist(graph, 0, 4);
53
54 // Print the result
55 if (pathExists) {
56 cout << "There is a path between vertex 0 and vertex 4" << endl;
57 } else {
58 cout << "There is no path between vertex 0 and vertex 4" << endl;
59 }
60
61 return 0;
62}xxxxxxxxxx}using namespace std;// Function to check if there is a path between two verticesbool isPathExist(vector<vector<int>>& graph, int start, int end) { if (start == end) { return true; } int n = graph.size(); vector<bool> visited(n, false); visited[start] = true; // Create a stack for DFS vector<int> stack; stack.push_back(start); while (!stack.empty()) { int currVertex = stack.back(); stack.pop_back(); // Visit all the neighbors of the current vertex for (int neighbor : graph[currVertex]) { if (neighbor == end) { return true; }