Graph Overview

Graph is a combination of Vertices (or nodes) and set of Edges which connect a pair of nodes. 

These graphs will solve real life problems such as in networking.





Click here to debug more 

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

// A simple representation of graph using STL
#include <bits/stdc++.h>
using namespace std;

// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
        // adj[u] = v; in C programming
	adj[u].push_back(v); 
	adj[v].push_back(u);
}

// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
	for (int v = 0; v < V; ++v) {
		cout << "\n Adjacency list of vertex " << v
			<< "\n head ";
		for (auto x : adj[v])
			cout << "-> " << x;
		printf("\n");
	}
}

// Driver code
int main()
{
	int V = 5;
	vector<int> adj[V];
	addEdge(adj, 0, 1);
        // Vertex 0 head -> 1
        // Vertex 1 head -> 0
	addEdge(adj, 0, 4);    
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0
        // Vertex 4 head -> 0
	addEdge(adj, 1, 2);
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0 -> 2
        // Vertex 2 head -> 1
        // Vertex 4 head -> 0
	addEdge(adj, 1, 3);
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0 -> 2 -> 3
        // Vertex 2 head -> 1
        // Vertex 3 head -> 1
        // Vertex 4 head -> 0
	addEdge(adj, 1, 4);
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0 -> 2 -> 3 -> 4
        // Vertex 2 head -> 1 
        // Vertex 3 head -> 1
        // Vertex 4 head -> 0 -> 1
	addEdge(adj, 2, 3);
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0 -> 2 -> 3 -> 4
        // Vertex 2 head -> 1 -> 3
        // Vertex 3 head -> 1 -> 2
        // Vertex 4 head -> 0 -> 1
	addEdge(adj, 3, 4);
        // Vertex 0 head -> 1 -> 4
        // Vertex 1 head -> 0 -> 2 -> 3 -> 4
        // Vertex 2 head -> 1 -> 3 
        // Vertex 3 head -> 1 -> 2 -> 4
        // Vertex 4 head -> 0 -> 1 -> 3
	printGraph(adj, V);
	return 0;
}

Output

 Adjacency list of vertex 0
 head -> 1-> 4

 Adjacency list of vertex 1
 head -> 0-> 2-> 3-> 4

 Adjacency list of vertex 2
 head -> 1-> 3

 Adjacency list of vertex 3
 head -> 1-> 2-> 4

 Adjacency list of vertex 4
 head -> 0-> 1-> 3


 Adjacency Matrix             

Adjacency List



We will use graph in the following cases:
The graph node can be considered web pages, the edges can be hyperlinks between pages. 
The graph nodes can be Airports, and the edges represent the flights between airports. 

In most of the problems, we will have an undirected graph. 
Lee Algorithm - Shortest Path in Maze 
Flood Fill Algorithm  - Paint in MS

Click here to read the DFS & BFS search algorithm before jumping into the problems.

These are the curated list of graph problems 

• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Number of Islands (Must Read*)
• Longest Consecutive Sequence (Must Read*)
• Alien Dictionary (Leetcode Premium)
• Graph Valid Tree (Leetcode Premium)
• Number of Connected Components in an Undirected Graph


References : GeeksforGeeks

Comments

Post a Comment