Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

 
CATEGORII DOCUMENTE
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Implementarea grafurilor cu ajutorul matricei de adiacenta

c

+ Font mai mare | - Font mai mic


DOCUMENTE SIMILARE

Trimite pe Messenger
Operatii cu liste liniare dublu inlantuite
Sortarea prin metoda 'bubble sort' - optimizare
Liste dublu legate
Citirea si afisarea datelor. Primele programe in C++
crearea unei liste liniare si determinarea primului element par
crearea unei liste predefinite cu 3 elem
crearea unei liste liniare prin citirea informatiilor din noduri
Liste circulare
Expresii si operatori
Instructiunea SWITCH

TERMENI importanti pentru acest document

matrice de adiacenta c :

Implementarea grafurilor cu ajutorul matricei de adiacenta

         Tema nr. 5:

         Scrieti programul C care permite crearea si vizualizara sub forma naturala a unui graf implementat cu ajutorul matricei de adiacenta varianta I. (Se va afisa si matricea de adiacenta)

         Analiza:

         Un graf este format dintr-o multime de noduri (varfuri) si o multime de arce (muchii). Astfel, vom nota  graful ce are multimea nodurilor  ( este numarul de noduri ale grafului), si multimea arcelor .

         Matricea de adiacenta este o matrice patratica de ordinul , cu elemente booleene, in care elementul de pe pozitia  este TRUE d.n.d. exista arc de la nodul  la nodul , adica matricea definita astfel:

         Deoarece limbajul C nu are definit tipul de date boolean, in implementarea acestei matrice intr-un progam C vom folosi in locul valorilor TRUE si FALSE valorile 1 si respectiv 0.

         Un prim pas pe care trebuie sa-l realizam in implementarea grafurilor cu ajutorul matricei de adiacenta este stabilirea unei corespondente intre numele nodurilor si indicii de acces ai nodurilor in matricea de adiacenta. Aceasta corespondenta poate fi stabilita implicit prin alegerea corespunzatoare a tipului de baza al multimii nodurilor, sau explicit prin realizarea unei asocieri definita pe multimea nodurilor cu valori in multimea intregilor (care sunt indicii de acces ai nodurilor in cadrul matricei de adiacenta).

         Pentru usurinta descrierii algoritmilor de prelucrare a grafurilor, in cele ce urmeaza vom denumi nodurile prin litere consecutive ale alfabetului latin, in acest caz putand realiza conversia directa de la tipul nodului (caracter) la tipul intreg prin functii specifice de limbaj.

         Functia C care realizeaza aceasta conversie o vom denumi index, si o definim astfel:

int index(char c)

    /* index */

         In prelucrarea grafurilor implementate cu ajutorul matricei de adiacenta putem considera ca fiecare nod este legat cu el insusi, ceea ce se realizeaza in matricea de adiacenta prin valoarea TRUE pe diagonala principala. Acest lucru nu este insa obligatoriu, putand fi precizat de la caz la caz.

         Exemplu: Sa consideram graful:

         Multimea nodurilor este

         Putem construi urmatorul tabel:

A

B

C

D

A

x

x

x

B

x

x

x

x

C

x

x

x

D

x

x

unde am marcat cu „x” existenta arcului de la nodul ce da numele liniei la nodul ce da numele coloanei, deci matricea de adiacenta este:

         Deoarece un graf este precizat prin multimea nodurilor si multimea arcelor, in cazul prelucrarii grafului cu ajutorul unui sistem de calcul graful va fi o data de intrare, deci va trebui sa stim care sunt modalitatile de reprezentare a celor doua multimi. Cel mai simplu mod de a realiza acest lucru este de a citi direct matricea de adiacenta (de la intrare), insa acest lucru nu este eficient in cazul matricelor rare, de aceea se obisnuieste ca intr-o prima etapa sa se precizeze multimea nodurilor grafului, iar in cea de-a doua etapa sa precizam multimea nodurilor care imi definesc arcele.

         In cazul reprezentarii implicite a grafului cu ajutorul matricei de adiacenta prima etapa poate sa lipseasca (nu ne intereseaza care este numele nodurilor, ci numai cate sunt), urmand doar sa precizam multimea de noduri care imi dau arcele, ordinea nefiind importanta.

         Programul:

#include <conio.h>

