Scrieti programul C care va permite crearea unui graf neorientat implementat prin structuri de adiacenta metoda I cu vizualizare sub forma naturala!
Descriere algoritm
O alta maniera de reprezentar 242j99c e a unui TDA graf o constituie structurle de adiacenta (adjacency structures). In cadrul acestei reprezentari, fiecarui nod al grafului i se asociaza o lista de adiacente in care sunt inlantuite toate nodurile cu care acesta este conectat. In continuare se prezinta metode pentru implementarea grafurilor cu ajutorul structurilor de a adiacenta.
Metoda 1: Implementarea structurii de adiacenta se bazeaza in acest caz pe liste simplu inlantuite. Listele sunt construite in maniera obisnuita, cu un nod fictiv z pe post de fanion, a carui inlantuire indica nodul insusi.
Inceputurile listelor de adiacenta sunt pastrate intr-un tablou “StrAdi” indexat prin intemrediul nodurilor. Initial in acest tablou se introduce inlantuirile la nodurile fictive, urmand ca insertiile in lista sa fie de la “inceputul listei”.
Adaugarea unui arc care conecteaza nodul x cu nodul y in cazull acestui nod de reprezentare presupune in cazul grafurilor neorientate insertia nodului x in lista de adiacente a lui y si insertia lui y in lista de adiacente a nodului x.
Observatii: Un arc oarecare (x,y) este evidentiat in doua locuri in cadrul structurii (atat in lista de adiacenta a lui x, cat si in lista de adiacenta a lui y). Acest mod redundant de evidentiere isi dovedeste utilitatea in situatia in care se cere sa se determine intr-o maniera eficienta care sunt nodurile conectate de un anumit nod.
Pentru acest mod de prezentare conteaza ordinea in care sunt prezentate arcele (perechile de noduri) la intrare. Ordinea in care apar arcele in lista de adiacente afecteaza la randul ei ordinea in care arcele sunt prelucrate de catre algoritm .
Aceasta metoda necesita ca fiecare nod alocat sa contina un numar variabil de pointeri, depinzand de numarul de noduri cu care este adiacent.
Rezolvare:
Scrieti programul C care va permite crearea unui graf neorientat implementat prin structuri de adiacenta metoda I cu vizualizare sub forma naturala!
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<conio.h>
#include<ctype.h>
#include<dos.h>
#include<alloc.h>
#define R 200
#define r 15
#define pi M_PI
#define maxN 10
typedef char TipCheie;
struct adi
;
typedef struct adi Tadi;
typedef Tadi* PointAdi;
PointAdi StrAdi[maxN];
PointAdi z,v;
int n,k,i,j,x,y;
double xk,yk,x0,y0,x1,y1,x2,y2,xi,yi,xj,yj;
char s[2]=;
char n1,n2,c,op;
void Init_Mod_Grafic(void)
}/*Init_Mod_Grafic*/
void Desenare_Noduri(void)
delay(1000);
}/*Desenare_Noduri*/
int index(char c)
/*index*/
void Desenare_Graf(void)
}
}/*Desenare_Graf*/
void Creare_Graf(void)
}
printf('Mai adaugi arc?(D/N)');
fflush(stdin);
scanf('%c',&c);c=toupper(c);
}/*while*/
}/*Creare_Graf*/
void main(void)
//switch
}while(op!='E');
}/*functia principala*/
|
