Perform width search

0

I have a job to do and I'm beating my head to understand how I will do the same. I should perform a width search based on a .txt . The teacher sent some of the code (I'm only doing main ), I could already read the file, but I'm not sure how to feed the graph and start the width search based on the values.

The txt file looks like this:

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 origin vertex, target vertex and weight (in this order). I'm hooked on InsereAresta on main (which is where I believe I should start to mount 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");
}
    
asked by anonymous 05.05.2017 / 22:48

0 answers