Graph Theory(Depth First Search)

Hello, guys in this article I will speak about the important searching way which is used in graph theory.

 Depth-first-search, ok first what is it? and how it works?
Here we have a photo which describes how this algorithm work:
  





In this algorithm, we move from the root of the tree to the depth level then we move up again and down again. as you see in the photo;
  

now one will ask me ok how can I implement that?

I will write an Implementation in C++ language


void dfs(int node)
{
visited[node] = true;

for(int i=0;i< adj[node];i++)
{
int child = adj[node][i];
if (!visited[child]) // To avoid cyclic behavior
dfs(child);
}

}
 
 let's talk about Dfs application which is Dfs EdgeClassification.
(notice that it works in Directed graph)

what is it???
let's look first.


ok in this photo you will notice four types of edges.
the first one is tree Edge: we called that edge is a tree edge when we move from parent to child
(like 1  -> 2)

the second one is Back edge: we called that edge is a Back edge when this edge makes cycle by moving 
from a deep level to a superficial level  
(like 4 -> 2)

the third one is forward edge: we called that edge is a forward edge when this edge moves from superficial node to deep one which is a child to the first one. 
(like 1->8)

the fourth one is cross edge: we called that edge is a cross edge when this edge moves from node to another node in another branch  
 (like 6  -> 3)













Comments

Post a Comment

Popular posts from this blog

Leet code (Reverse Integer)

  7.   Reverse Integer Given a signed 32-bit integer  x , return  x  with its digits reversed . If reversing  x  causes the value to go outside the signed 32-bit integer range  [-2 31 , 2 31  - 1] , then return  0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned).   Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Example 4: Input: x = 0 Output: 0   Constraints: -2 31  <= x <= 2 31  - 1 Solution class Solution { public:     int reverse(int x) {         int rev = 0;         while (x) {             int pop = x % 10;             x /= 10;             if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;             if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;             rev = rev * 10 + pop;         }         return rev;   }      };
Read more

Graph Theory(adjacency matrix,adjacency list)

Image
today I will speak about one of the most important topics which are graph theory. I will take a long time in this series because I wanna speak a lot of data structure related to graph theory but in the beginning, I will speak about just two representations which are  (adjacency matrix, adjacency list). adjacency matrix the first let's talk about adjacency matrix .this to make a memory representation for any graph (directed or non-directed) we can imagine that Like  code bool adjacency_matrix[100][100];        Example n=3 0 1 0 1 1 0 0 1 1 for(int i=0;i<n;i++) for(int j=0;j<;j++){ int x; cin>>x; adjacency_matrix[i][j]=x; } adjacency list then I will speak about adjacency list, how to represent it in memory and how we implement it with code code vector< vector<int> > adjList1;               if adjacency list without  weight vector< vector< pair<int, int> > > adjList2;    if adjacency list with weight Example-1               3
Read more

Recursion(Part 1)

In this article I will speak about one of the main topics in computer science and I will write some examples to make you know what is that and how you should use it.   Recursion function it’s a function call itself. And this function is consisting of three parts (Base Case, some Logic,  Sub-problem). 1-Base case: this is a case when it happens this recursion function should stop and gave you the result.     2- some Logic: which happens when function called himself. 3- Sub-problem: in this part, the function calls itself by part of it but this calling should never go to infinity. Ex1: void SayHello(int num) {     if(num < 1)                                                                // Base Case                         return;       cout<<"Hello.\n";                  // Some logic       SayHello(num - 1);                // Sub-problem - never go to infinity } Ex2 int Fact(int n) {             if(n <= 1)                   
Read more