Matricea lanturilor

Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii). Lui G i se asociaza matricea D numita matricea lanturilor, cu n linii si n coloane.

Astfel: D = (d_{i j}) _{n x n} cu:

1, daca exista lant de la i la j

d[i,j]=

0, altfel

Matricea lanturilor ca si matricea de adiacenta, in cazul grafurilor neorientate , este o matrice simetrica (daca exista lant de la i la j exista si lant de la j la i).

Grafului de mai jos i se asociaza urmatoarea matrice a lanturilor:

0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0

Linia k (sau coloana k) a matricei lanturilor ne arata nodurile j pentru care exista lant de k la j ( si de la j la k). Spre exemplu, pentru nodul 3 .

0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0

Nu se poate ajunge de la nodul 3 la nodurile 6 sau 7.

Problema:

Fiind dat un graf neorientat, memorat prin intermediul matricei de adiacenta, se cere sa se creeze si sa se tipareasca matricea lanturilor.

Se observa ca parcurgand in adancime (sau in latime) graful pornind de la nodul nod=3 spre exemplu vectorul de “vizitati” este:

1 1 1 1 1 0 0. Daca se inlocuieste viz[nod]=viz[3]=0 se obtine: 1 1 0 1 1 0 0 si se poate incarca linia 3 din matricea lanturilor cu continultul vectorului de vizitati. Prin urmare se parcurge df graful pornind de la fiecare nod in parte si se incarca de fiecare data continutul vectorului viz in matricea lanturilor in linia corespunzatoare. Iata o solutie:

#include<fstream.h>

#include<conio.h>

int a[20][20],n,m,viz[100],gasit,drum[20][20];

void dfmr(int nod)

{ viz[nod]=1;

for(int k=1;k<=n;k++)

if(a[nod][k]==1&&viz[k]==0)

dfmr(k);

}

void main()

{int x,y,j;

fstream f;

clrscr();

f.open("muchii.txt",ios::in); //citire matrice de adiacenta din fisier

if(f)

cout<<"ok!"<<endl;

else

cout<<"eroare la deschidere de fisier!";

f>>n>>m;

for(int i=1;i<=m;i++)

{f>>x>>y;

a[x][y]=a[y][x]=1;}

cout<<endl<<"matricea de adiacente"<<endl;

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

{for(j=1;j<=n;j++)

cout<<a[i][j]<<" ";

cout<<endl;}

int nod;

for(nod=1;nod<=n;nod++) //parcurgere graf incepand de la fiecare nod

{for(j=1;j<=n;j++)

viz[j]=0; //pentru fiecare nod se face vectorul viz in prealabil 0

dfmr(nod);

viz[nod]=0;

for(j=1;j<=n;j++) //incarcare vector viz in matrice drum

drum[nod][j]=viz[j];

}

cout<<endl<<"matricea drumurilor "<<endl;

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

{for(j=1;j<=n;j++)

cout<<drum[i][j]<<" ";

cout<<endl;}

getch();}