Mình nhập vào 1 ma trận kề (nếu có cạnh kề thì nhập số 1 ngược lại nhập số 0), duyệt đồ thị theo chiều sâu bằng stack nhưng chỉ xuất kết quả là số 1. không biết sai ở đâu? mong các a pro chỉ giúp ạ! thanks nhìu nhìu
C++ Code:
  1. #include <iostream.h>
  2. #include <iomanip.h>
  3. #include <stdlib.h>
  4.  
  5. #define max 100
  6. int danhdau[max];
  7. ////////////
  8. struct DoThi
  9. {
  10.     int mtke[max][max];
  11.     int n;
  12. };
  13. DoThi G;
  14.  
  15. struct Stack
  16. {
  17.     int key;
  18.     Stack *next;
  19. };
  20. Stack *st;
  21. //*************************************
  22.  
  23. int Menu();
  24. void Run( int task);
  25.  
  26. void Nhap(DoThi &G);
  27. void Xuat(DoThi G);
  28. void DFS(DoThi G);
  29. void DFS_Visit(int u);
  30. void InitStack();
  31. void Push(int s);
  32. int empty();
  33. int Pop(Stack *st);
  34.  
  35. //*************************************
  36.  
  37. void main()
  38. {
  39.     int task;
  40.     while( task=Menu() )
  41.         Run(task);
  42. }
  43.  
  44. //*************************************
  45. int Menu()
  46. {
  47.     cout <<"\n\t Menu cong viec:\n";
  48.     cout <<"\n  1. Nhap Do Thi.  "<<endl;
  49.     cout <<"\n  2. Xuat Do Thi "<<endl;
  50.     cout <<"\n  3. Duyet do thi DFS "<<endl;
  51.     //..........
  52.     cout <<"\n...\n  0.Thoat."<<endl;
  53.     cout <<"\n\t Ban chon:  ";
  54.  
  55.     int task;
  56.     cin >>task;
  57.     return task;
  58. }
  59. void Run( int task)
  60. {
  61.    
  62.     switch (task)
  63.     {
  64.     case 1:
  65.         Nhap(G);
  66.         break;
  67.  
  68.     case 2:
  69.         Xuat(G);
  70.         break;
  71.  
  72.     case 3:
  73.        
  74.         DFS(G);
  75.         break;
  76.     }
  77.     cin.get(); cin.get();
  78.     system("cls");
  79. }
  80.  
  81. void Nhap(DoThi &G)
  82. {
  83.     int x;
  84.     do{
  85.     cout <<"\n Nhap dinh cua do thi: ";
  86.     cin >>G.n;
  87.     }while(G.n<=0);
  88.     cout <<"\n\n\tTuy chon: "
  89.          <<"\n\t\tYes (nhan phim 1)"
  90.          <<"\n\t\tNo (nhan phim 0)";
  91.     cout <<"\n\n\t--------------------------";
  92.     if(G.n>1)
  93.     {
  94.     for(int i=1;i<=G.n;i++)
  95.     {
  96.         cout <<"\n-->Xet dinh "<<i<<endl;
  97.         for(int j=1;j<=G.n;j++)
  98.         {
  99.                
  100.                 if(i!=j)
  101.                 {
  102.                     do{
  103.                         cout <<"\nDinh "<<i<<" co ke voi dinh "<<j<<" khong?"<<endl;
  104.                         cout <<"\n\tYes/No:";
  105.                         cin >>x;
  106.                     }while(x!=0 && x!=1);
  107.                     G.mtke[i][j]=x;
  108.                 }
  109.                
  110.         }
  111.        
  112.     }
  113.     }
  114.     else cout <<"\nDo thi co 1 dinh";
  115. }
  116.  
  117.    
  118.  
  119.  
  120. void Xuat(DoThi G)
  121. {
  122.     cout <<"\n--------------------------------------------\n";
  123.     cout <<"\tHien thi Do Thi: \n\n";
  124.     cout <<endl;
  125.    
  126.         for(int i=1;i<=G.n;i++)
  127.         {
  128.            
  129.             for(int j=1;j<=G.n;j++)
  130.             {
  131.                
  132.                 if(G.mtke[i][j]==1)
  133.            
  134.                     cout <<"\nDinh "<<i <<" ke voi "<<j<<' ';
  135.                
  136.             }
  137.             cout <<endl;
  138.         }
  139.    
  140. }
  141. void DFS(DoThi G)
  142. {
  143.    
  144.     for( int i=1; i<=G.n; i++)
  145.         danhdau[i]=0; // chua co dinh nao dc xet
  146.     for( i=1; i<=G.n; i++)
  147.         if(danhdau[i]==0)
  148.             DFS_Visit(i);  
  149. }
  150. void DFS_Visit(int u)
  151. {
  152.    
  153.     InitStack();
  154.     Push(u);
  155.     while(!empty())
  156.     {
  157.         int v=Pop(st);
  158.         if(danhdau[v]!=1)
  159.         {
  160.             cout <<v<<' ';
  161.             danhdau[v]=1;
  162.             for(int i=G.n;i>=1;i--)
  163.             {
  164.                 if(!danhdau[i] && G.mtke[v][i]!=0) 
  165.                     Push(i);
  166.             }
  167.         }
  168.     }
  169. }
  170. void InitStack()
  171. {
  172.     st=NULL;
  173. }
  174. void Push(int u)
  175. {
  176.     Stack *p=new Stack;
  177.     p->key=u;
  178.     p->next=st;
  179.     st=p;
  180. }
  181. int empty()
  182. {
  183.     if(st==NULL)
  184.         return 1;
  185.     return 0;
  186. }
  187. int Pop(Stack *st)
  188. {
  189.     if(st==NULL)
  190.         return 0;
  191.     else
  192.     {
  193.        
  194.         Stack *p=st;
  195.         st=p->next;
  196.         delete p;
  197.         return 1;
  198.  
  199.     }
  200. }