C Criação de um labirinto

[Lipeco]

Boa noite, estou aproveitando as aulas do Programação Descomplicada.

Já tentei e estou com dificuldade de criar um labirinto específico como na imagem abaixo.

Com esse código ele gera um labirinto aleatório.

Teriam alguma dica de como eu criar exatamente o labirinto específico?
 

//Arquivo Grafo.c
//Definição do tipo Grafo
struct grafo{
    int nro_vertices;
    int grau_max;
    int** arestas;
    int** pesos;
    int* grau;
};

Grafo* cria_Grafo(int nro_vertices, int grau_max){
    Grafo *gr;
    gr = (Grafo*) malloc(sizeof(struct grafo));
    if(gr != NULL){
        int i;
        gr->nro_vertices = nro_vertices;
        gr->grau_max = grau_max;
        gr->grau = (int*) calloc(nro_vertices,sizeof(int));

        gr->arestas = (int**) malloc(nro_vertices * sizeof(int*));
        gr->pesos = (int**) malloc(nro_vertices * sizeof(int*));
        for(i=0; i<nro_vertices; i++){
            gr->arestas[i] = (int*) malloc(grau_max * sizeof(int));
            gr->pesos[i] = (int*) malloc(grau_max * sizeof(int));
        }

    }
    return gr;
}

void libera_Grafo(Grafo* gr){
    if(gr != NULL){
        int i;
        for(i=0; i<gr->nro_vertices; i++){
            free(gr->arestas[i]);
            free(gr->pesos[i]);
        }
        free(gr->arestas);
        free(gr->pesos);
        free(gr->grau);
        free(gr);
    }
}

int insereAresta(Grafo* gr, int orig, int dest, int eh_digrafo, int peso){
    if(gr == NULL)
        return 0;
    if(orig < 0 || orig >= gr->nro_vertices)
        return 0;
    if(dest < 0 || dest >= gr->nro_vertices)
        return 0;

    gr->arestas[orig][gr->grau[orig]] = dest;
    gr->pesos[orig][gr->grau[orig]] = peso;
    gr->grau[orig]++;

    if(eh_digrafo == 0)
        insereAresta(gr,dest,orig,1,peso);
    return 1;
}

int procuraMenorDistancia(int *dist, int *visitado, int NV){
    int i, menor = -1, primeiro = 1;
    for(i=0; i < NV; i++){
        if(dist[i] >= 0 && visitado[i] == 0){
            if(primeiro){
                menor = i;
                primeiro = 0;
            }else{
                if(dist[menor] > dist[i])
                    menor = i;
            }
        }
    }
    return menor;
}

ARESTA* menorCaminho_Grafo(Grafo *gr, int ini, int *ant, int *dist){
    int i, pos, cont, NV, ind, *visitado, vert;
    cont = NV = gr->nro_vertices;
    visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++){
        ant[i] = -1;
        dist[i] = -1;
        visitado[i] = 0;
    }

    ARESTA *ar = (ARESTA*) malloc(4*NV * sizeof(ARESTA));
    for(i=0; i < 4*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
    }


    dist[ini] = 0;
    pos = 0;
    while(cont > 0){
        vert = procuraMenorDistancia(dist, visitado, NV);
        if(vert == -1)
            break;

        visitado[vert] = 1;
        cont--;
        for(i=0; i<gr->grau[vert]; i++){
            ind = gr->arestas[vert][i];

            ar[pos].orig = vert;
            ar[pos].dest = ind;
            pos++;

            if(dist[ind] < 0){
               dist[ind] = dist[vert] + 1;//ou peso da aresta
               ant[ind] = vert;
            }else{
                if(dist[ind] > dist[vert] + 1){
                    dist[ind] = dist[vert] + 1;//ou peso da aresta
                    ant[ind] = vert;
                }
            }
        }
    }

    free(visitado);
    return ar;
}

