Scrieti programul C care va permite crearea si vizualizarea unui graf implementat prin structura de adiacenta metoda I cu vizualizare naturala a grafului. Pentru un nod sa se precizeze care sunt toate nodurile adiacente lui.

Descriere algoritm

In implementarea grafurilor prin structuri de adiacenta fiecarui nod al grafului i se asociaza o lista a nodurilor adiacente lui (multimea arcelor se va reprezenta prin tipul pointer). Pentru aceasta varianta de implementare a grafurilor exista doua metode. Prez 444b17e entam mai jos Metoda I.

Metoda I

Presupunem asocierea fiecarui nod al grafului a listei de adiacenta formata din nodurile adiacente lui. Cu alte cuvinte fiecarui nod al grafului i se asociaza o lista liniara simplu inlantuita formata din nodurile adiacente lui.

Fig. 1

Listele de adiacenta sunt construite dupa ideea construirii listelor liniare cu un nod fictiv (fanion), inceputurile listei de adiacenta fiind memorate intr-un tablou StrAdi, iar crearea listei liniare simplu inlantuite se va face dupa tehnica de creare cu inserare in fata listei.

Tabloul StrAdi va fi indexat dupa multimea nodurilor grafului. Presupunem ca fiecare nod al grafului este desemnat print-o litera din alfabetul latin (primele n litere).

Pentru a realiza corespondenta intre numele nodului si indexul nodului respectiv in tabloul structurii de adiacenta, vom defini o functie Index. Deci, multimea nodurilor grafului nu este reprezentata explicit in memoria calculatorului, ci doar prin pozitiile lor in cadrul structurilor de adiacenta.

In implementarea grafurilor cu ajutorul structurilor de adiacenta metoda I, fiecare arc al grafului (x,y), daca graful este neorientat va fi evidentiat atat in lista de adiacenta a lui x cat si in lista de adiacenta a lui y.

Structurile de date prin care vom realiza o astfel de implementare sunt: tabloul: structura de adiacenta e un tablou de pointeri catre inceputurile listei liniare simplu inlantuite ale nodurilor adiacente corespunzatoare nodului respectiv.

Un alt tip de date este structura de date de tip lista liniara simplu inlantuita cu nod fictiv pe post de fanion creata dupa tehnica de creare cu inserare in fata listei.

Structurile de date si variabilele care implementeaza graful in aceasta varianta sunt:

#define MaxN 10;

typedef int TipCheie;

struct adi

;

typedef struct adi Tadi;

typedef Tadi * PointAdi;

PointAdi StrAdi[MaxN];

PointAdi v,z;//v-pointer auxiliar

char n1,n2,c;

int x,y,i,n;

Functia care realizeaza corespondenta intre indice si numele nodului este:

int Index(char c)

/*Index*/

Observatii:

Precizarea unui arc de la x la y se face in doua locuri: in lista de adiacenta a lui x si precizarea arcului de la y la x plasand nodul y in lista de adiacenta a lui x. Acest mod redundant de precizare a unui arc isi motiveza utilitatea doar in cazul in care ni se cere sa precizam intr-un mod eficient lista tuturor nodurilo adiacente ale unui nod dat.ordinea de introducere a nodurilor in listele de adiacenta este importanta pentru ca in acea ordine vor fi prelucrate. Prin urmare in functie de natura algoritmului de prelucrare aceasta ordine in care am introdus arcele poate sa afecteze sau nu rezultatul.

Vom defini de fiecare data o functie care realizeaza corespondenta intre numele nodului si indexul nodului respectiv

Inlantuirea nodului fictiv indica tot nodul fictiv.

Convenim ca in lista de adiacenta sa memoram cheile de adiacenta prin indexul nodului respectiv in tabloul structurii de adiacenta.

Rezulta asadar ca pentru un graf dat implementat prin structuri de adiacenta metoda I avem mai multe structuri de adiacenta in functie de ordinea introducerii arcelor.

Programul C:

#include<stdio.h>

#include<stdlib.h>

#include<graphics.h>

#include<math.h>

#include<ctype.h>

#include<conio.h>

#include<string.h>

#include<alloc.h>

#define R 200

#define r 20

#define MaxN 6

#define pi M_PI

#define cale 'c:borlandcbgi'

typedef int TipCheie;

struct adi

;

typedef struct adi Tadi;

typedef Tadi * PointAdi;

PointAdi StrAdi[MaxN];

PointAdi p,v,z,q;

double x0,y0,xi,xj,yi,yj;

char n1,n2;

int i,j,a,n,x,y;

void init_mod_grafic(void)

}/*init_mod_grafic*/

void AfisareNoduri(void)

;

x0=(getmaxx()/2)+80;

y0=getmaxy()/2;

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

}/*AfisareNoduri*/

void Traversare(PointAdi p)

q=q->UrmAdi;

}/*Traversare*/

void AfisareGraf(void)

}/*AfisareGraf*/

int Index(char c)

/*Index*/

void Creare(void)

printf('Introduceti al doilea nod: ');

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

y=Index(n2);

while((y<0)||(y>=n))

v=(PointAdi)malloc(sizeof(Tadi));

v->cheie=x;

v->UrmAdi=StrAdi[y];

StrAdi[y]=v;

v=(PointAdi)malloc(sizeof(Tadi));

v->cheie=y;

v->UrmAdi=StrAdi[x];

StrAdi[x]=v;

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

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

}

}/*Creare*/

void main(void)

/*main*/