Scrieti programul C care permite crearea, vizualizarea sub forma naturala a unui graf implementat cu matricea de adiacenta(varianta I)

Scrieti programul C care permite crearea, vizualizarea sub forma naturala a unui graf implementat cu matricea de adiacenta(varianta I).

Descrierea algoritmului.

In vederea prelucrarii unui graf cu ajutorul calculatorului graful trebuie sa fie transmis ca data de intrare algoritmului care realizeaza prelucrarea grafului. Stim ca un graf este precizat prin multimea nodurilor sale si prin multimea arcelor sale, de aceea prelucrarea grafului revine la a preciza cum sunt organizate cele 2 multimi.

Presupunem graful:

G = (N, A)

N = ; n -> nr. de noduri ale grafului

A = multimea arcelor.

Atunci in implemetarea grafului cu ajutorul matricei de adiacenta, matricea de adiacenta este o matrice patratica A[n][n] astfel incat:

True(1), daca exista (x, y)

A[x][y] =

False(0), daca nu exista (x, y)

Un prim pas in reprezentarea grafului cu ajutorul matricei de adiacenta consta in stabilirea unei corespondente intre numele nodurilor si indecsii de acces in matricea de adiacenta. Pentru o urmarire usoara a algoritmului de prelucrare a structurii de date TDA graf vom utiliza o tehnica implicita de corespondenta alegand drept nume pentru noduri litere ale alfabetului latin, iar corespondenta nume nod – index o vom face prin functia:

int index(char c)

/* index */

care intoarce ca valoare intregul ce reprezinta indexul de acces al nodului cu numele c.

Cel de-al doilea pas va consta in introducerea perechilor de noduri ce desemneaza arcele in vederea completarii matrcicei de adicenta. Se poate considera ca intr-un graf neorientat exista arc de la un nod la el insusi, lucru care se materializeaza prin a pune true(1) pe diagonala principala a matricei de adiacenta.

Varianta I

Intrucat graful este precizat prin multimea nodurilor si multimea arcelor in prima etapa va trebui sa introducem numele nodurilor grafului in vederea asocierii mai sus amintite, dupa care va trebui sa introducem perechile de noduri care desemneaza arcele.

Am fi putut realiza introducerea de la tastatura a matricei de adiacenta, dar acest lucru nu convine pentru matrici rare, de aceea vom opta pentru introducerea numelor nodurilor si a arcelor existente. Am convenit sa denumim nodurile prin litere consecutive lae alfabetului si deci etapa de introducere a multimii nodurilor poate sa lipseasca dat fiind faptul ca functia index imi realizeaza implicit corespondenta nume – index in matricea de adiacenta. De aceea in varianta I de implementare a grafului primul pas il vom inlocui cu introducerea numarului de noduri ale grafului(n) si prin precizarea numarului de arce ale grafului(m).

Pasul 2 – perechile de noduri (n₁, n₂)

x = index(n₁);

y = index(n₂);

Arce[x][y] = 1;

Arce[y][x] = 1;

Exemplu: Fie graful si matricea lui de adiacenta

Observatii:

1)Nodurile grafului sunt denumite prin primele n litere din alfabet.

i-indicele unui nod;

j-indicele celui de-al doilea nod;

2)In program se va face si validarea datelor.

Programul C:

#include <conio.h>

#include <graphics.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h> /* pentru functia exit din initializare_mod_grafic() */

#include <ctype.h> /* pentru functia toupper() */

#define PI 2*asin(1)

#define r 200

#define CALE 'c:BorlandcBGI'

#define maxN 10

int Arce[maxN][maxN];

char n1, n2;

void vizualizare_graf(int n, int a) /* n-nr. de noduri */

/* initializarea matricei de adiacenta */

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

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

Arce[x][y] = 0;

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

Arce[x][x] = 1;

for(i=1; i<=a; i++)

outtextxy(getmaxx()-430, getmaxy()-10, 'Apasati o tasta pentru a termina!');

getch();

closegraph();

}

void initializare_mod_grafic(void)

}/* initializare mod grafic */

void desenare(int n)

;

x0 = getmaxx()/2;

y0 = getmaxy()/2;

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

setcolor(WHITE);

}/* desenare */

int index(char c)

void main(void)

vizualizare_graf(n, a);

}/*main*/