void arvoreGeradoraMinimaPRIM_Grafo(Grafo *gr, int orig, int *pai){
    int i, j, dest, NV, primeiro;
    int menorPeso;
    NV = gr->nro_vertices;
    for(i=0; i < NV; i++)
        pai[i] = -1;// sem pai

    pai[orig] = orig;
    while(1){
        primeiro = 1;
        for(i=0; i < NV; i++){//percorre todos os vértices
            if(pai[i] != -1){//achou vértices já visitado
                for(j=0; j<gr->grau[i]; j++){ // percorre os vizinhos do vértice visitado
                    if(pai[gr->arestas[i][j]] == -1){//achou vértice vizinho não visitado
                         if(primeiro){//procura aresta de menor custo
                            menorPeso = gr->pesos[i][j];
                            orig = i;
                            dest = gr->arestas[i][j];
                            primeiro = 0;
                         }else{
                             if(menorPeso > gr->pesos[i][j]){
                                menorPeso = gr->pesos[i][j];
                                orig = i;
                                dest = gr->arestas[i][j];
                             }
                         }
                    }
                }
            }
        }
        if(primeiro == 1)
            break;

        pai[dest] = orig;
    }
}


void buscaProfundidade(Grafo *gr, int ini, int dest, int *visitado, AR_PILHA* ar, int *cont, int *achou){
    int i;
    visitado[ini] = 1;
    for(i=0; i<gr->grau[ini]; i++){
        if(*achou == 1)
            return;

        if(!visitado[gr->arestas[ini][i]]){
            ar[*cont].orig = ini;
            ar[*cont].dest = gr->arestas[ini][i];
            ar[*cont].tipo = 0;
            (*cont)++;

            if(gr->arestas[ini][i] == dest){
                *achou = 1;
                return;
            }
            buscaProfundidade(gr,gr->arestas[ini][i],dest,visitado,ar,cont,achou);
            if(*achou == 0){
                ar[*cont].orig = ini;
                ar[*cont].dest = gr->arestas[ini][i];
                ar[*cont].tipo = 1;
                (*cont)++;
            }
            if(*cont > 8*gr->nro_vertices)
                printf("ERRO!!!\n");
        }
    }
}

AR_PILHA* buscaProfundidade_Grafo(Grafo *gr, int ini, int dest){
    int i, cont = 0, achou = 0;
    int NV = gr->nro_vertices;

    int *visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++)
        visitado[i] = 0;

    AR_PILHA *ar = (AR_PILHA*) malloc(8*NV * sizeof(AR_PILHA));
    for(i=0; i < 8*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
        ar[i].tipo = 0;
    }

    buscaProfundidade(gr,ini,dest,visitado,ar,&cont,&achou);
    free(visitado);
    return ar;
}

ARESTA* buscaLargura_Grafo(Grafo *gr, int ini){
    int i, vert, NV, cont = 1;
    int *fila, IF = 0, FF = 0;
    int ind, pos = 0;
    NV = gr->nro_vertices;

    int *visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++)
        visitado[i] = 0;

    ARESTA *ar = (ARESTA*) malloc(4*NV * sizeof(ARESTA));
    for(i=0; i < 4*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
    }

    fila = (int*) malloc(NV * sizeof(int));
    FF++;
    fila[FF] = ini;
    visitado[ini] = cont;
    while(IF != FF){
        IF = (IF + 1) % NV;
        vert = fila[IF];
        cont++;
        for(i=0; i<gr->grau[vert]; i++){
            ind = gr->arestas[vert][i];
            if(!visitado[ind]){

                ar[pos].orig = vert;
                ar[pos].dest = ind;
                pos++;
                //printf("pos = %d\n",pos);

                FF = (FF + 1) % NV;
                fila[FF] = ind;
                visitado[ind] = cont;
            }
        }
    }
    free(fila);

    return ar;
}

 

[devair1010]

@Lipeco    esse seu código não está compilando e nem func ,   mas creio que você possa usar uma função criada pelo usuário chamada " gotoxy "  , para posicionar o cursor nas posições que você quer desenhar o labirinto ,  mas no console não conseguirá fazer um gráfico bem elaborado , e então precisa usar uma biblioteca de terceiros , como a Allegro  , ou a SDL , ou a QT ou outras e até mesmo a API do windows que nem precisa ser instalada , , ....  ,

[arfneto]

12 horas atrás, Lipeco disse:

Teriam alguma dica de como eu criar exatamente o labirinto específico?
 

 

