Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define NRMAXNODURI 64
- #include <stdio.h>
- typedef struct
- {
- int nrNoduri;
- char tabChei[NRMAXNODURI];
- int tabVizitat[NRMAXNODURI];
- char matAdiacenta[NRMAXNODURI][NRMAXNODURI];
- }Graf;
- typedef struct
- {
- int nrElemente;
- int tabElemente[NRMAXNODURI];
- } Coada;
- void initializare(Graf &g)
- {
- int i,j;
- g.nrNoduri=0;
- for (i=0;i<NRMAXNODURI;i++)
- {
- g.tabChei[i]=0;
- g.tabVizitat[i]=0;
- }
- for (i=0;i<NRMAXNODURI;i++)
- {
- for(j=0;j<NRMAXNODURI;j++)
- {
- g.matAdiacenta[i][j]=0;
- }
- }
- }
- void reinitializare(Graf &g)
- {
- int i;
- for (i=0;i<NRMAXNODURI;i++)
- {
- g.tabVizitat[i]=0;
- }
- }
- void afisare(Graf g)
- {
- int i,j;
- printf("\nLista de chei;\n");
- for (i=0;i<g.nrNoduri;i++)
- {
- printf("%c ",g.tabChei[i]);
- }
- printf("\nMatricea de adiacenta:\n");
- for (i=0;i<g.nrNoduri;i++)
- {
- for(j=0;j<g.nrNoduri;j++)
- {
- printf("%d ",g.matAdiacenta[i][j]);
- }
- printf("\n");
- }
- }
- void adaugaNod(Graf &g,char cheie)
- {
- g.tabChei[g.nrNoduri]=cheie;
- g.nrNoduri++;
- }
- void adugaArc(Graf &g,int index1,int index2)
- {
- g.matAdiacenta[index1][index2]=1;
- g.matAdiacenta[index2][index1]=1;
- }
- void stergereArc(Graf &g,int index1,int index2)
- {
- g.matAdiacenta[index1][index2]=0;
- g.matAdiacenta[index2][index1]=0;
- }
- void traverseazaInAdancime2(Graf &g,int indexNod)
- {
- int i;
- if (!g.tabVizitat[indexNod])
- {
- printf("%c ",g.tabChei[indexNod]);
- g.tabVizitat[indexNod]=1;
- for (i=0;i<g.nrNoduri;i++)
- {
- if (g.matAdiancenta[indexNod][i])
- {
- traverseazaInAdancime2(g,i);
- }
- }
- }
- }
- void traverseazaInAdancime(Graf g)
- {
- int i;
- printf("\nTraversare in adancime:\n");
- for (i=0;i<g.nrNoduri;i++)
- {
- if (g.tabVizitat[i]==0)
- {
- traverseazaInAdancime2(g,i);
- printf("\n");
- }
- }
- printf("\n");
- }
- void initializare(Coada &coada)
- {
- int i;
- for (i=0;i<NRMAXNODURI;i++)
- {
- coada.tabElemente[i]=-1;
- }
- coada.nrElemente=0;
- }
- void adauga(Coada &coada,int indexNod)
- {
- //printf("Adauga %d\n", indexNod);
- coada.tabelemente[coada.nrElemente++]=indexNod;
- }
- int scoate(Coada &coada)
- {
- int i;
- int indexNod=coada.tabElemente[0];
- for (i=0;i<coada.nrElemente;i++)
- {
- coada.tabElemente[i]=coada.tabelemente[i+1];
- }
- coada.nrElemente--;
- //printf("Scoatem %d\n", indexNod);
- return indexNod;
- }
- int vida(Coada coada)
- {
- return coada.nrElemente==0;
- }
- void traverseazaPrinCuprindere2(Graf &g, int indexNod)
- {
- int i;
- Coada coada;
- initializare(coada);
- adauga(coada,indexNod);
- g.tabVizitat[indexNod]=1;
- do
- {
- indexNod=scoate(coada);
- printf("%c ",g.tabChei[indexNod]);
- for (i=0;i<g.nrNoduri;i++)
- {
- if (g.matAdiancenta[indexNod][i] && !(g.tabVizitat[i]))
- {
- g.tabVizitat[i]=1;
- adauga(coada,i);
- }
- }
- }
- while (!vida(coada));
- }
- void traverseazaPrinCuprindere(Graf g)
- {
- int i;
- printf("\nTraversare prind cuprindere:\n");
- for (i=0;i<g.nrNoduri;i++)
- {
- if (g.tabVizitat[i]==0)
- {
- traverseazaPrinCuprindere2(g,i);
- printf("\n");
- }
- }
- printf("\n");
- }
- int main()
- {
- Graf g;
- initializare(g);
- adaugaNod(g,'A');
- adaugaNod(g,'B');
- adaugaNod(g,'C');
- adaugaNod(g,'D');
- adaugaNod(g,'E');
- adaugaNod(g,'F');
- adaugaNod(g,'G');
- adaugaNod(g,'H');
- adaugaNod(g,'I');
- adaugaNod(g,'J');
- adaugaNod(g,'K');
- adaugaNod(g,'L');
- adaugaNod(g,'M');
- adaugaArc(g,0,1);
- adaugaArc(g,0,2);
- adaugaArc(g,0,3);
- adaugaArc(g,0,4);
- adaugaArc(g,1,2);
- adaugaArc(g,1,3);
- adaugaArc(g,2,3);
- adaugaArc(g,4,5);
- adaugaArc(g,5,6);
- adaugaArc(g,7,8);
- adaugaArc(g,9,10);
- adaugaArc(g,11,12);
- traverseazaInAdancime(g);
- reinitializare(g);
- traverseazaPrinCuprindere(g);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement