a Discreta(Lab.1)

download a Discreta(Lab.1)

of 13

Transcript of a Discreta(Lab.1)

MINISTERUL EDUCAIEI I TIINEI AL R.M

Lucrare de laborato Nr.1Tema: Pstrarea grafurilor n memoria calculatorului.

A elaborate: A verificat:

Studentul gr.MN-111 Belitei I..

Profesoara

Marusic G. .

Chisinau 2011

1.

SCOPUL LUCRRII

Studierea metodelor de definire a unui graf: matrice de inciden, matrice de adiacen, liste; Elaborarea unor proceduri de introducere, extragere i transformare a diferitor forme de reprezentare intern a grafurilor cu scoaterea rezultatelor la display sau imprimant.

2.

NOTE DE CURS

Metode de reprezentare a grafului Exist trei metode de baz de definire a unui graf: 1. Matricea de inciden; 2. Matricea de adiacen; 3. Lista de adiacen (inciden). Vom face cunotin cu fiecare dintre aceste metode. Matricea de inciden Este o matrice de tipul mxn, n care m este numrul de muchii sau arce (pentru un graf orientat), iar n este numrul vrfurilor. La intersecia liniei i cu coloana j se vor considera valori de 0 sau 1 n conformitate cu urmtoarea regul: 1 - dac muchia i este incident cu vrful j (dac arcul i "intr" n vrful j n cazul unui graf orientat); 0 - dac muchia (arcul) i i vrful j nu sunt incidente; -1 - numai pentru grafuri orientate, dac arcul i "iese" din vrful j. x1 x2 x3 x4 x5 x6 x7 u1 u2 u3 u4 u5 u6 u7 u8 -1 -1 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 1 0 0 -1 1 0 0 -1 0 1 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0

Fig. 3. Exemplu de matrice de inciden

Este uor de observat c aceast metod este de o eficacitate mic n sensul utilizrii memoriei calculatorului: fiecare linie conine doar dou elemente diferite de zero (o muchie poate fi incident cu nu mai mult de dou vrfuri). n limbajul C++ matricea de inciden poate fi redat printr-un tablou bidimensional mxn.

Matricea de adiacen Este o matrice ptrat nxn, aici n este numrul de vrfuri. Fiecare element poate fi 0, dac vrfurile respective nu sunt adiacente, sau 1, n caz contrar. Pentru un graf fr bucle putem observa urmtoarele:

diagonala principal este format numai din zerouri; pentru grafuri neorientate matricea este simetric fa de diagonala principal. x1 x2 x3 x4 x5 x6 x7 x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0

Fig. 4. Exemplu de matrice de adiacen Dup cum se de observa i n acest caz memoria calculatorului este utilizat nu prea eficace din care cauz matricea de adiacen ca i matricea de inciden se vor utiliza de obicei doar n cazul n care se va rezolva o problem concret pentru care reprezentarea grafului n aceast form aduce unele faciliti algoritmului respectiv. Pentru pstrarea grafurilor n memoria calculatorului (n deosebi, memoria extern) se va utiliza una din posibilitile de mai jos.

Lista de adiacen i lista de inciden Lista de adiacen este o list cu n linii (dup numrul de vrfuri n), n linia cu numrul i vor fi scrise numerele vrfurilor adiacente cu vrful i. Lista de inciden se definete analogic cu deosebirea c n linia i vor fi scrise numerele muchiilor (arcelor) incidente cu vrful i.Reprezentarea grafurilor prin intermediul acestor liste permite utilizarea mai eficace a memoriei calculatorului, ns aceste forme sunt mai complicate att n realizare, ct i n timpul procesrii. Pentru a lua n consideraie lungimea variabil a liniilor vor fi utilizate variabile dinamice i pointeri.

