[Patrunjel]

Hi.
Now i'm learning graphs, and i really can't get my head around BF.I mean, i uderstand the concept, but i can't get it to work in code.I don't get errors, but the function isn't working....can somewone over here please give an advice?

#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("graph");

struct node{
    int val;//the number that corresponds to the node
    node *next_adr;//the next address (for the linked list)
};

void read(node *a[],int &n){
/* a-the array in witch i keep the nodes
n- the number of nodes */
    int i,j;
    node *p;
    fin>>n;
    while(fin>>i>>j){
        p=new node;
        p->val=j;
        p->next_adr=a[i];
        a[i]=p;

        p=new node;
        p->val=i;
        p->next_adr=a[j];
        a[j]=p;}
}

void write(node *a[],int n){//writes the nodes of the graph, just for testing the input
    int i;
    node *p;//i cycle with p through the list that represents the adiacent nodes to the i node
    for(i=0;i<n;i++){
        cout<<"The nodes adiacent to "<<i<<" are : ";
        p=a[i];
        while(p){
            cout<<p->val<<" ";
            p=p->next_adr;}
        cout<<endl;}
    cout<<endl;}

void breadth_first(node *a[]){
    int queue[100];//I meant a FIFO structure, sorry i don't know how to say it in english
    int visited[100]={0};//to know what nodes i have visited
    int start=0,end=0,num;//the end and start of the FIFO structure
    node *p;//cursor for the nodes
    cout<<"We start the search at node : ";cin>>num;
    queue[0]=num;
    end++; //add the selected element to the queue
    while(start<end){
        p=a[queue[start]];//the first element in the FIFO structure
        while(p){
            if(!visited[p->val]){//if node p->val is not visited
                queue[end]=p->val;//add it to the queue
                end++;}
            p=p->next_adr;}
        cout<<a[queue[start]]->val<<" ";//output the node through i have just passed
        visited[queue[start]]=1;
        start++;}
}
int main(){
    node *a[100]={0};//initialize a at 0 (like being global)
    int n;
    read(a,n);
    breadth_first(a);
    return 0;}

If you want to help, and don't understand some part of the source, please ask...

[jimblumberg]

Please post a sample of your input file.

Also the use of the pointer for your node array doesn't make much sense to me.

Jim

[Patrunjel]

Wow, an answer Thanks for interest
So, here is some input (please ignore the C++-like comments, i wanted to show what each number signifies)

6  //the total number of nodes
//nodes adiacent to each other. For example, 3 is adiacent to 1 (and 1 is adicent to 3)
3 1
1 4
0 1
0 5
0 2
5 2
2 6

The way i store the graphs looks like this : At the element 3 in the array, for example, i reffer to all the adiacent nodes to the node "3" , via a dinamic allocated simple linked list. I will do a simple drawing and edit in 5 minutes

This post has been edited by Patrunjel: 06 March 2011 - 07:54 AM

[Salem_c]

Start with simpler input files.

For example, with 1 or 2 nodes, there should be a trivial answer. If the code barfs on these, then you've got something else to fix first.

As a precaution, I would make sure that ALL your local variables are initialised.

It might be a good idea to add some code to validate your array subscripts as well.

[jimblumberg]

Quote

I don't get errors, but the function isn't working.

Please be more specific. What function? Why it isn't working. With your input file what do you expect your output to look like?

Jim

[Patrunjel]

Here is an example of how a graph is stored in memory (lower in the img you have the graph drawing) (sorry for the drawing being so retarded...)


The breadth_first function isn't working...i don't really have any clue on what im doing wrong...It should go through a graph ( BF ) and output the nodes that it had been through...I guess the problem is related to the visited[] array...I don't really have any clue...i have followed the algorithm on paper, still nothing...

Note: The array is from up to down, and the linked lists are from left to right.The numbers outside the arrays represent the indices of the elements.For example, in my drawing, the node called "2" is represented by the linked list on the indice 2 on the array.So it's adiacent nodes are 1 and 0.
The 0's at the end are there because of the initialization (i added values in front, when creating the linked list)

This post has been edited by Patrunjel: 06 March 2011 - 08:31 AM

[macosxnerd101]

It looks like the problem is the way you're setting up your Graph. The "Linked List" structure of the Graph is the fact that the Nodes point to other Nodes. Unlike a List though, Graph Nodes can point to multiple other Nodes, not just a single (or no) Node (which is hindering your ability to traverse the Graph). You could also add an isVisited field to your Node struct if you want to prevent multiple traversals of the Node (which for algorithms like Dijkstra's algorithm that utilize a BFS, this isn't a great idea).

I have a Graphs tutorial in Java you might want to check out. The syntax is somewhat different than C++, but the concepts are there.

Hope this helps some.

[jimblumberg]

I think you first problem is in your data structure. Breadth first searches are usually done using a queue. I found this tutorial on graphs and their data structures that you might find useful. There are several sections to this tutorial so be sure to look at all of them.


Jim

[Patrunjel]

I used a queue (the FIFO structure)

[macosxnerd101]

@jimblumberg: Often times when a breadth-first search is used with another algorith, a Queue or Priority Queue data structure is utilized. However, just for a simple BFS by itself, no queue is necessary if the Vertices store a collection of Edges or Vertices (depending on how the Graph is designed).