Графы С++

[Fantazerishka]

Здравствуйте, есть задачка: Четыре трамвайных маршрута города представлены структурой типа граф. Узлы структуры соответствуют остановкам трамвайных маршрутов и дополнительно включают название остановок. Для двух названий остановок, введенных в режиме диалога с ЭВМ, найти все маршруты перемещения от первой остановки до второй с использованием не более одной пересадки.
Я её кое-как сделал, однако она не работает, вернее работает, но при определенных значениях, боюсь при защите не проканает, если у кого есть подобная программа поделитесь плиз, хочу посмотреть как она работает( Очень прошу

[[CODER]]

Лучше выложи свой код, так будет интереснее

[Fantazerishka]

Сообщение от [CODER]

Лучше выложи свой код, так будет интереснее

Тогда чур тапками не кидаться)

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <iomanip.h>

struct uzel
{
int nom;
uzel *next;
};

uzel *z,*vs,*t1,*t2,*t3;
uzel *p[13];
uzel *cpi[13];
bool nov[13];
int m[13];
int naz[10];
int mas[10];
int i,j,w,n,k,l2,x,y,o,beg,en,v,h,l,u,b,d,g,f;

int a[13][13] = {      0,    1,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,
                      1,    0,   1,1000,1000,   1,   1,1000,1000,1000,1000,1000,1000,
                   1000,    1,   0,   1,1000,1000,1000,1000,1000,   1,1000,   1,1000,
                   1000, 1000,   1,   0,   1,1000,1000,1000,1000,   1,   1,1000,1000,
                   1000, 1000,1000,   1,   0,1000,1000,1000,1000,1000,1000,1000,1000,
                   1000,    1,1000,1000,1000,   0,1000,1000,1000,1000,1000,1000,1000,
                   1000,    1,1000,1000,1000,1000,   0,   1,   1,   1,1000,1000,1000,
                   1000,1000,1000,1000,1000,1000,    1,   0,1000,1000,1000,1000,1000,
                   1000,1000,1000,1000,1000,1000,    1,1000,   0,1000,1000,1000,1000,
                   1000,1000,   1,   1,1000,1000,    1,1000,1000,   0,1000,1000,   1,
                   1000,1000,1000,   1,1000,1000, 1000,1000,1000,1000,    0,1000,1000,
                   1000,1000,   1,1000,1000,1000, 1000,1000,1000,1000,1000,    0,1000,
                   1000,1000,1000,1000,1000,1000, 1000,1000,1000,   1,1000,1000,    0};

int m1[11][9] = {0,1,2,3,4,100,100,100,100,
                 1,5,6,7,100,100,100,100,100,
                 2,9,11,12,100,100,100,100,100,
                 3,6,8,9,10,100,100,100,100,100,
                 0,1,2,3,4,5,6,7,100,
                 0,1,2,3,4,9,11,12,100,
                 0,1,2,3,4,6,8,9,10,
                 1,2,5,6,7,9,11,12,100,
                 1,3,5,6,7,8,9,10,100,
                 2,3,6,8,9,10,11,12,100};
int qwek[10][10];
void soz();
void vkls(uzel *t2);
void iskl(int &k);
void print();


int main()
{
soz();
print();

system("PAUSE");
return 0;
}

void soz()
{
for (i=0;i<13;i++)
{
z=new uzel;z->nom=i;t2=z;
for (j=0;j<13;j++)
if ((a[i][j]!=1000)&&(a[i][j]!=0))
{
t1=new uzel; t2->next=t1;t1->nom=j;t2=t1;
}
t1->next=0;
p[i]=z;
}
}

void vkls(uzel *t2)
{
  if (vs==0)
   { vs=new uzel;vs->nom=t2->nom;vs->next=0;
   }
   else
   {
   t1=new uzel;t1->nom=t2->nom;
   t1->next=vs;vs=t1;
   }
}

void iskl(int &k)
{
  if (vs!=0)
   { 
     k=vs->nom;
     t1=vs;
     vs=vs->next;
     delete t1;
   }
}