#include <graphics.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h> // for exit

#include <ctype.h>  // for toupper

#define PI 2*asin(1)

#define R 200  //raza cercului mare (imaginar)

#define r 20     //raza cercului mic (nodul)

#define CALE 'C:BORLANDCBGI'

#define nMax 10 //nr max de noduri admise

int g[nMax][nMax];

int i,j,k,n;

char n1,n2;

int x0,y0,xi,yi,xj,yj,x,y;

void initializare_mod_grafic(void);

void desenare(int n);

int index(char c);

void afisare_matrice(void);

void sterge(void);

void main(void)

 

    initializare_mod_grafic();

    desenare(n);

    for(i=0;i<n;i++)

      for(j=0;j<n;j++)

            g[i][j]=0;  //initializarea elem matricei de adiacenta

    for(i=0;i<n;i++)

      g[i][i]=1;  //pres ca exista arc de la un nod la el insusi

    printf('nIntroduceti arce? (D/N) ');

    fflush(stdin);  scanf('%c',&ch);  ch=toupper(ch);

    while(ch=='D')

     

            printf('Al doilea nod: ');

            fflush(stdin); scanf('%c',&n2);

            j=index(n2);

            if((j<0) || (j>=n))

             

            g[i][j]=1;

            g[j][i]=1;  // pres ca graful nu e orientat

            xi = x0 + R*cos(2*i*PI/n);

            yi = y0 - R*sin(2*i*PI/n);

            xj = x0 + R*cos(2*j*PI/n);

            yj = y0 - R*sin(2*j*PI/n);

            setcolor(WHITE);

            line(xi,yi,xj,yj);

            afisare_matrice();

            alt_arc:

            sterge();

            gotoxy(1,2);

            printf('Mai introduceti un arc? ');

            fflush(stdin);  scanf('%c',&ch);  ch=toupper(ch);

      }

    sterge();

    gotoxy(1,2);

    printf('Asta a fost tot. Bye!n');

    afisare_matrice();

    getch();

    closegraph();

  } /* main */

void initializare_mod_grafic(void)

 

  }  /* initializare_mod_grafic */

void desenare(int n)

  ;

    x0 = getmaxx()/2+90; //'deplasam' graful spre dreapta pt a putea reprez mat de adi

    y0 = getmaxy()/2;

    for(k=0; k<n; k++)

     

    setcolor(WHITE);

  }  /* desenare */

int index(char c)

    /* index */

void afisare_matrice(void)

 

  } /* afisare_matrice */

void sterge(void)

 

         Observatii:

1)     Varianta I de implementare a unui graf cu ajutorul matricei de adiacenta este destul de „slaba” deoarece matricea de adiacenta a grafului si reprezentarea fizica a acestuia (desenul) nu sunt „legate” (daca modificam matricea de adiacenta nu o sa se modifice si reprezentarea fizica a grafului). Din acest motiv:

·        Nu se pot adauga noi noduri grafului pe durata rularii programului

·        Nu se pot sterge noduri ale grafului

·        Nu se pot sterge arce dupa ce au fost adaugate

·        Numele nodurilor vor fi litere consecutive ale alfabetului, neexistand posibilitatea denumirii arbitrare a nodurilor, sau posibilitatea ca nodurile sa contina si informatii.

         Astfel, in momentul introducerii unui nou arc desenul se modifica in acelasi timp cu matricea de adiacenta, insa fara o legatura fizica intre ele, ceea ce ne duce cu gandul la tema laboratorului anterior, in care am realizat un desen care simula reprezentarea naturala a unui graf, si astfel putem spune ca acest program mimeaza un graf real.

         Deci avem nevoie de o implementare mai puternica si mai flexibila a unui graf, care o vom introduce in laboratorul urmator

2)     Din motive de design am ales ca graful sa nu mai fie pozitionat exact in centrul ecranului, ci l-am deplasat spre dreapta pentru a putea afisa matricea de adiacenta in coltul din stanga jos al ecranului, astfel putem urmari in momentul in care introducem un nou arc cum se modifica desenul si matricea de adiacenta. Tot din motive de design am pastrat modul de interogare cu privire la introducerea de noi arce din seminarul anterior, fara nici o modificare.

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 716
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Distribuie URL

Adauga cod HTML in site

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2014. All rights reserved