Simplesmente leia os vértices a partir de um arquivo. No arquivo digite de acordo com o desenho, claro.

 

Depois disso vai ter a matriz de adjancência e pode usar um métdo de percurso entre 1 e 36 o algoritmo vai te mostrar o melhor caminho.

[Lipeco]

@devair1010 Coloquei o código incompleto, não prestei atenção, estava tão cansado, vou colocar o código inteiro separando o main.c dos outros.

Segue abaixo

 

//Arquivo main.c
//fontes Programação descomplicada  
#include <windows.h>
#include <time.h>
#include "Labirinto.h"

LRESULT CALLBACK WindowProc(HWND, UINT, WPARAM, LPARAM);
void EnableOpenGL(HWND hwnd, HDC*, HGLRC*);
void DisableOpenGL(HWND, HDC, HGLRC);

int tipo = 0;
LABIRINTO *lab = NULL;

int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int nCmdShow)
{
    int op;

    printf("\t\tDeseja iniciar o Labirinto?\n\n");
    printf("\t\t1 - SIM ou 2 - não\n\n");
    printf("\t\tDigite sua opcao: ");
    scanf("%d", &op);
    printf("\n\n");

    if (op == 1){

    printf("\t\t\tAPOS ABRIR A INTERFACE\n");
    printf("\t\tAPERTE A TECLA 'ESPACO' PARA MOSTRAR\n \t\t     OS CAMINHOS ATE ACHAR A SAIDA\n\n");
    system("pause\n\n");

    WNDCLASSEX wcex;
    HWND hwnd;
    HDC hDC;
    HGLRC hRC;
    MSG msg;
    BOOL bQuit = FALSE;

    /* register window class */
    wcex.cbSize = sizeof(WNDCLASSEX);
    wcex.style = CS_OWNDC;
    wcex.lpfnWndProc = WindowProc;
    wcex.cbClsExtra = 0;
    wcex.cbWndExtra = 0;
    wcex.hInstance = hInstance;
    wcex.hIcon = LoadIcon(NULL, IDI_APPLICATION);
    wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
    wcex.hbrBackground = (HBRUSH)GetStockObject(BLACK_BRUSH);
    wcex.lpszMenuName = NULL;
    wcex.lpszClassName = "GLSample";
    wcex.hIconSm = LoadIcon(NULL, IDI_APPLICATION);;


    if (!RegisterClassEx(&wcex))
        return 0;

    /* cria janela principal do OpenGl */
    hwnd = CreateWindowEx(0,
                          "GLSample",
                          "OpenGL Sample",
                          WS_OVERLAPPEDWINDOW,
                          CW_USEDEFAULT,
                          CW_USEDEFAULT,
                          650,
                          650,
                          NULL,
                          NULL,
                          hInstance,
                          NULL);

    ShowWindow(hwnd, nCmdShow);

    /* Ativa OpenGL para janela */
    EnableOpenGL(hwnd, &hDC, &hRC);

    //Inicia Tudo
    //srand(time(NULL));

    lab = monta_labirinto();

    /* program main loop */
    while (!bQuit)
    {
        /* check for messages */
        if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE))
        {
            /* handle or dispatch messages */
            if (msg.message == WM_QUIT)
            {
                bQuit = TRUE;
            }
            else
            {
                TranslateMessage(&msg);
                DispatchMessage(&msg);
            }
        }
        else
        {
            /* OpenGL animation code goes here */

            glClearColor(1.0f, 1.0f, 1.0f, 0.0f);
            glClear(GL_COLOR_BUFFER_BIT);

            glPushMatrix();

            desenha_labirinto(lab,tipo);

            glPopMatrix();

            SwapBuffers(hDC);


            Sleep(10);
        }
    }

    destroi_labirinto(lab);

    /* shutdown OpenGL */
    DisableOpenGL(hwnd, hDC, hRC);

    /* destroy the window explicitly */
    DestroyWindow(hwnd);

    return msg.wParam;
    }else{
        exit(1);
    }
}

