Perform wide search

Question

I’ve got a job to do and I’m racking my brain to figure out how I’m gonna do the same. I must perform a wide search based on a .txt. The teacher sent part of the code (I’m just doing the main), I’ve already been able to read the file, but I’m not sure how to feed the graph and start the search in width based on the values.

The archive txt comes this way:

7 8

1 2 1

1 3 1

2 4 1

3 4 1

4 5 1

4 6 1

5 7 1

6 7 1

The first line is the number of vertices and the number of edges. From the second line down are the source vertex, target vertex and weight (in this order). I’m stuck in the InsereAresta in main (which is where I believe I should start to assemble the graph).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNUMVERTICES 100
#define MAXNUMARESTAS 4500
#define FALSE 0
#define TRUE 1

typedef int TipoValorVertice;
typedef int TipoPeso;

typedef struct TipoItem
{
    TipoValorVertice Vertice ;
    TipoPeso Peso;
} TipoItem;

typedef struct TipoCelula *TipoApontador;

struct TipoCelula
{
    TipoItem Item;
    TipoApontador Prox;
} TipoCelula;

typedef struct TipoLista
{
    TipoApontador Primeiro , Ultimo;
} TipoLista;

typedef struct TipoGrafo
{
    TipoLista Adj[MAXNUMVERTICES + 1];
    TipoValorVertice NumVertices;
    short NumArestas;
} TipoGrafo;

void FLVazia(TipoLista *Lista)
{
    Lista->Primeiro = (TipoApontador) malloc(sizeof(TipoCelula ));
    Lista->Ultimo = Lista->Primeiro ;
    Lista->Primeiro->Prox = NULL;
}

void FGVazio(TipoGrafo *Grafo)
{
    long i ;
    for ( i = 0; i < Grafo->NumVertices; i ++)
        FLVazia(&Grafo->Adj[ i ] ) ;
}

void Insere(TipoItem x, TipoLista *Lista)
{
    Lista->Ultimo->Prox = (TipoApontador) malloc(sizeof(TipoCelula ));
    Lista->Ultimo = Lista->Ultimo->Prox;
    Lista->Ultimo->Item = x;
    Lista->Ultimo->Prox = NULL;
}

void InsereAresta(TipoValorVertice *V1, TipoValorVertice *V2, TipoPeso
                  *Peso, TipoGrafo *Grafo)
{
    TipoItem x;
    x.Vertice = *V2;
    x.Peso = *Peso;
    Insere(x, &Grafo->Adj[*V1] ) ;
}

short ExisteAresta(TipoValorVertice Vertice1 ,TipoValorVertice Vertice2 ,
                   TipoGrafo *Grafo)
{
    TipoApontador Aux;
    short EncontrouAresta = FALSE;
    Aux = Grafo->Adj[Vertice1 ] . Primeiro->Prox;

    while (Aux != NULL && EncontrouAresta == FALSE)
    {
        if ( Vertice2 == Aux->Item. Vertice ) EncontrouAresta = TRUE;
        Aux = Aux->Prox;
    }
    return EncontrouAresta;
}

short ListaAdjVazia(TipoValorVertice *Vertice , TipoGrafo *Grafo)
{
    return (Grafo->Adj[*Vertice ] . Primeiro == Grafo->Adj[*Vertice ] . Ultimo);
}

TipoApontador PrimeiroListaAdj(TipoValorVertice *Vertice , TipoGrafo *Grafo)
{
    return (Grafo ->Adj[*Vertice ] . Primeiro->Prox) ;
}

void ProxAdj(TipoValorVertice *Vertice , TipoGrafo *Grafo, TipoValorVertice *Adj , TipoPeso
             *Peso, TipoApontador *Prox, short *FimListaAdj)
{
    *Adj = (*Prox)->Item. Vertice ;
    *Peso = (*Prox)->Item.Peso;
    *Prox = (*Prox)->Prox;

    if (*Prox == NULL)
        *FimListaAdj = TRUE;
}

int Vazia(TipoLista Lista)
{
    return ( Lista.Primeiro == Lista.Ultimo ) ;
}

