Se da un graf orientat valoric. Se cere sa se scrie un program C care creaza si afiseaza graful in forma naturala si afiseaza matricea de adiacenta asociata grafului. Se va folosi implementarea prin matrice de adiacenta varianta a II-a.
Descrierea algoritmului
In cazul in care numarul de noduri ale grafului este fix, ceea ce presupune ca vom putea adauga noi arce sau suprima in structura de date de tip graf, dar nu si noduri, atunci tipurile de date folosite si variabilele utilizate in prelucrarea structurii de tip graf cu varianta II 2 vor fi urmatoarele:
#define NrNoduri 5
typedef char TipCheie;
typedef TipCheie TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
Functiile care vor descrie operatiile efectuate asupra structurii de tip graf astfel implementata vor presupune si testul daca exista arc intre 2 noduri x si y. Functia care realizeaza acest lucru este:
int Adiacent(TipEl x, TipEl y, Graf g)
/* Adiacent */
Functia index realizeaza corespondenta nume nod – indice de acces in matricea de adiacenta.
Grafurile orientate sunt simple restrictii ale grafurilor orientate, in sensul ca daca exista arc de la x la y, <x, y> se materializeaza punand pe linia corespunzatoare lui x si coloana corespunzatoare lui y in matricea Arce valoarea 1, dar nu si pe corespunzatoare lui y si coloana coreapunzatoare lui x.
In cazul grafurilor valorice stim ca fiecare arc are asociat un numar numit valoarea(costul) arcului, prin urmare in implementarea grafurilor valorice va trebui sa reprezentam si valoarea asociata fiecarui arc.
Tipurile de structuri de date si variabile folosite in implementarea unui graf valoric cu varianta II 2 vor fi urmatoare:
#define NrNoduri 5
typedef char TipCheie;
typedef int TipInfo;
typedef struct
TipEl;
typedef TipEl TipTabEl[NrNoduri];
typedef int TipVal;
typedef struct
TipArc;
typedef TipArc TipMatAdi[NrNoduri][NrNoduri];
typedef struct
Graf;
Graf g;
TipVal v;
Functii folosite in implementarea grafurilor valorice:
void InitGraf(Graf *g); - realizeaza initializarea grafului
void AdaugaV(TipEl x, TipEl y, TipVal v, Graf *g); - adauga un arc de la x la y de valoare v;
void Sterge(TipEl x, TipEl y, TipVal *v,Graf *g); - sterge arcul de la x la y(daca exista) si seteaza pe v la valoarea asociata grafului;
Rezolvare tema 1:
Se da un graf orientat valoric. Se cere sa se scrie un program C care creaza si afiseaza graful in forma naturala si afiseaza matricea de adiacenta asociata grafului. Se va folosi implementarea prin matrice de adiacenta varianta a II-a.
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <math.h>
#define R 130
#define r 15
#define pi M_PI
#define maxN 30
typedef char TipCheie;
typedef int TipVal;
typedef struct
TipAdi;
typedef TipCheie TipEl;
typedef int TipContor;
typedef TipEl TipTabEl[maxN];
typedef TipAdi TipMatAdi[maxN][maxN];
typedef int TipMat[maxN][maxN];
typedef struct
Graf;
typedef struct
TipArc;
double xi,yi,xj,yj,x1,y1,x2,y2,x3,y3,x0,y0,xk,yk,x,y;
double ALFA,ALFA1,ALFA2;
int n,k,i,j,a;
char s[2]=,c1,c2,c;
char sir[2];
Graf g;
TipArc IndiceArc;
TipEl e;
TipMatAdi Adi,Drum;
int IndiceNod;
TipVal v;
void Init_Mod_Grafic(void)
}//initmodgrafic
void DesenareNoduri(void)
}//DesenareNoduri
void DesenareGraf(void)
}//DesenareGraf
void Inser_Nod(Graf *g,TipEl e)
}/*Inser_Nod*/
void Inser_Arc(Graf *g,TipArc IndiceArc,TipVal val)
void Suprima_Nod(Graf *g, int IndiceNod)
g->Contor--;
} /* Suprima_Nod */
void Suprima_Arc(Graf *g,TipArc IndiceArc)
/*Suprima_Arc*/
int Cauta_Nod(Graf g,TipCheie Cheie)
/*Cauta_Nod*/
void Creare(void)
//crearea multimii arcelor
if(g.Contor==0)
printf('Nu exista noduri!n');
else
printf('Adaugi arc?(D/N)');
fflush(stdin);scanf('%c',&c);c=toupper(c);
}
}
}
}
void Afisare_Matrice(TipMatAdi A)
}/*Afisare_Matrice*/
int main(void)
}
DesenareGraf();
break;
case 'S': printf('Introduceti nodul de suprimat:');
fflush(stdin);scanf('%c',&e);e=toupper(e);
IndiceNod=Cauta_Nod(g,e);
if(IndiceNod!=-1)
Suprima_Nod(&g,IndiceNod);
else printf('Nodul nu exista in graf!n');
DesenareGraf();
break;
case 'D':if(g.Contor!=0)
}
else
printf('Graful este vid!n');
break;
case 'G': DesenareGraf();
break;
case 'M': Afisare_Matrice(g.Arce);
break;
case 'E': break;
default : printf('Optiune gresita!n');
break;
}
printf('Tastati Enter!n');
fflush(stdin);
getch();
}
while(op!='E');
return 0;
}
|