LRESULT CALLBACK WindowProc(HWND hwnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
    switch (uMsg)
    {
        case WM_CLOSE:
            PostQuitMessage(0);
        break;

        case WM_DESTROY:
            return 0;

        case WM_KEYDOWN:
        {
            switch (wParam)
            {
                case VK_ESCAPE:
                    PostQuitMessage(0);
                break;

                case VK_SPACE: tipo = (tipo + 1) % 7;
                               if(tipo > 3)
                                   inicia_animacao(lab);
                               break;

            }
        }
        break;

        default:
            return DefWindowProc(hwnd, uMsg, wParam, lParam);
    }

    return 0;
}

void EnableOpenGL(HWND hwnd, HDC* hDC, HGLRC* hRC)
{
    PIXELFORMATDESCRIPTOR pfd;

    int iFormat;

    /* get the device context (DC) */
    *hDC = GetDC(hwnd);

    /* set the pixel format for the DC */
    ZeroMemory(&pfd, sizeof(pfd));

    pfd.nSize = sizeof(pfd);
    pfd.nVersion = 1;
    pfd.dwFlags = PFD_DRAW_TO_WINDOW |
                  PFD_SUPPORT_OPENGL | PFD_DOUBLEBUFFER;
    pfd.iPixelType = PFD_TYPE_RGBA;
    pfd.cColorBits = 24;
    pfd.cDepthBits = 16;
    pfd.iLayerType = PFD_MAIN_PLANE;

    iFormat = ChoosePixelFormat(*hDC, &pfd);

    SetPixelFormat(*hDC, iFormat, &pfd);

    /* create and enable the render context (RC) */
    *hRC = wglCreateContext(*hDC);

    wglMakeCurrent(*hDC, *hRC);
}

void DisableOpenGL (HWND hwnd, HDC hDC, HGLRC hRC)
{
    wglMakeCurrent(NULL, NULL);
    wglDeleteContext(hRC);
    ReleaseDC(hwnd, hDC);
}

 

// labirinto.h
#include <gl/gl.h>

typedef struct labirinto LABIRINTO;

void desenha_circulo(GLfloat x, GLfloat y, GLfloat radius);
void desenha_linha(GLfloat x1, GLfloat y1, GLfloat x2, GLfloat y2, int cor);

LABIRINTO* monta_labirinto();
void destroi_labirinto(LABIRINTO* lab);

void desenha_arvore_geradora(int *arv);
void desenha_paredes_labirinto(int *arv);
void desenha_labirinto(LABIRINTO *lab,int tipo);

void inicia_animacao(LABIRINTO *lab);
void desenha_procura_caminho(LABIRINTO *lab);
void desenha_menor_caminho(LABIRINTO *lab);

void desenha_busca_largura(LABIRINTO *lab);

 

//labirinto.c

#include "Labirinto.h"
#include "Grafo.h"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

struct labirinto{
    int *arv;
    int *ant;
    int dist;
    ARESTA *ar_largura;
    ARESTA *ar;
    AR_PILHA *ph;
    int idx;
};

//=========================================================
// Tamanho da matriz do labirinto
#define N 3
// Tamanho de cada bloco da matriz na tela
#define TAM (2.0f / N)
//Funções que convertem a linha e coluna da matriz em uma coordenada de [-1,1]
#define MAT2X(j) ((j)* TAM - 1.0)
//#define MAT2Y(i) (1.0 - (i) * TAM)
#define MAT2Y(i) (1.0 - (i) * TAM)
//=========================================================

void desenha_linha(GLfloat x1, GLfloat y1, GLfloat x2, GLfloat y2, int cor){

    switch(cor){
        case 0: glColor3f(0.0,0.0,0.0); glLineWidth(5); break;
        case 1: glColor3f(1.0,0.0,0.0); glLineWidth(2); break;
        case 2: glColor3f(1.0,1.0,1.0); glLineWidth(5); break;
    }
    glBegin(GL_LINES);
        glVertex2f(x1, y1);
        glVertex2f(x2, y2);
    glEnd();
}

void desenha_circulo(GLfloat x, GLfloat y, GLfloat radius){
	int i, triangleAmount = 20; //# of triangles used to draw circle
	GLfloat twicePi = 2.0f * acos(-1.0);
    glColor3f(0.0,0.0,0.0);
	glBegin(GL_TRIANGLE_FAN);
		glVertex2f(x, y); // center of circle
		for(i = 0; i <= triangleAmount;i++) {
			glVertex2f(x + (radius * cos(i *  twicePi / triangleAmount)),
                       y + (radius * sin(i * twicePi / triangleAmount)));
		}
	glEnd();
}


