Laborator 10 - Reprezentarea si traversarea grafurilor + Algoritmi pentru prelucrarea grafurilor (6 mai)

Explorarea în lărgime

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

typedef struct Nod{
    int cheie;
    struct Nod *urm;
    } nod;

void adauga_coada(nod **prim, int s)
{
    nod*p=NULL;
    p=(nod*)malloc(sizeof(nod));
    p->cheie=s;
    p->urm=NULL;

    if(*prim==NULL)
        *prim=p;
    else
    {
    nod*q=NULL;
    q=*prim;
    while(q->urm!=NULL)
        q=q->urm;
    q->urm=p;
    p->urm=NULL;
    }
}

void sterge_coada(nod **prim)
{
    nod*p=*prim;
    (*prim)=(*prim)->urm;
    free(p);
}

void largime(int a[][20],int n, int s)
{
    nod *prim=NULL;
    int viz[20];
    int i;
    for(i=0;i<n;i++)
        viz[i]=0;
    viz[s]=1;
    printf("%d ",s);
    adauga_coada(&prim,s);
    while(prim!=NULL)
    {
        int v=prim->cheie;
        int w=0;
        for(w=0;w<n;w++)
        {
            if(a[v][w]==1 && viz[w]==0)
            {
                viz[w]=1;
                printf("%d ",w);
                adauga_coada(&prim,w);
            }
        }
        sterge_coada(&prim);
    }
}

int main()
{
    int n,a[20][20],i,j,ok=1;
    FILE *f;
    f=fopen("date.txt","r");
    fscanf(f,"%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        a[i][j]=0;
    while(ok>0)
    {
        ok=fscanf(f,"%d,%d ",&i,&j);
        a[i][j]=a[j][i]=1;
    }
    printf("Nod de start: ");
    int p;
    scanf("%d",&p);
    largime(a,n,p);
    printf("\nApasati o tasta pentru iesire");
    getch();
    return 0;
}

date.txt

8
0,1 0,2 0,3
1,3 1,5 1,6
2,3 2,4
6,7

Explorarea în adâncime

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

typedef struct Nod
{
    int cheie;
    struct Nod *urm;
} nod;

void adauga_stiva(nod **vf, int x)
{
    nod*p;
    p=(nod*)malloc(sizeof(nod));
    p->cheie=x;
    p->urm=*vf;
    *vf=p;
}

void sterge_stiva(nod **vf)
{
    nod *x;
    x=(*vf);
    (*vf)=(*vf)->urm;
    free(x);
}

void adancime(int a[][20],int n, int s)
{
    nod *prim=NULL;
    int viz[20];
    int i,w,v;
    for(i=0; i<n; i++)
        viz[i]=0;
    viz[s]=1;
    printf("%d ",s);
    adauga_stiva(&prim,s);
    while(prim!=NULL)
    {
        v=prim->cheie;
        w=0;
        for(w=0;w<n;w++)
        {
            if(a[v][w]==1 && viz[w]==0)
                break;
        }
        if(w<n)
        {
            viz[w]=1;
            printf("%d ",w);
            adauga_stiva(&prim,w);
        }
        else sterge_stiva(&prim);
    }
}

int main()
{
    int n,a[20][20],i,j,ok=1;
    FILE *f;
    f=fopen("date.txt","r");
    fscanf(f,"%d",&n);
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            a[i][j]=0;
    while(ok>0)
    {
        ok=fscanf(f,"%d,%d ",&i,&j);
        a[i][j]=a[j][i]=1;
    }
    printf("Nod de start: ");
    int p;
    scanf("%d",&p);
    adancime(a,n,p);
    printf("\nApasati o tasta pentru iesire");
    getch();
    return 0;
}

date.txt

8
0,1 0,2 0,3
1,3 1,5 1,6
2,3 2,4
6,7

Algoritmul lui Dijkstra. Algoritmul lui Dijkstra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf.

#include <stdio.h>
#include <stdlib.h>
void dijkstra (int n,int a[][100])
{
    int tata[n],cost[n][n],dist[n],s[n],i,j,pas,k,q,minim;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i==j)
                cost[i][j]=0;
            else
                if (a[i][j])
                    cost[i][j]=a[i][j];
                else
                    cost[i][j]=100000;
    for (i=1;i<=n;i++)
    {
        s[i]=0;
        dist[i]=cost[1][i];
        if (dist[i]<100000)
            tata[i]=1;
        else
            tata[i]=0;
    }
    s[1]=1;
    tata[1]=0;
    for (i=1;i<n;i++)
    {
        minim=100000;
        for (q=1;q<=n;q++)
            if (dist[q]<minim && dist[q])
            {
                minim=dist[q];
                k=q;
            }

        if (k==100000)
            return;
        s[k]=1;
        for (j=1;j<=n;j++)
            if (s[j]==0 && dist[k]+cost[k][j]<dist[j])
            {
                dist[j]=dist[k]+cost[k][j];
                tata[j]=k;
            }
    }
    for (i=2;i<=n;i++)
        printf("%d - %d\n",dist[i],tata[i]);
}

int main()
{
    int a[100][100],n,m,i,x,y,c,j;
    FILE *f;
    f=fopen("date.txt","r");

    fscanf(f,"%d %d\n",&n,&m);
    for (i=0;i<m;i++)
    {
        fscanf(f,"%d %d %d\n",&x,&y,&c);
        a[x][y]=c;
    }
    dijkstra(n,a);
    return 0;
}

date.txt

10 8
1 2 9
1 3 1
1 4 3
1 7 9
3 5 2
3 6 5
4 7 5
5 2 4
5 6 1
6 7 1
8 4 1
8 6 4
8 7 2