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. And adj[i][j] represents there is an edge from node i to j.
There are two ways to represent a graph
1. Adjacency matrix:
Time Complexity:O(m)**** Space Complexity:**O(n*n)**
2. Adjacency List
Time Complexity:**O(m)** Space Complexity:**O(n*n)**
If there are also weights in edges, we create the adjacency list as ' vector <vector < pair <int,int> > > ' where first value is node(v) and second value represents weight b/w the nodes(u and v).
Since there can be multiple disconnected components in a graph, while graph traversal we have to call BFS/DFS from every unvisited node. To avoid repetition we store information if a node is visited or not by creating a boolean array where is_visited[i]==true represents node 'i' is visited. ~~~~~ for(int i=1i<=n;i++) { if(!is_visited[i]) BFS(i); } ~~~~~
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 Graphs
Case 1:Cycle detection in undirected graph using dfs
If a node adjacent to a node ( that is not its parent node ) is already visited, the component contains a cycle.