Imprimă pagina - Problema Drumuri C++

Titlul: Problema Drumuri C++
Scris de: Voicu Iulian din Octombrie 21, 2009, 18:01:11

Am nevoie sa modific urmatorul cod (care reprezinta parcurgerea in latime a unui graf) astfel incat inainte sa imi afizeze drumul (adica parcurgerea propriu-zisa) sa pot introduce in afara de nodul de pornire si un nod cautat!

Deci eu trebuie sa plec de la nodul X si sa ajung la Y...iar cand ajung la Y...sa ma opresc si sa afisez drumul parcurs!

Cod:

#include <iostream.h>
#include <conio.h>
void main (void)
{	
	int a[20][20],trecut[20],n,i,j,u,pc, m,e1,e2,x,sol[20];
	cout<<"numarul de noduri: ";
	cin>>n;
	cout<<"numarul de muchii: ";
	cin>>m;
	for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++)
	    a[i][j]=0;
	for (i=1;i<=m;i++)
	  {
	    cout<<"Muchia "<<i<<":\n";
	    cout<<"e1=";
	    cin>>e1;
	    cout<<"e2=";
	    cin>>e2;
	    a[e1][e2]=a[e2][e1]=1;
	  }
	for (i=1;i<=n;i++)
	  trecut[i]=0;
	cout<<"Nodul initial: ";
	cin>>x;
	pc=1;
	u=1;
	sol[1]=x;
	trecut[x]=1;
	while (u<n)
	  {
	    for (i=1;i<=n;i++)
	      if (a[sol[pc]][i] && !trecut[i])
		  {
		    u++;
		    sol[u]=i;
		    trecut[i]=1;
		  }
	    pc++;
	  }
	cout<<"Parcurgerea BFS:";
	for (i=1;i<=n;i++)
		cout<<sol[i]<<',';
	cout<<'\b';
getche();
}

Variabilele utilizate Ä«n programul C++

a - matricea de adiacenÅ£Äƒ asociatÄƒ grafului;

trecut -vector Ä«n care se trec Ä«n ordine nodurileâ€parcurseâ€;

n - numÄƒrul de noduri din graf;

m - numÄƒrul de muchii din graf;

e1,e2 - extremitÄƒÅ£ile muchiilor;

i,j - contori;

x â€“ nodul din care se â€žpleacÄƒâ€;

u - variabilÄƒ (contor) ce Å£ine evidenÅ£a numÄƒrului de noduri vizitate;

pc - nodul ai cÄƒrui vecini Ä«i cÄƒutÄƒm;

sol - vectorul rezultat Ä«n urma parcurgerii (conÅ£ine nodurile Ä«n ordinea vizitÄƒrii lor).

Titlul: RÄƒspuns: Problema Drumuri C++
Scris de: alexandru din Octombrie 21, 2009, 18:28:37

Adauga la conditia

Cod:

 u < n && !trecut[y]

Cat timp u < n si nu am trecut de y atunci continua :D
Mie mi se pare ca ai luat de undeva codul, sau nu l-ai inteles , faci tot algoritmul corect dar nu sti sa pui un stop ?

Titlul: RÄƒspuns: Problema Drumuri C++
Scris de: Voicu Iulian din Octombrie 21, 2009, 18:32:11

Citat din mesajul lui: alexandru din Octombrie 21, 2009, 18:28:37

Adauga la conditia

Cod:

 u < n && !trecut[y]

Cat timp u < n si nu am trecut de y atunci continua :D

si cum introduc nodul cautat....?
Trebuie sa introduc si nodul de plecare si nodul la care trebuie sa ajung(nodul cautat)...iar atunci cand am ajuns la nodul cautat trebuie sa afisez prin ce noduri am trecut pana atunci

dupa cout<<"nodul initial: ";
cin>>x;

scriu cout<<"nodul cautat: "
cin>>y;

Deci conditia de oprire este ajungerea la nodul cautat...si afisarea celorlalte noduri prin care am trecut! si atat

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Voicu Iulian din Octombrie 21, 2009, 18:01:11