OJ Board

Posted: **Mon Dec 20, 2004 1:01 pm**

Hello Everybody,
This is Niaz Morshed Chowdhury from Dhaka, Bangladesh.
In this "Topic" I will list Graph Algorithm and their sample implementation as well as some useful information and links. I am not a good programmer but I can say, from my side the try will be the best. I hope other experienced programmers will also contribute algorithms, views and ideas.

So, Lets start the journey.....

My first goal is to provide Algorithm and Implementation for the topics listed at the end of this post. I will list some problems and also give a rank beside those problems. Newcomer's first tusk should be to read the Algorithm and try to implement it by themselves. If they fail then they should have a look on my implementation. When they will feel that they are mature enough to attack the first problem from the list given with the algorithm, they should start then. In that list I will give a rank beside each problem. This rank will indicate their level of knowledge on that particular algorithm. I hope our journey will be an interesting one.

This training session will be available also at The ACM Solver Group. In that group I will upload some files and helpful e-books for the newcomers and also for the seniors. So, you may have a look there also.

These are the preliminary topics that will be discussed with the next few days.

1. Graph Traversal with BFS
2. Graph Traversal with DFS
3. Single Source Shortest Path
4. All Pair Shortest Path
5. Minimum Spanning Tree
6. Maximum Flow
7. Flood Fill

Niaz

Posted: **Sat Dec 25, 2004 9:35 am**

Hello Everybody,
I am going to attend World Universities Debating Championship 2005 in Malaysia on 26th of December. Please pray for me so that I can bring good result for my Country as well as my university.

I will continue working on the Graph Training after returning from Malaysia hopefully by 5th of January 2005.

Thanks.

Niaz Morshed Chowdhury

Posted: **Thu Mar 17, 2005 6:41 am**

Hi,

Long time no posts Niaz? We are waiting for your tutorial with bated breath

Posted: **Thu Apr 07, 2005 7:04 am**

Breadth First Search (BFS)

We have
- a quequ Q
- distance matrix d [ ] where finally we will get the result.
- parent matrix pi [ ] where finally we will get the parent of each vertex.
- color matrix color [ ] which will help us to identify which node is discovered and which one is not.
- we have u number of nodes.
- s is our source vertex.
- Let WHITE = 1, GRAY = 2 and BLACK = 3.

Code: Select all

BFS (G, s)
{
	
	// Initialization

	for ( all u )
	{
		color [u] = WHITE
		d [u] = Infinite
		pi [u] = -1;
	}
	color [s] = GRAY
	d [s] = 0;
	pi [s] = -1;
	
	initQ() // Q will be initialized.
	

	// Start

	enque(s) // insert source in Q
  
	while( empty() ) // empty() will return 0 if Q is empty otherwise 1
	{
		u = dequeue()
		for( each v connected with u) 
                // in the 2D connection matrix in u row 
                                                // all the v column that hold 1
		{
			if( color [v] = WHITE)
			{
				color [v] = GRAY
				d [v] = d [u] + 1
				pi [v] = u
				enque(v)
			}   
      }
		color [u] = BLACK
	}
}

Now, we will get the distance from s to all other vertex from the d [ ] matrix and parent of each vertex from pi [ ] matrix.
Let, s = 4 for a sample
Then d [1] will be the distance from vertex 4 to 1
and pi [1] will be the vertex from which we can reach 1 (which means parent vertex)

NOTE : I have tried to explain each and every points that I felt confusing while learning this Algorithm 3 years back. But you may feel the confusion in some other places. So, I hope, you will first read the algo carefully then try to understand it. Then post your confusion here. Just feel free to ask me. I will give the reply as early as possible.

OJ Board

Graph Algorithm Training for Newcomer and Interested Person

Graph Algorithm Training for Newcomer and Interested Person

Notice :-)

Hi

Breadth First Search (BFS)