LABIRINTO* monta_labirinto(){
    LABIRINTO* lab = malloc(sizeof(LABIRINTO));

    if(lab == NULL)
        return NULL;

    int i,j;
    Grafo* gr = cria_Grafo(N*N, 4);

    for(i=0; i<N; i++){
        for(j=0; j<N; j++){

            int v1 = i * N + j; //v1 Origem
            printf("V1: %d ",v1);

                if(j+1 < N){
                int v2 = i * N + (j+1);
                printf("V2: %d ",v2);
                if(!insereAresta(gr,v1,v2,0,rand()%9 + 1))
                    printf("\nErro 1: %d %d",i,j);
                }

                if(i+1 < N){

                int v2 = (i+1) * N + j; //v2 destino
                printf("V2 depois: %d \n",v2);
                if(!insereAresta(gr,v1,v2,0,rand()%9 + 1))
                    printf("\nErro 2: %d %d",i,j);
                }
        }
    }

    lab->arv = malloc(N*N*sizeof(int));
    lab->ant = malloc(N*N*sizeof(int));
    int *dist = malloc(N*N*sizeof(int));

    arvoreGeradoraMinimaPRIM_Grafo(gr, 0, lab->arv);
    libera_Grafo(gr);
    // =============================================
    //criar um novo grafo com a árvore geradora...
    gr = cria_Grafo(N*N, 4);
    int N2 = N*N;
    for(i=1; i < N2; i++){
        if(!insereAresta(gr,i,lab->arv[i],0,1))
            printf("Erro ARV: %d %d",i,lab->arv[i]);
    }

    lab->ar = menorCaminho_Grafo(gr, 0, lab->ant, dist);
    lab->dist = dist[N*N-1];
    free(dist);

    lab->ph = buscaProfundidade_Grafo(gr, 0, N*N-1);
    lab->ar_largura = buscaLargura_Grafo(gr, 0);

    libera_Grafo(gr);
    return lab;
}

void destroi_labirinto(LABIRINTO* lab){
    if(lab == NULL)
        return;
    free(lab->arv);
    free(lab->ant);
    free(lab->ar);
    free(lab->ar_largura);
    free(lab->ph);
    free(lab);
}

void desenha_arvore_geradora(int *arv){
    int i, j;

    int N2 = N*N;
    int i1, i2, j1, j2;

    for(i=1; i < N2; i++){
        i1 = i / N;
        j1 = i % N;

        i2 = arv[i] / N;
        j2 = arv[i] % N;

        desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                      MAT2X(j2+0.5), MAT2Y(i2+0.5),1);
    }

    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            desenha_circulo(MAT2X(j+0.5), MAT2Y(i+0.5),0.0175);
        }
    }
}

void desenha_paredes_labirinto(int *arv){
    int i,j;

    //Desenha parede externa do labirinto
    desenha_linha(MAT2X(0.025), MAT2Y(0.025),MAT2X(0.025), MAT2Y(N-0.025),0);
    desenha_linha(MAT2X(0.025), MAT2Y(N-0.025),MAT2X(N-0.025), MAT2Y(N-0.025),0);
    desenha_linha(MAT2X(N-0.025), MAT2Y(0.025),MAT2X(N-0.025), MAT2Y(N-0.025),0);
    desenha_linha(MAT2X(0.025), MAT2Y(0.025),MAT2X(N-0.025), MAT2Y(0.025),0);

    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            int v1 = i * N + j;
            if(j+1 < N){
                int v2 = i * N + (j+1);
                if(arv[v2] != v1 && arv[v1] != v2){
                    desenha_linha(MAT2X(j+1), MAT2Y(i),
                                  MAT2X(j+1), MAT2Y(i+1),0);
                }
            }
            if(i+1 < N){
                int v2 = (i+1) * N + j;
                if(arv[v2] != v1 && arv[v1] != v2){
                    desenha_linha(MAT2X(j), MAT2Y(i+1),
                                  MAT2X(j+1), MAT2Y(i+1),0);
                }
            }
        }
    }
}

