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 !!
Morae Q!
- Convert from binary number to decimal number.
- Swap two numbers by using division and multiplication.
- Compute foot and inches into centimetres.
- Concatenate Strings.
- Convert lowercase letters to uppercase letters.
- Compute the sum of all the digits of N.
- Compute the area of the pentagon.
- Get input using scanner.
- Find the distance between two points (x1,y1) and (x2,y2).
- Finding patterns in a file using frep and egrep .
- Detecting a cycle in a directed graph using Depth First Traversal.
- Topological ordering in a Graph.
- Storing graphs using adjacency list.
- Introduction to graph theory.
- Graph Adjacency Matrix pseudo code.
- Adjacency Matrix for storing graphs.
- Dijkstra’s shortest path algorithm .
- Breadth first search (BFS) Algorithm.
- Find the multiple of given number in the list of integers.
- Finding patterns in files using grep .