void Retira(TipoApontador p, TipoLista *Lista , TipoItem *Item)
{
    TipoApontador q;
    if (Vazia(*Lista ) || p == NULL || p->Prox == NULL)
    {
        printf ( " Erro : Lista vazia ou posicao nao existe \n" );
        return;
    }

    q = p->Prox;
    *Item = q->Item ;
    p->Prox = q->Prox;

    if (p->Prox == NULL)
        Lista->Ultimo = p;
    free(q);
}

void RetiraAresta(TipoValorVertice *V1, TipoValorVertice *V2, TipoPeso *Peso, TipoGrafo *Grafo)
{
    TipoApontador AuxAnterior , Aux;
    short EncontrouAresta = FALSE;
    TipoItem x;
    AuxAnterior = Grafo->Adj[*V1] . Primeiro;
    Aux = Grafo->Adj[*V1] . Primeiro->Prox;
    while (Aux != NULL && EncontrouAresta == FALSE)
    {
        if (*V2 == Aux->Item. Vertice)
        {
            Retira(AuxAnterior, &Grafo->Adj[*V1] , &x);
            Grafo->NumArestas--;
            EncontrouAresta = TRUE;
        }
        AuxAnterior = Aux;
        Aux = Aux->Prox;
    }
}

void LiberaGrafo(TipoGrafo *Grafo)
{
    TipoApontador AuxAnterior , Aux;
    int i;
    for ( i = 0; i < Grafo->NumVertices; i++)
    {
        Aux = Grafo->Adj[ i ].Primeiro->Prox;
        free(Grafo->Adj[ i ].Primeiro ) ;

        Grafo->Adj[ i ].Primeiro=NULL;
        while (Aux != NULL)
        {
            AuxAnterior = Aux;
            Aux = Aux->Prox;
            free(AuxAnterior);
        }
    }
    Grafo->NumVertices = 0;
}

void ImprimeGrafo(TipoGrafo *Grafo)
{
    int i ;
    TipoApontador Aux;
    for ( i = 0; i < Grafo->NumVertices; i++)
    {
        printf ( "Vertice%2d: " , i );
        if ( !Vazia(Grafo->Adj[ i ]))
        {
            Aux = Grafo->Adj[ i ] . Primeiro->Prox;
            while (Aux != NULL)
            {
                printf ( "%3d (%d) " , Aux->Item. Vertice , Aux->Item.Peso);
                Aux = Aux->Prox;
            }
        }
        putchar('\n');
    }
}

int main()
{
    int qtdVertices = 0, qtdArestas = 0;

    char line[1024];
    FILE *fp = fopen("C:\\ep1_teste1.txt","r");

    //Verifica se o arquivo não foi aberto.
    if( fp == NULL )
    {
        return 1;
    }

    int primeiraLinha = 1;

    //Lê cada linha e imprimi os valores de cada uma.
    while( fgets(line,1024,fp) )
    {
        printf("%s\n",line);

        if(primeiraLinha == 1)
        {
            char* variaveis = strtok(line, " ");
            while(variaveis != NULL)
            {
                if(qtdVertices == 0)
                    qtdVertices = atoi(variaveis);
                else
                    qtdArestas = atoi(variaveis);

                variaveis = strtok(NULL, " ");
            }

            primeiraLinha = 0;
        }
        //Segunda linha pra frente
        else
        {
            int contaVariavel = 0;
            int noPai = 0, noFilho = 0, peso = 0;

            TipoValorVertice *V1;
            TipoValorVertice *V2;
            TipoPeso *Peso;
            TipoGrafo *Grafo;

            char* variaveisSegundaLinha = strtok(line, " ");
            while(variaveisSegundaLinha != NULL)
            {
                if(contaVariavel == 0)
                {
                    noPai = atoi(variaveisSegundaLinha);
                }
                else if(contaVariavel == 1)
                {
                    noFilho = atoi(variaveisSegundaLinha);
                }
                else if(contaVariavel == 2)
                {
                    peso = atoi(variaveisSegundaLinha);
                }

                variaveisSegundaLinha = strtok(NULL, " ");
                contaVariavel++;
            }

            InsereAresta(V1, V2, Peso, Grafo); //Estou agarrado aqui
        }
    }

    system("PAUSE");
}