Basic terminologies:
Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights. In an undirected graph, the sum of degrees of all vertices is double the vertices (We consider degree=indegree=outdegree in an undirected graph).
Graph representation in C++
Let us say there are n nodes and m edges.
There are two ways to represent a graph
- Adjacency matrix:
adj[i][j] represents there is an edge from node i to j.
int n, m;
cin >> n >> m;
// declare the adjacent matrix
int adj[n+1][n+1];
// take edges as input
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1; //write this line only if the graph is undirected
}
Time Complexity:**O(m)**
Space Complexity:**O(n*n)**
- Adjacency List
cin >> n >> m;
// declare the adjacent matrix
vector<vector<int>> adj[n+1];
vector<int> adj[n+1];
// take edges as input
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
return 0;
}
Time Complexity:**O(m)**
Space Complexity:**O(n*n)**
If there are also weights in edges we create the adjacency list like vector <vector < pair <int,int> > > where first value is node and second value represents weight b/w the nodes.
Since there can be multiple components in a graph, for graph traversal we have to call BFS/DFS from every unvisited node, but to avoid repetition we will store information if a node is visited by creating a boolean array where is_visited[i]==true represents node 'i' is visited.
BFS
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for queue )
DFS
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for stack space )
Cycle detection in undirected graph using DFS
If a node adjacent to a node is already visited except the adjacent node is its parent, the component contains a cycle.