void inicia_animacao(LABIRINTO *lab){
    lab->idx = 0;
}

void desenha_procura_caminho(LABIRINTO *lab){
    int i1, i2, j1, j2;
    int cont = 0;
    while(cont <= lab->idx){
        i1 = lab->ar[cont].orig / N;
        j1 = lab->ar[cont].orig % N;

        i2 = lab->ar[cont].dest / N;
        j2 = lab->ar[cont].dest % N;

        desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                      MAT2X(j2+0.5), MAT2Y(i2+0.5),1);

        desenha_circulo(MAT2X(j1+0.5), MAT2Y(i1+0.5),0.0175);
        desenha_circulo(MAT2X(j2+0.5), MAT2Y(i2+0.5),0.0175);

        cont++;
        if(lab->ar[cont].orig == -1)
            break;
    }
    if(lab->idx < 4*N*N)
        lab->idx++;

}


void desenha_menor_caminho(LABIRINTO *lab){
    int v1, v2 = N*N-1;
    int i1, i2, j1, j2;
    int cont = 0;
    while(cont < lab->idx){
        v1 = lab->ant[v2];
        i1 = v1 / N;
        j1 = v1 % N;
        i2 = v2 / N;
        j2 = v2 % N;

        desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                      MAT2X(j2+0.5), MAT2Y(i2+0.5),1);

        desenha_circulo(MAT2X(j1+0.5), MAT2Y(i1+0.5),0.0175);
        desenha_circulo(MAT2X(j2+0.5), MAT2Y(i2+0.5),0.0175);

        cont++;
        v2 = v1;
        if(cont == lab->dist)
            break;

    }
    if(lab->idx < lab->dist)
        lab->idx++;
}

void desenha_busca_profundidade(LABIRINTO *lab){
    int v1, v2 = N*N-1;
    int i1, i2, j1, j2;
    int cont = 0;
    while(cont < lab->idx){
        v1 = lab->ph[cont].orig;
        v2 = lab->ph[cont].dest;

        i1 = v1 / N;
        j1 = v1 % N;

        i2 = v2 / N;
        j2 = v2 % N;
        if(lab->ph[cont].tipo == 0){
            desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                          MAT2X(j2+0.5), MAT2Y(i2+0.5),1);
        }else{
            desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                          MAT2X(j2+0.5), MAT2Y(i2+0.5),2);
        }

        desenha_circulo(MAT2X(j1+0.5), MAT2Y(i1+0.5),0.0175);
        desenha_circulo(MAT2X(j2+0.5), MAT2Y(i2+0.5),0.0175);

        cont++;
        v2 = v1;
        if(lab->ph[cont].orig == -1)
            break;
    }
    if(lab->idx < 8*N*N)
        lab->idx++;
}

void desenha_busca_largura(LABIRINTO *lab){
    int i1, i2, j1, j2;
    int cont = 0;
    //printf("busca_largura\n");
    while(cont <= lab->idx){
        i1 = lab->ar_largura[cont].orig / N;
        j1 = lab->ar_largura[cont].orig % N;

        i2 = lab->ar_largura[cont].dest / N;
        j2 = lab->ar_largura[cont].dest % N;

        desenha_linha(MAT2X(j1+0.5), MAT2Y(i1+0.5),
                      MAT2X(j2+0.5), MAT2Y(i2+0.5),1);

        desenha_circulo(MAT2X(j1+0.5), MAT2Y(i1+0.5),0.0175);
        desenha_circulo(MAT2X(j2+0.5), MAT2Y(i2+0.5),0.0175);

        cont++;
        //printf("cont = %d\n",cont);
        if(lab->ar_largura[cont].orig == -1)
            break;
    }
    if(lab->idx < 4*N*N)
        lab->idx++;

}

