limbajul c

by

Grafuri neorientate – drumul optim intr-un graf

Una din problemele care apar foarte des în practică este găsirea drumului optim între două noduri ale unui graf.

Formalizarea problemei drumului optim este următoarea:

“Fiind dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)”.

Valoarea unui drum este dată de suma valorilor arcelor care îl compun. Pentru problema drumului optim s-au elaborat mai multe categorii de algoritmi, după cum urmează:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell)
Algoritmi prin ajustări succesive (Ford)
Algoritmi prin inducţie (Dantzig)
Algoritmi prin ordonare prealabilă a vârfurilor grafului
Algoritmi prin extindere selectivă (Dijkstra)

by

Grafuri neorientate – implementarea unui graf utilizand pointeri

Pentru a defini un graf utilizând pointeri, vom defini următoarele structuri:
typedef struct NODL
{
  //nodul adiacent indicat
  struct NODG *nod;
  //pointer spre următorul nod în lista de adiacenţe
  struct NODL *urml;
} nodl;

typedef struct NODG
{
  int cheie;
  … informaţii
  //începutul şi sfârşitul listei de adiacenţă
  struct NODL *inc_lista, *sfarsit_lista;
  //pointer spre următorul nod al grafului
  struct NODG *urmg;
} nodg;

//începutul şi sfârşitul listei de noduri din graf
struct nodg *incG, *sfG;

by

Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta


//definirea tipului nod
typedef TIP_NODG
{
  int cheie;
  ... informaţii
} tip_nodg;
ntip_nodg nod[Nmax];
//tabloul de noduri
//Nmax este numărul maxim de noduri
int arc[N max] [N max];
//matricea de adiacenţă

Adăugarea unui nod cu cheia key:
int i;
nod[N].cheie=key;
//adăugăm nodul N+1
for(i=0;i <= N;i++)   arc[i][N]=arc[N][i]=0; //iniţalizarea cu o a conexiunilor cu celelalte noduri N++; //incrementarea numărului de noduri Continue reading →

by

Grafuri neorientate – euleriene

Fiind dat un graf neorientat, să se determine dacă este eulerian, iar dacă răspunsul este afirmativ, să se determine toate ciclurile euleriene care încep dintr-un nod dat.

Pentru a rezolva această problemă, vom parcurge următorii paşi:
• se determină dacă graful este conex
• se determină dacă fiecare nod are grad par


#include "stdio.h"
#include "conio.h"
int a[10][10],viz[10],n,m;
//parcurgere in adâncime
void df_r(int nod)
{
  int k;
  //afişăm nodul curent ca vizitat
  printf("%d ",nod);
  //marcăm nodul curent ca vizitat
  viz[nod]=1;
  //pentru fiecare nod k
  for(k=1;k <= n;k++)     //dacă există muchie între nodul curent şi nodul k şi nodul k nu a fost incă vizitat,     //apelăm funcţia recursivă de vizitare depth first df_r având ca parametru nodul k     if(a[nod][k] && !viz[k])       df_r(k); } Continue reading →

by

Grafuri neorientate – hamiltonian

Se citeşte matricea de adiacenţă a unui graf. Să se determine dacă graful este hamiltonian.

Soluţie: vom folosi metoda backtracking, aplicată asupra unei stive în care vom păstra nodurile care compun lanţul. Vom porni de la primul nod şi vom putea adăuga în stivă doar un nod adiacent. De asemenea, nodul adăugat nu trebuie să se regăsească pe nivelurile anterioare. Dacă am atins în stivă numărul total de noduri iar nodul final este adiacent cu nodul iniţial, am găsit soluţia problemei.


#include "stdio.h"
#include "conio.h"
int stiva[100],n,m,k,nr_solutii,a[20][20];
int verifica()
{
  int i;
  if(k>1)
    //dacă a[st[k-1]][st[k]] este 0 returnăm 0
    if(!a[stiva[k-1]][stiva[k]])
       return 0;
    else
      //dacă a [stiva[k-1]][stiva [k]] este 1 căutam pe toate nivelurile
      //anterioare nivelului curent
      for(i=1;i <= k-1;i++)         //dacă nodul curent se găseşte pe unul din nivelurile         //anterioare returnăm 0         if(stiva[i] == stiva[k])           return 0;         //dacă stiva conţine toate nodurile grafului         if(k == n)           //iar ultimul nod nu este adiacent cu primul nod returnăm 0           if(!a[stiva[1]][stiva[k]])             return 0;   return 1; } Continue reading →