[mossy464]

Hi,

Im looking for a bit of guidance on this. I have a project for college for network design. It is to implement a C program for the breadth first search algorithm.

I can program in c but this is really confusing me, iv seen examples but they are hard to follow. Please see the brief below. Just need a push in the right direction to get started.

BRIEF:

Implement Moores + Breadth First Search algorithm

-Input a list of edges in the format

{A, B}

-Where A, B are integers.
-The application should return

* Shortest path between a pair of user selected nodes.
* A spanning tree for the network.


Estimate the performance of the algorithm as a function of no of edges in the input list.

(I.e. time no of top level operations, memory usage etc)

[Momerath]

Start with the first node, and check all the nodes that are attached to it. If you've arrived at the last node, you are done.
Otherwise, check all the subnodes, etc.

For example, you have these nodes:

A -> B, C, D
B -> A, E, F
C -> A, E, G, H
D -> A, H, I

so you'd check A->B, A->C, A->D. Then A->B->E, A->B->F. Then A->C->E, A->C->G, etc.

[mossy464]

Sorry back again. i dont know where to start with inputing the edges. is it a two dimensional array i use. If so how do i use that to find the shortest path. This is what i have so far. Nothing basically.

  
#include<stdio.h>

#define n 9
main()
{

	int a[n][n]={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),
	(3,1), (3,2), (3,3)};
	int i, j;
	
	printf("Enter the source node (1-3): ");
	scanf("%d",&i);
	
	printf("Enter the destination node (1-3): ");
	scanf("%d",&j);
	

	
}	 

This post has been edited by mossy464: 30 October 2009 - 09:12 AM

[mossy464]

Please help. Iv been trying to do this for the past 4 hours. Its head wrecking

[Oler1s]

Are you actually familiar with C? For example, I'd love for you to tell me what (1,2) is in C. You have int a[n][n]={(1,1),(1,2),(1,3),... and I'm asking you if each element of that array (something, something) makes sense?

What I'd like to know is what your logical data structure is. Forget about code. On paper, it's easy to draw a graph. You need to come up with a data structure that allows you to represent this graph. There's multiple ways to do it.

A two dimensional graph is one possible way. I'm going to give you a hint on that. Adjacency matrix.

[mossy464]

Yes i am familiar with C. Just not great at programming. Iv seen examples of adjacency matrices but done know how to find a shortest path.