CareerCup

As I said BFS is the solution to the problem.. so i thought y not code it and present it to you
instead of a pseudo code.. once you understand BFS, its simple to understand all the code..

boolean[][] adjMatrix; 
	 public void findTheDegree(){
		
		/* parse the strings & represent them in a Graph structure.. i'm using matrix representation here
		 * node-> person
		 * edges-> relationship (i.e. connected or not )
		 * In the above example 
		 * 	John, Jane, Jill, Jim, Jeb, June,Jason represented by vertices 
		 * 	   0,   1,     2,   3,   4,    5,  	6
		 * 
		 *   I'm using String[] array for convinience to represent the connections as below
		 *   each index referring to each person as above, and each string value representing the connections to the persons.  
		*/
		
		String[] connections = { "1:2:4:3",
		 		                        "0:6:5",
				                        "0:3",
				                        "0:2:5",
				                        "5:0",
				                        "3:1:4",
				                        "1"
						   };
		
		 int totalNodes = connections.length; 
		 adjMatrix = new boolean[totalNodes][totalNodes];
		
		//initially there are no connections among the nodes.. 
		 for(int i=0;i<totalNodes;i++){
		 	for(int j=0;j<totalNodes;j++){
				adjMatrix[i][j] = false;
			}
		 }
		
		 //setting up the connections
		 // from the problem statement, its indicated that it's an undirected graph 
		 //   ( this can be seen from the connections that are made in the graph ) 
		
		 for(int i=0;i<totalNodes;i++){
			 StringTokenizer st = new StringTokenizer(connections[i],":");
		 	  while(st.hasMoreTokens()){
				int j = Integer.parseInt(st.nextToken());
				adjMatrix[i][j]= true;
			}
		}
		
		int node1,node2;
		
		// eg: You would like to know the connection degree b/w John & June 
		// so node1-> 0, node2-> 5
		
		node1=0;
		node2=5;
		
		
		//use Breadth First Search to get the degreee of connection
		BFS(node1,node2,totalNodes);
		
	}
	
	
	public void BFS(int source, int target,int totalNodes){
		int degree=0; 
		boolean found=false;
		
		boolean[] color = new boolean[totalNodes];
		for(int i=0;i<totalNodes;i++)
			color[i]=false;
		
        class node{
        	int nodeValue;
        	int degree;
        	node(int nodeValue,int degree){
        		this.nodeValue = nodeValue;
        		this.degree = degree;
        	}
        };
		Deque<node> q= new ArrayDeque<node>();
		
		q.add(new node(source,0));
		node tempNode;
		while(!q.isEmpty() && !found){
			tempNode = q.poll();
			
			if(tempNode.nodeValue==target){
				found=true;
				degree = tempNode.degree;
				break;
			}
			
			if(color[tempNode.nodeValue]){
				continue;
			}
			
			color[tempNode.nodeValue]=true;
			
			for(int i=0;i<totalNodes;i++){
				if(adjMatrix[tempNode.nodeValue][i]){
					q.add(new node(i,tempNode.degree+1));
				}
			}
		}
		
		if(found){
			System.out.println("Degree -> "+degree);
		}
		else
			System.out.println(" Not Connected ");
	}

Use BFS.
Consider people as nodes. And their friendship as an edges between the nodes.

To improvise on the algorithm, run BFS from Both ends, and some kind of book keeping, like a Hashmap to keep track to visited nodes. ( Proof given by eugene in some previous post, If needed I will explain.)

Thanks Kai..for your help but this logic is going in infinite loop :

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication1
{
public class node
{
public int nodeValue;
public int degree;
public node(int nodeValue, int degree)
{
this.nodeValue = nodeValue;
this.degree = degree;
}
}
class Program
{
public Boolean[,] adjMatrix;


static void Main(string[] args)
{
Program p = new Program();
p.Initialize();
}

/* parse the strings & represent them in a Graph structure.. i'm using matrix representation here
* node-> person
* edges-> relationship (i.e. connected or not )
* In the above example
* John, Jane, Jill, Jim, Jeb, June,Jason represented by vertices
* 0, 1, 2, 3, 4, 5, 6
*
* I'm using String[] array for convinience to represent the connections as below
* each index referring to each person as above, and each string value representing the connections to the persons.
*/
public void Initialize()
{
string[] connections = { "1:2:4:3",
"0:6:5",
"0:3",
"0:2:5",
"5:0",
"3:1:4",
"1"
};

int totalNodes = connections.Length;
adjMatrix = new Boolean[totalNodes, totalNodes];

//initially there are no connections among the nodes..
for (int i = 0; i < totalNodes; i++)
{
for (int j = 0; j < totalNodes; j++)
{
adjMatrix[i, j] = false;
}
}

//setting up the connections
// from the problem statement, its indicated that it's an undirected graph
// ( this can be seen from the connections that are made in the graph )

for (int i = 0; i < totalNodes; i++)
{
string[] str = connections[i].Split(':');
foreach (string st in str)
{
int j = Convert.ToInt32(st);
adjMatrix[i, j] = true;
}
}

int node1, node2;

// eg: You would like to know the connection degree b/w John & June
// so node1-> 0, node2-> 5

node1 = 0;
node2 = 5;


//use Breadth First Search to get the degreee of connection
BFS(node1, node2, totalNodes);
}


public void BFS(int source, int target, int totalNodes)
{
int degree=0;
Boolean found=false;

Boolean[] color = new Boolean[totalNodes];

for(int i=0;i<totalNodes;i++)
color[i]=false;

Queue<node> q = new Queue<node>();
q.Enqueue(new node(source,0));

//Deque<node> q= new ArrayDeque<node>();

//q.add(new node(source,0));
node tempNode = new node(0,0) ;

while(q.Count != 0 && !found)
{
tempNode = (node) q.Peek();

if(tempNode.nodeValue == target){
found=true;
degree = tempNode.degree;
break;
}

if(color[tempNode.nodeValue]){
continue;
}

color[tempNode.nodeValue]=true;

for(int i=0;i<totalNodes;i++){
if(adjMatrix[tempNode.nodeValue,i])
{
q.Enqueue(new node(i,tempNode.degree+1));
}
}
}

if(found){
Console.WriteLine("Degree -> "+degree);
}
else
Console.WriteLine(" Not Connected ");
}
}
}

Kai's program is excellent. One thing to note is it will detect 2nd degree connnection between John and June by 1) John is friend with Jane and Jane is friend with June. The explaination given in problem is still valid but if you run Kai's program, this is how it will determine the 2nd degree connection