Thread: graph problem

Hello everyone.I have to write a program which returns the min(max) key values ​​of the peak for a given graph.So far I have been able to writte the part for adding/searching for a node and arc.My idea is to use a Depth-first search and use a min/max function to find what I need.I program works ok ,until i added the dfs and convert every time i fix an error a bigger one show up

Code:

#include<iostream>
using namespace std;

const int n=10;
struct elem
{
    char key;
    elem * next;
}*g[n];


int convert(int k);
void init(elem * gr[n]);
int search_node(elem * g[], char c);
int search_arc(elem * g[], char c1, char c2);
void add_node(elem * g[n], char c);
void add_arc(elem * g[n], char c1, char c2);
void print(elem * g[n]);


int main()
{
    char c,d;
    int m, vhod, izhod;

    do{
        cout<<"\n\tMenu\n";
        cout<<"1-init\n";
        cout<<"2-add node\n";
        cout<<"3-add arc\n";
        cout<<"4-search node\n";
        cout<<"5-search arc\n";


        cout<<"8-print\n";

        cout<<"10-exit\n";

        cin>>m;

        switch(m)
        {
        case 1: { init(g); break; }
        case 2: { cout<<"\nInput c: "; cin>>c; add_node(g,c); break; }
        case 3: { cout<<"\nInput first node: "; cin>>c; cout<<"\nInput second node: "; cin>>d; add_arc(g,c,d) ; break; }
        case 4: { cout<<"\nInput node for searching: "; cin>>c;
            if(search_node(g,c)) cout<<"Yep ;)";
            else cout<<"Nope :(";
            break; }
        case 5: { cout<<"\nInput nodes for arc:\nc= "; cin>>c; cout<<"\nd= "; cin>>d;
            if(search_arc(g,c,d)) cout<<"Yep ;)";
            else cout<<"Nope :(";
            break; }

        case 8: { print(g) ; break; }


        case 10: { break; }
        }
    }while(m!=10);

}


void init(elem * gr[n])
{
    for(int i=0;i<n;i++)
        g[i]=NULL;
}


int search_node(elem * g[], char c)
{
    bool flag=false;
    for(int i=0;i<n;i++)
        if(g[i])
            if(g[i]->key==c)
                flag=true;
    return flag;
}


int search_arc(elem * g[], char c1, char c2)
{
    elem * t;
    bool flag=false;

    if(!search_node(g,c1))
        return false;
    if(!search_node(g,c2))
        return false;

    for(int i=0;i<n;i++)
    {
        if(g[i])
            if(g[i]->key==c1)
            {
                t=g[i];
                while(t->next)
                {
                t=t->next;
                if(t->key==c2) flag=true;
                }
            }
    }

    return flag;
}


void add_node(elem * g[n], char c)
{
    if(search_node(g,c))
        cout<<"\Existing node!\n";
    else
    {
        int j=0;
        while(g[j]&&j<n)    j++;
        if(g[j]==NULL)
        {
            g[j]=new elem;
            g[j]->key=c;
            g[j]->next=NULL;
        }
        else
            cout<<"\nOverflow!\n";
    }
}


void add_arc(elem * g[n], char c1, char c2)
{
    int i=0;
    elem * p;
    if(search_arc(g,c1,c2))
        cout<<"\nExisting arc!";
    else
    {
        if(!(search_node(g,c1)))
            add_node(g,c1);
        if(!(search_node(g,c2)))
            add_node(g,c2);
        while(g[i]->key!=c1)    i++;
        p=new elem;
        p->key=c2;
        p->next=g[i]->next;
        g[i]->next=p;
    }
}




void print(elem * g[n])
{
    elem * t;
    for(int i=0;i<n;i++)
    {
        if(!g[i]) continue;
        t=g[i];
        cout<<t->key<<" ";
        while(t->next)
        {
            t=t->next;
            cout<<t->key<<" ";
        }
        cout<<endl;
    }
}


void dfs(int k)
{
    cout<<k;
    int j=convert[k];
    g[j];
    for(elem *t=g[j]->next;t->next!=NULL;t=t->next)
       if(!g[convert(t->key)])
       dfs(t->key);
}

int convert(int k)
{
    int i=0;
    while(g[i]->key!=k)
        i++;
    return i;
}

Code:

                while(t->next)
                {
                t=t->next;

Why do you start with t->next?
Is there something special about the first node that you always skip it?

> while(g[j]&&j<n) j++;
> while(g[i]->key!=c1) i++;
Both these loops (and some others) lead to buffer overrun if the loop reaches n before finding something.