Vom exemplifica pentru un graf cu n vrfuri. Deoarece fiecare element al listei conine numere de vrfuri este evident s considerm c vom avea un ir de variabile dinamice de tip INTEGER care se vor afla n relaia respectiv de precedare (succedare). Aceast relaie se va realiza prin pointeri, unii mpreun cu variabila de tip ntreg n nregistrarea. Pentru a pstra indicatorii de intrare n aceste iruri se va folosi un tablou unidimensional de indicatori de lungime n. n calitate de simbol de terminare a irului se va utiliza un simbol care nu a fost folosit la numeraia vrfurilor (de exemplu 0), care va fi introdus n calitate de variabil de tip ntreg al ultimului bloc.

De exemplu, lista de adiacen : 1 - 3, 4, 0 2 - 3, 5, 6, 0 3 - 6, 7, 0 4 7, 0 5-0 6-0 7-0va avea urmtoarea reprezentare intern: 2 3 4 3 ^ 5 ^ 6 ^ 0

variabile dinamice (pointer i variabil de tip ntreg)

masiv de indicatori Fig. 5. Reprezentarea intern a listei de adiacen

Exemplu am graf cu 5 varfuri si 7 arce ( vezi fig1)

X

u3

X u6 u7

u2 X u4

u1 X u5 X

Fig.1 Reprezentarea grafica a grafului G

Xi x1 x2 x3 x4 x5Fig.2

F(xi) MA 2,0 x1 4,0 x2 2,4,0 x3 0 x4 1,2,3,0 x5

x1 0 0 0 0 1

x2 1 0 1 0 1

x3 0 0 0 0 1

x4 0 1 1 0 0

x5 0 0 0 0 0

MI u1 u2 u3Fig.1

x1 0 1 -1 0 0 0 0

x2 1 0 1 0 0 1 -1

x3 0 0 0 1 -1 -1 0

x4 0 0 0 0 1 0 1

x5 -1 -1 0 -1 0 0 0Fig.3

Matricea de adiacenta

u4 u5 u6 u7

Lista

Matricea de incidenta

3. SARCINA DE BAZ 1. Elaborai procedura introducerii unui graf n memoria calculatorului n form de matrice de inciden, matrice de adiacen i list de adiacen cu posibiliti de analiz a corectitudinii. 2. Elaborai proceduri de transformare dintr-o form de reprezentare n alta. 3. Folosind procedurile menionate elaborai programul care va permite: introducerea grafului reprezentat sub oricare din cele trei forme cu posibiliti de corecie a datelor;

pstrarea grafului n memoria extern n form de list de adiacen; extragerea informaiei ntr-una din cele trei forme la imprimant sau display.

Textul Programului:#include #include #include #include #include void setcolor(unsigned short color) { HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hcon,color); }

{ _m_incidenta[ac][i]=-1; _m_incidenta[ac][j]=1; } ac++; if(!_lista[i]) { _lista[i]=(LISTA*)malloc(sizeof(LISTA)); pos=_lista[i]; } else { pos>next=(LISTA*)malloc(sizeof(LISTA)); pos=pos->next; } pos->virf=j+1; pos->next=NULL; } } } *m_incidenta=_m_incidenta; *arcuri=_arcuri; *lista=_lista; return 1; }

typedef struct LISTA{ int virf; struct LISTA *next; }LISTA;

int din_adiacenta(int **m_adiacenta, int ***m_incidenta, LISTA ***lista,int virfuri,int *arcuri) { LISTA **_lista=NULL, *pos=NULL; int **_m_incidenta; int _arcuri=0, i, j, ac=0; for(i=0;inext=NULL; } } } } } } if(!din_lista(&m_adiacenta,&m_incidenta,li sta,virfuri,&arcuri)) { puts("\n Eroare !!!: Conversie esuata!"); getch(); } break; case 4: if(!m_adiacenta) puts(" Erorare !!!: Graful nu e introdus."); else { puts(" Reprezentarea grafului introdus in forma matricii de adiacenta:"); textcolor(RED); x=6; y=5; for(i=0;i