finding the longest path in a tree

There is a very good task in spoj which requires finding the longest path in a tree.
Go here to find the link to the task, the explanation and teh full source code for this task.

DFS (depth first search)

DFS is another search algorithm in graphs. The absic use os this algorithm is finding the "first" way between to edges. It won't be the shortest like BFS. but it will find the first way betwwen 2 nodes. We implement DFS with the help of recursion.
void DFS(int X)
{
    for(i=0;i< number of neighbours of X ; i++)
  {  
     a=current neighbour;
     if( not marked a)
       {    
             DFS(a);
            a becomes marked;
       }
    }
}

        

BFS (Breadth First Search)

 The BFS is used to find a shortest path between 2 points of the graph. The C++ STL  queue. Consider these steps for the BFS algorithm. Suppose we want to find the distance between nodes X and Y.
We need to use a pair, the first element will show the current node and the second element will show the distance between the nodes X and the node we are currently in.
Step 1 . Add the first pait to the queue . The first element of the pair is X and the second element of the pair is 0. (The distance between X and X is 0 : ) ).
Step 2 On every step check all the nodes which are neghbours with node X . If the node we are checking is not visited ( every time we add a node to our queue , we mark it as visited so that we won't have to visist it again) we add that node to the queue and the distance equals to the distance which is required to reach teh neghbour of that node + 1.
Step.3 Do the second step until you reach the node Y (note that whenever you reach the node Y you should stop the process because the found distance is the shortest).

The pseudocde
Suppose we have queue q;

q.push(x,0);
while( q is not empty)
{
        take the first element of the queue.
         node=the first elemnet of q.top()
       distnace = the second element of the q.top()
       for(i=0; i< neighboursnumberl i++)
               If ( neighbour is not visited )
                   q. add element( neighbour, distance+1)
      remove the first element of queue
}

And also check if you reached the Y node or not. If you reached it there is not point in continuing our loop,




                     

Directed and indirected graphs.

Let's have a look at 2 graphs which are almost the same.

The two graphs are almost the same. But there is one difference. The cities of the first graph are connected with simple lines while the cities of the second graph are connected with vectors.
   There are 2 types of graphs. They are called directed and indirected. As the name suggests indirected means without directions. The first graph is indirected. If we can go from the city A to city B and we can get back from city B to city A that means that the road connecting the cities A and B is not directed. In  the second graph, the arrow means that we can go from A to B but we can't get back. We can only move with the direction of an arrow. 

what are graphs?

We can imagine a graph as a bunch of different cities which are connected to each other with roads. 

The picture above is a simple graph. Here we have cities A,B,E,G,H,F,K,M and the roads which are connecting them. The cities are called nodes (sometimes vertexes) and the roads are called edges. So if we want to get from the city G to the city K as fast as possible We can go to the city H then go to K or we can go to the city M and then go to K. We treat all the roads equally. There is a type of a graph when the roads have , let's say length. The lengths of cities are sometimes called weights. 

The graph above is the same as the previous one but the roads of this graph have wights (lengths). So if we want to get from the city G to the city k as fast as possible we better go to the city M and then to K (by doing so we will pass 13+34=47 distance not 4+47 (If we went to H then to K) ).. 

Examples of graphs from our daily life

 1.  The cities and roads.

 2.  Airport network

3.  Firneds of friends network

   You have a friend. And your friend has another friend whom you don't know so you are connected to your friend and you friend is connected to his friend.

4. Internet network 

 Your computer is connected to a modem. The modem is connected to the ISP (internet service provider).ISP is connected to the different sattelites which connect the whole internet together and so...

...

....

....