void desenha_labirinto(LABIRINTO *lab,int tipo){
    if(lab == NULL)
        return;

    switch(tipo){
        case 0: desenha_arvore_geradora(lab->arv);
                break;
        case 1: desenha_arvore_geradora(lab->arv);
                desenha_paredes_labirinto(lab->arv);
                break;
        case 2: desenha_paredes_labirinto(lab->arv);
                break;
        case 3: desenha_paredes_labirinto(lab->arv);
                desenha_procura_caminho(lab);
                break;
        case 4: desenha_paredes_labirinto(lab->arv);
                desenha_menor_caminho(lab);
                break;
        case 5: desenha_paredes_labirinto(lab->arv);
                desenha_busca_profundidade(lab);
                break;
        case 6: desenha_paredes_labirinto(lab->arv);
                desenha_busca_largura(lab);
                break;
        default: desenha_paredes_labirinto(lab->arv);
    }
}

 

//grafo.c

#include <stdio.h>
#include <stdlib.h>
#include "Grafo.h" //inclui os Protótipos

//Definição do tipo Grafo
struct grafo{
    int nro_vertices;
    int grau_max;
    int** arestas;
    int** pesos;
    int* grau;
};

Grafo* cria_Grafo(int nro_vertices, int grau_max){
    Grafo *gr;
    gr = (Grafo*) malloc(sizeof(struct grafo));
    if(gr != NULL){
        int i;
        gr->nro_vertices = nro_vertices;
        gr->grau_max = grau_max;
        gr->grau = (int*) calloc(nro_vertices,sizeof(int));

        gr->arestas = (int**) malloc(nro_vertices * sizeof(int*));
        gr->pesos = (int**) malloc(nro_vertices * sizeof(int*));
        for(i=0; i<nro_vertices; i++){
            gr->arestas[i] = (int*) malloc(grau_max * sizeof(int));
            gr->pesos[i] = (int*) malloc(grau_max * sizeof(int));
        }

    }
    return gr;
}

void libera_Grafo(Grafo* gr){
    if(gr != NULL){
        int i;
        for(i=0; i<gr->nro_vertices; i++){
            free(gr->arestas[i]);
            free(gr->pesos[i]);
        }
        free(gr->arestas);
        free(gr->pesos);
        free(gr->grau);
        free(gr);
    }
}

int insereAresta(Grafo* gr, int orig, int dest, int eh_digrafo, int peso){
    if(gr == NULL)
        return 0;
    if(orig < 0 || orig >= gr->nro_vertices)
        return 0;
    if(dest < 0 || dest >= gr->nro_vertices)
        return 0;

    gr->arestas[orig][gr->grau[orig]] = dest;
    gr->pesos[orig][gr->grau[orig]] = peso;
    gr->grau[orig]++;

    if(eh_digrafo == 0)
        insereAresta(gr,dest,orig,1,peso);
    return 1;
}

int procuraMenorDistancia(int *dist, int *visitado, int NV){
    int i, menor = -1, primeiro = 1;
    for(i=0; i < NV; i++){
        if(dist[i] >= 0 && visitado[i] == 0){
            if(primeiro){
                menor = i;
                primeiro = 0;
            }else{
                if(dist[menor] > dist[i])
                    menor = i;
            }
        }
    }
    return menor;
}

ARESTA* menorCaminho_Grafo(Grafo *gr, int ini, int *ant, int *dist){
    int i, pos, cont, NV, ind, *visitado, vert;
    cont = NV = gr->nro_vertices;
    visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++){
        ant[i] = -1;
        dist[i] = -1;
        visitado[i] = 0;
    }

    ARESTA *ar = (ARESTA*) malloc(4*NV * sizeof(ARESTA));
    for(i=0; i < 4*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
    }


    dist[ini] = 0;
    pos = 0;
    while(cont > 0){
        vert = procuraMenorDistancia(dist, visitado, NV);
        if(vert == -1)
            break;

        visitado[vert] = 1;
        cont--;
        for(i=0; i<gr->grau[vert]; i++){
            ind = gr->arestas[vert][i];

            ar[pos].orig = vert;
            ar[pos].dest = ind;
            pos++;

            if(dist[ind] < 0){
               dist[ind] = dist[vert] + 1;//ou peso da aresta
               ant[ind] = vert;
            }else{
                if(dist[ind] > dist[vert] + 1){
                    dist[ind] = dist[vert] + 1;//ou peso da aresta
                    ant[ind] = vert;
                }
            }
        }
    }

    free(visitado);
    return ar;
}

