fork download 
  1. #include<iostream>
  2. #define N 100
  3.  
  4. using namespace std;
  5.  
  6.  
  7. struct Node{
  8.  
  9.      int data;   
  10.      Node *link;
  11.  
  12.  
  13.  
  14.         };
  15.  
  16. struct stack{
  17.        Node* stackarray[N];
  18.        int sp;
  19.  
  20.  
  21.        };
  22.  
  23. stack s;        
  24.  
  25.  
  26. struct Queue{
  27.         Node* queuearray[N];
  28.         int rear;
  29.         int front;              
  30.         };
  31.  
  32. Queue q;
  33. Node Adjlist[9];
  34. bool visited[9];
  35.  
  36.  
  37.  
  38. void construct(Node*,int);
  39. void DFSh(int);
  40. int push(stack *,Node*&);
  41. void pop(stack *,Node*&);
  42. int isempty(stack *);
  43. int isfull(stack *);
  44. void visit(Node*);
  45. Node* findAdj(Node *);
  46. void DFS(Node*);
  47.  
  48.  
  49. int main(void){
  50.     for(int i=1;i<=8;i++){
  51.       Adjlist[i].link=NULL;
  52.       Adjlist[i].data=i;}
  53.  
  54.     Node *head1=&Adjlist[1];
  55.     Node *head2=&Adjlist[2];
  56.     Node *head3=&Adjlist[3];
  57.     Node *head4=&Adjlist[4];
  58.     Node *head5=&Adjlist[5];
  59.     Node *head6=&Adjlist[6];
  60.     Node *head7=&Adjlist[7];
  61.     Node *head8=&Adjlist[8];
  62.  
  63.     construct(head1,2);
  64.     construct(head1,3);
  65.     construct(head2,4);
  66.     construct(head2,5);
  67.     construct(head3,6);
  68.     construct(head3,7);
  69.     construct(head4,2);
  70.     construct(head4,8);
  71.     construct(head5,2);
  72.     construct(head5,8);
  73.     construct(head6,3);
  74.     construct(head6,8);
  75.     construct(head7,3);
  76.     construct(head7,8);
  77.     construct(head8,4);
  78.     construct(head8,5);
  79.     construct(head8,6);
  80.     construct(head8,7);
  81.  
  82.     s.sp=-1;
  83.      for(int i=1;i<=8;i++)  
  84.       visited[i]=false;
  85.  
  86.  
  87.     DFS(head1);
  88.  
  89.        return 0;
  90. }
  91.  
  92. void construct(Node* ptr,int x){
  93.       Node *ppp=new Node;
  94.       ppp->data=x;
  95.       ppp->link=NULL;
  96.  
  97.       while(ptr->link!=NULL){
  98.  
  99.         ptr=ptr->link;
  100.  
  101.      }
  102.      ptr->link=ppp;
  103.  
  104.      }
  105.  
  106.  
  107.  
  108. void DFSh(int v){
  109.       visited[v]=true;
  110.  
  111.       cout<<"Visit Vertex:"<<v<<" "<<endl;
  112.       Node *w;
  113.       for(w=&Adjlist[v];w;w=w->link)
  114.         if(!visited[w->data])
  115.            DFSh(w->data);
  116.      }
  117.  
  118.  
  119. void DFS(Node *ptr){
  120.  
  121.       Node *Vx,*Vy;
  122.  
  123.       push(&s,ptr);
  124.       while(!(isempty(&s))){
  125.  
  126.            pop(&s,Vx);              
  127.         if(visited[Vx->data]==false){
  128.              visit(Vx);
  129.              Vy=findAdj(Vx);                 
  130.                  while(Vy!=NULL){
  131.                     push(&s,Vy);      
  132.                     Vy=findAdj(Vx);          
  133.                                  }             
  134.  
  135.  
  136.                                  }               
  137.  
  138.                                }                  
  139.  
  140.  
  141.  
  142.                           }
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153. void visit(Node *x){
  154.  
  155.       visited[x->data]=true;
  156.       cout<<"Visit Vertex:"<<x->data<<" "<<endl;
  157.  
  158.      }
  159.  
  160. Node* findAdj(Node *ptr){
  161.         Node *pk=NULL;
  162.         ptr=ptr->link;
  163.  
  164.      while(ptr!=NULL){  
  165.          if(visited[ptr->data]==false)
  166.           return ptr;
  167.           ptr=ptr->link;
  168.           }
  169.  
  170.      return pk;
  171.  
  172.      }  
  173.  
  174.  
  175.  
  176. int push(stack *p,Node* &x){
  177.      if(isfull(p))
  178.      return 1;
  179.      p->sp++;
  180.      p->stackarray[p->sp]=x;
  181.  
  182.      }
  183.  
  184. void pop(stack *p,Node *&x){
  185.  
  186.      x=p->stackarray[p->sp--];     
  187.  
  188.  
  189.      } 
  190.  
  191. int isempty(stack *p){
  192.      if(p->sp==-1)
  193.      return 1;
  194.      else
  195.      return 0;      
  196.      }
  197.  
  198. int isfull(stack *p){
  199.     if(p->sp==N-1)   
  200.     return 1;
  201.     else
  202.     return 0;   
  203. }
  204.  
Time limit exceeded #stdin #stdout 5s 2812KB
comments (?)
stdin 
Standard input is empty
stdout 
Visit Vertex:1
https://ideone.com/Ke8fB
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!