5 Replies - 1789 Views - Last Post: 09 March 2011 - 02:24 PM Rate Topic: -----

#1 born2c0de   User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 187
  • View blog
  • Posts: 4,673
  • Joined: 26-November 04

Breadth First Search Graph Traversal

Posted 10 June 2008 - 07:42 AM

Description: Performs Breadth First Search on a Graph stored as an Adjacency Matrix.
/* Written by Sanchit Karve (born2c0de)
   Contact me on born2c0de AT dreamincode DOT net
*/

#include <stdio.h>

#define N 10

void bfs(int adj[][N],int visited[],int start)
{
	int q[N],rear=-1,front=-1,i;
	q[++rear]=start;
	visited[start]=1;
	while(rear != front)
	{
		start = q[++front];
		if(start==9)
			printf("10t");
		else
			printf("%c t",start+49); //change to 65 in case of alphabets

		for(i=0;i<N;i++)
		{
			if(adj[start][i] && !visited[i])
			{
				q[++rear]=i;
				visited[i]=1;
			}
		}
	}
}

int main()
{
	int visited[N]={0};
	int adj[N][N]={{0,1,1,0,0,0,0,0,0,1},
	{0,0,0,0,1,0,0,0,0,1},
	{0,0,0,0,1,0,1,0,0,0},
	{1,0,1,0,0,1,1,0,0,1},
	{0,0,0,0,0,0,1,1,0,0},
	{0,0,0,1,0,0,0,1,0,0},
	{0,0,0,0,0,0,0,1,1,1},
	{0,0,1,0,0,0,0,0,0,0},
	{0,0,0,1,0,0,0,0,0,0},
	{0,0,1,0,0,0,0,1,1,0}};

	bfs(adj,visited,0);
	return 0;

	
}



Is This A Good Question/Topic? 0
  • +

Replies To: Breadth First Search Graph Traversal

#2 aawadheshwari   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 03-May 09

Re: Breadth First Search Graph Traversal

Posted 03 May 2009 - 02:18 AM

plz add the graph u used ,i have to match it with the one made by me through the "adjancy matrix "taken by u.
Was This Post Helpful? 0
  • +
  • -

#3 born2c0de   User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 187
  • View blog
  • Posts: 4,673
  • Joined: 26-November 04

Re: Breadth First Search Graph Traversal

Posted 06 May 2009 - 04:09 AM

Can't you just create the graph from the adjacency matrix?
Was This Post Helpful? 0
  • +
  • -

#4 dranjan   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 11-July 09

Re: Breadth First Search Graph Traversal

Posted 10 July 2009 - 11:52 PM

brother the adjacency matrix u hav made seems to be wrong at some places .. u r kindly requested to check it Eg. in the 10th row:vertex 10 seems to be connected to 3 , 8,9. but in 9th row:9 is only connected to 4. there are other nistakes like this one. please rectify them also.
Was This Post Helpful? 0
  • +
  • -

#5 addibatista   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 0
  • Joined: 06-September 10

Re: Breadth First Search Graph Traversal

Posted 07 September 2010 - 11:32 PM

make it more user friendly. program still may some mistakes.
Was This Post Helpful? 0
  • +
  • -

#6 thebban   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 09-March 11

Re: Breadth First Search Graph Traversal

Posted 09 March 2011 - 02:24 PM

that codes doesnt work, would u please check it again. it compiles but before it runs it says run-time error: at line 24 and 47. thanks
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1