void print()
{
  x=0; o=1;
  cout<<"BBEDITE BEGIN UZEL"<<endl;
  cin>>beg;
  cout<<"BBEDITE END UZEL"<<endl;
  cin>>en;
  for (i=0;i<13;i++)
  {
   nov[i]=true;
   m[i]=0;
   cpi[i]=p[i];
  }
  vs=0;
  m[1]=beg; l=2;
  vkls(p[beg]);
  nov[beg]=false;
  nov[en]=false;
  i=beg;
  while (vs!=0)
  {
   do
   {
     if (cpi[i]->nom==en)
      { cout<<o<<"   "; o++;

       for (l2=1;l2<l;l2++) {cout<<m[l2]<<" "; qwek[x][l2]=m[l2];}
cout<<en<<endl; x++;

       }


    cpi[i]=cpi[i]->next;
   }
   while((cpi[i]!=0)&& (!nov[cpi[i]->nom]));
   if(cpi[i]!=0)
     if (nov[cpi[i]->nom])
       {
         i=cpi[i]->nom;
         vkls(p[i]);
         nov[i]=false;
         m[l]=i;
         l++;
       };
    if (cpi[i]==0)
       {
        iskl(k);
        l--;
        m[l]=0;
        nov[k]=true; cpi[k]=p[k];
       if (vs!=0) i=vs->nom;
       };
   }
 cout<<endl;
 
for (i=0;i<x;i++) 
{
for (l2=1;l2<10;l2++){
if ((l2>1 && qwek[i][l2]!=0)||(l2==1 && qwek[i][l2]>=0)) {cout<<qwek[i][l2]<<" ";}
                     }
cout<<en<<endl;
}
v=0;
for (i=0;i<10;i++) {h=0;
for (j=0; j<=8; j++) {
if (m1[i][j]==en && m1[i][j]==beg) {h++;}
if (h==2) {mas[v]=i; v++;}
                     }
                   }
g=0;
 for (i=0; i<x; i++) {u=0;
 for (f=0; f<=v; f++) {d=0;
for (l2=2; l2<12; l2++) {
for (j=0; j<=8; j++) {
//if (m1[mas[f]][j]==100) {f++;}
if (qwek[i][l2]>0) {u++;} //else {i++;}
if (qwek[i][l2]==m1[mas[f]][j]) {d++;}
if (u==d) {naz[g]=i+1; g++;}
}}}}
cout<<endl;
cout<<"Vozmojnie puti s odnoy peresadkoy:"<<endl;
for (b=0; b<g; b++) {if (naz[b+1]!=naz[b]) {cout<<naz[b]<<endl;}}

 cout<<endl;
}

[Fantazerishka]

Чую этот код взрывает мозг не только мне...((

[Evgenii90]

Я не силён в дискретке, но чую что граф не правильный даже...
P.S код действительно для разгона мозга!

[NiCola999]

представлять граф в виде односвязного списка не есть хорошо...

[Fantazerishka]

так вот мне бы типовой, чтобы понять что да как, если с комментариями то просто идеально будет)

[skiffter]

Нет граф правильный Evgenii90 ) Я его сам состовлял и проверил ))

[[CODER]]

В задании указанно что выводить нужно маршруты с одной и без пересадок, а у тебя выводит только те что находятся через одну вершину не зависимо от того были пересадки или нет.
Так будет точнее и компактней

			   for (i = 0; i < 10; i++) {
				   for (i = 0; i < 10; i++) {
						ms[i][j]=false;
				   }
			   }
				//       0    1    2    3    4    5    6    7    8    9   10   11   12         остановки
		mas[13][4] = {   1,   1,   1,   1,   1,1000,1000,1000,1000,1000,1000,1000,1000,  // 1   маршруты
					  1000,   1,1000,1000,1000,   1,   1,   1,1000,1000,1000,1000,1000,  // 2
					  1000,1000,1000,   1,1000,1000,   1,1000,   1,   1,   1,1000,1000,  // 3
					  1000,1000,   1,1000,1000,1000,1000,1000,1000,   1,1000,   1,   1}  // 4
					  for (i = 0; i < 13; i++) {
						  for (j = m; j < 4; j++) {
							 if (mas[i][j]==1){
								  ms[i][j]=true;
							 }
						  }
					  }

Получим матрицу типа

        	mass[][]={  0,  1,  2,  3,  4,
				 5,  1,  6,  7,
				 8,  6,  9,  3, 10,
				11,  2,  9,  12  }

Далее можно тупо перебрирать все варианты, т. к. матрица не большае, о времени можно и не думать (примеры есть в любом учебнике по структурам данных)

Пересадками считать количество прошедших сток, но не столбцов!!!
Например

                          0 => 12
			  0 - 1 - 6 - 9 - 12          // 3 пересадки
			  0 - 1 - 2 - 9 - 12          // 1 пересадка   	// выводим
			  0 - 1 - 2 - 3 - 9 - 12      // 2 пересадки

			  7 => 8
			  7 - 6 - 8  1    // 1 пересадка   // выводим

			  1 => 5
			  1 - 5    // 0 пересадок   // выводим

[Vago]

Джентльмены, кто мне, бестолковому, объяснит - каков физический смысл м-цы m1[][] в варианте автора, и по какому правилу она строилась?