Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Introduction To Graph Theory …FTC 👈 👈 😉
A cycle in a directed graph exists if there’s a back edge discovered during a DFS. A back edge is an edge from a node to itself or one of the ancestors in a DFS tree. For a disconnected graph, we get a DFS forest, so you have to iterate through all vertices in the graph to find disjoint DFS trees.
C++ implementation:
#include <iostream> #include <list> using namespace std; #define NUM_V 4 bool helper(list<int> *graph, int u, bool* visited, bool* recStack) { visited[u]=true; recStack[u]=true; list<int>::iterator i; for(i = graph[u].begin();i!=graph[u].end();++i){ if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal return true; else if(*i==u) //if there's an edge from the vertex to itself return true; else if(!visited[*i]){ if(helper(graph, *i, visited, recStack)) return true; } } recStack[u]=false; return false; } /* /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false. */ bool isCyclic(list<int> *graph, int V) { bool visited[V]; //array to track vertices already visited bool recStack[V]; //array to track vertices in recursion stack of the traversal. for(int i = 0;i<V;i++) visited[i]=false, recStack[i]=false; //initialize all vertices as not visited and not recursed for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited { if(visited[u]==false) { if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle return true; } } return false; } /* Driver function */ int main() { list<int>* graph = new list<int>[NUM_V]; graph[0].push_back(1); graph[0].push_back(2); graph[1].push_back(2); graph[2].push_back(0); graph[2].push_back(3); graph[3].push_back(3); bool res = isCyclic(graph, NUM_V); cout<<res<<endl; }
Output of the above program is : 1
Illustration of Output of above program in terminal
![](http://www.fcukthecode.com/wp-content/uploads/2022/03/Screenshot-from-2022-03-24-19-29-09.png)
Result: As shown below, there are three back edges in the graph. One between vertex 0 and 2; between vertice 0, 1, and 2; and vertex 3. Time complexity of search is O(V+E) where V is the number of vertices and E is the number of edges.
![](http://www.fcukthecode.com/wp-content/uploads/2022/03/Screenshot-from-2022-03-24-19-27-49.png)
To store a graph, two methods are common:
- Adjacency Matrix
- Adjacency List
An adjacency matrix is a square matrix used to represent a finite graph. Adjacency Matrix (Storing Graphs) 👈 👈 😉
An Adjacency list is a collection of unordered lists used to represent a finite graph. Storing Graphs (Adjacency List) 👈 👈 😉
Explore
1. Quantum Mechanics relation with quantum computing
2. Unzipping Files using Python
3. An Algorithm which accepts n integer values and calculates the average and prints it.
4. How can Quantum Computing merge with Virtual Reality ? !
5. Blockchain and Cryptocurrency. And their relations with Virtual Reality !!