Extras din laborator
Se citesc m perechi de numere întregi (x,y) reprezentând extremitatile muchiilor unui graf neorientat cu n vârfuri si m muchii.
Sa se verifice daca graful este eulerian tiparindu-se un mesaj.
Un graf este eulerian daca este conex si gradele tuturor vârfurilor sunt numere pare.
Reprezentarea datelor
Consideram ca exemplu graful de mai jos, cu n=8 vârfuri
În functia principala main se citesc: numarul de vârfuri n , numarul de muchii m , precum si cele m perechi de numere ce reprezinta extremitatile muchiilor grafului.
Elementele matricei de adiacenta se vor tipari pe monitor. Tot în acest modul vom apela functia conex ().
În functia conex() verificam daca graful este conex situatie în care vom apela functia grad(), iar daca graful nu este conex vom afisa un mesaj „graful nu este eulerian”.
Functia grad() verifica daca gradele tuturor vârfurilor sunt numere pare.
Programul aferent este:
#include<stdio.h>
#include<conio.h>
int a[20][20],n,m,x,y,i,j;
void conex();
void grad();
void main()
{
clrscr();
printf("Dati nr de muchii:");
scanf("%d",&m);
printf("Dati nr de varfuri:");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
for(i=1;i<=m;i++)
{do{
printf("n Dati muchia nr %d: ",i);
scanf("%d%d",&x,&y);
} while(x==y||x<1||x>n||y<1||y>n);
a[x][y]=1;
a[y][x]=1;
}
printf("nMatricea de adiacenta corespunzatoare este:nn");
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
printf("%2d",a[i][j]);
printf("n");
}
conex();
getch();
}
void conex()
{
int start,viz[20],c[20],pi,ps,z;
printf("nDati varful start:");
scanf("%d",&start);
for(i=1;i<=n;i++)
{viz[i]=0;
c[i]=0;
}
ps=1;
pi=1;
c[pi]=start;
viz[start]=1;
while(ps<=pi)
{
z=c[ps];
for(i=1;i<=n;i++)
if(a[i][z]==1&&viz[i]==0)
{pi++;
c[pi]=i;
viz[i]=1;
}
ps++;
}
if(pi==n)
grad();
else
printf("nGraful nu este eulerian");
}
void grad()
{
int grad,k;
k=0;
for(i=1;i<=n;i++)
Preview document
Conținut arhivă zip
- Structuri de Date si Algoritmi
- Grafuri.doc
- Lab10.doc
- Lab11.doc
- Lab2.doc
- Lab3.doc
- Lab4.doc
- Lab5.doc
- Lab6.doc
- Lab7.doc
- Lab8.doc
- liste.doc
Alții au mai descărcat și
1 INTRODUCERE Ce este un program? Un program este o listă de instrucțiuni date calculatorului pentru a le executa. Calculatorul va citi...
LUCRAREA 9 Scopul lucrarii îl constituie prezentarea tipurilor de date neomogene (structurile), utilizarea operatorului typedef în contextul...
Pentru testare se poate folosi urmatorul program: // include obiectele standard // pentru intrari/iesiri cu consola 1 #include <iostream> //...
1. Introducere in programarea calculatoarelor si prezentarea notiunii de algoritm Programarea calculatoarelor este procesul de proiectare,...
1. Prezentarea mediului de dezvoltare Microsoft Visual C++ 6.0 Microsoft Visual C++ 6.0 este mediul de dezvoltare integrat (Integrated Development...
Laborator nr. 1 Introducere in sistemul de operare Linux Surt istoric: Sistemul de operare UNIX a fost creat la Bell Laboratories in 1969, de...
Te-ar putea interesa și
Gestiunea unui magazin de piese auto Se va realiza un program care va permite accesul la operatii specifice gestionarii unui magazin de piese...
Motivatia alegerii temei. Utilitatea aplicatiei Am ales aceasta tema ca urmare a cerintelor avute la materia structuri de date si algoritmi,...
Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...
Un magazin de jucarii tine evidenta produselor cu ajutorul unui program pe claculator, care are ca structura de date un arbore AVL creat dupa cod....
1 Tema:Implimentarea tipului abstract de date.Tabloul de structuri. 2 Sarcina:De implimentat tipul abstract de date,tablou de structuri si de...
Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...
1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...
Lucrarea 1 Evaluarea si masurarea timpului de executie al unui algoritm 1.Definitia unui tip de date abstract - TDA Un TDA este un model...