Scrieti programul C care va permite crearea si vizualizarea unui graf implementat prin matricea de adiacenta varianta I. Se va afisa si matricea de adiacenta asociata grafului.

Scrieti programul C care va permite crearea si vizualizarea unui graf implementat prin matricea de adiacenta varianta I. Se va afisa si matricea de adiacenta asociata grafului.

1.    & 454j92e nbsp;   & 454j92e nbsp;   & 454j92e nbsp;  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 dea diacenta este o matrice patratica A[n][n] a.i.

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 indecsi 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 numenod – 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 I 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₂);

g[x][y] = 1;

g[y][x] = 1;

Exemplu: Fie graful si matricea lui de adiacenta

Rezolvare:

Scrieti programul C care va permite crearea si vizualizarea unui graf implementat prin matricea de adiacenta varianta I. Se va afisa si matricea de adiacenta asociata grafului.

#include<stdio.h>

#include<stdlib.h>

#include<graphics.h>

#include<math.h>

#include<conio.h>

#include<ctype.h>

#include<dos.h>

#define R 200

#define r 15

#define pi M_PI

#define maxN 20

int n,k,xk,yk,x0,y0,x1,y1,x2,y2,i,j;

char s[2]=;

char c1,c2,c,op;

int g[maxN][maxN];/*graful se confunda cu matricea de adiacenta*/

void Initializare(void)

/*Initializare*/

void Init_Mod_Grafic(void)

}/*Init_Mod_Grafic*/

void Desenare_Noduri(void)

delay(10);

}/*Desenare_Noduri*/

void Desenare_Graf(void)

}/*Desenare_Graf*/

void Afisare_Matrice(void)

}/*Afisare_Matrice*/

void main(void)

}

printf('Mai introduci arc?(D/N):');

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

}

cleardevice();

Desenare_Graf();

printf('Matricea de adiacenta asociata grafului este:n');

Afisare_Matrice();

printf('Tastati Enter!n');

getch();

closegraph();

}/*functia principala*/