void arvoreGeradoraMinimaPRIM_Grafo(Grafo *gr, int orig, int *pai){
    int i, j, dest, NV, primeiro;
    int menorPeso;
    NV = gr->nro_vertices;
    for(i=0; i < NV; i++)
        pai[i] = -1;// sem pai

    pai[orig] = orig;
    while(1){
        primeiro = 1;
        for(i=0; i < NV; i++){//percorre todos os vértices
            if(pai[i] != -1){//achou vértices já visitado
                for(j=0; j<gr->grau[i]; j++){ // percorre os vizinhos do vértice visitado
                    if(pai[gr->arestas[i][j]] == -1){//achou vértice vizinho não visitado
                         if(primeiro){//procura aresta de menor custo
                            menorPeso = gr->pesos[i][j];
                            orig = i;
                            dest = gr->arestas[i][j];
                            primeiro = 0;
                         }else{
                             if(menorPeso > gr->pesos[i][j]){
                                menorPeso = gr->pesos[i][j];
                                orig = i;
                                dest = gr->arestas[i][j];
                             }
                         }
                    }
                }
            }
        }
        if(primeiro == 1)
            break;

        pai[dest] = orig;
    }
}


void buscaProfundidade(Grafo *gr, int ini, int dest, int *visitado, AR_PILHA* ar, int *cont, int *achou){
    int i;
    visitado[ini] = 1;
    for(i=0; i<gr->grau[ini]; i++){
        if(*achou == 1)
            return;

        if(!visitado[gr->arestas[ini][i]]){
            ar[*cont].orig = ini;
            ar[*cont].dest = gr->arestas[ini][i];
            ar[*cont].tipo = 0;
            (*cont)++;

            if(gr->arestas[ini][i] == dest){
                *achou = 1;
                return;
            }
            buscaProfundidade(gr,gr->arestas[ini][i],dest,visitado,ar,cont,achou);
            if(*achou == 0){
                ar[*cont].orig = ini;
                ar[*cont].dest = gr->arestas[ini][i];
                ar[*cont].tipo = 1;
                (*cont)++;
            }
            if(*cont > 8*gr->nro_vertices)
                printf("ERRO!!!\n");
        }
    }
}

AR_PILHA* buscaProfundidade_Grafo(Grafo *gr, int ini, int dest){
    int i, cont = 0, achou = 0;
    int NV = gr->nro_vertices;

    int *visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++)
        visitado[i] = 0;

    AR_PILHA *ar = (AR_PILHA*) malloc(8*NV * sizeof(AR_PILHA));
    for(i=0; i < 8*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
        ar[i].tipo = 0;
    }

    buscaProfundidade(gr,ini,dest,visitado,ar,&cont,&achou);
    free(visitado);
    return ar;
}

ARESTA* buscaLargura_Grafo(Grafo *gr, int ini){
    int i, vert, NV, cont = 1;
    int *fila, IF = 0, FF = 0;
    int ind, pos = 0;
    NV = gr->nro_vertices;

    int *visitado = (int*) malloc(NV * sizeof(int));
    for(i=0; i < NV; i++)
        visitado[i] = 0;

    ARESTA *ar = (ARESTA*) malloc(4*NV * sizeof(ARESTA));
    for(i=0; i < 4*NV; i++){
        ar[i].orig = -1;
        ar[i].dest = -1;
    }

    fila = (int*) malloc(NV * sizeof(int));
    FF++;
    fila[FF] = ini;
    visitado[ini] = cont;
    while(IF != FF){
        IF = (IF + 1) % NV;
        vert = fila[IF];
        cont++;
        for(i=0; i<gr->grau[vert]; i++){
            ind = gr->arestas[vert][i];
            if(!visitado[ind]){

                ar[pos].orig = vert;
                ar[pos].dest = ind;
                pos++;
                //printf("pos = %d\n",pos);

                FF = (FF + 1) % NV;
                fila[FF] = ind;
                visitado[ind] = cont;
            }
        }
    }
    free(fila);

    return ar;
}

 

Arquivo Modificado algumas coisas.

FONTES: Programação Descomplicada