实验5 图的遍历问题

邻接表实现

1 #include 
      
         2 #define MaxVertexNum 100  3 #define QueueSize 30  4 #include
       
          5 using namespace std;  6 typedef enum{ FALSE, TRUE }Boolean;  7 Boolean visited[MaxVertexNum];  8 typedef char VertexType;  9 typedef int EdgeType; 10 typedef struct node     //边表结点 11 { 12     int adjvex;         //邻接点域 13     struct node *next;  //域链 14     //若是要表示边上的权,则应增加一个数据域 15 }EdgeNode; 16 typedef struct vnode    //顶点边结点 17 { 18     VertexType vertex;  //顶点域 19     EdgeNode *firstedge;//边表头指针 20 }VertexNode; 21 typedef VertexNode AdjList[MaxVertexNum];   //AdjList是邻接表类型 22 typedef struct 23 { 24     AdjList adjlist;    //邻接表 25     int n, e;           //图中当前顶点数和边数 26 }ALGraph;               //对于简单的应用，无须定义此类型，可直接使用AdjList类型 27  28 void CreateGraphAL(ALGraph *G) 29 { 30     int i, j, k,c; 31     char a,b,first; 32     EdgeNode * s; 33     cout<<"请输入顶点数和边数(输入格式为:顶点数,边数)：\n"; 34     cin>>(G->n)>>(G->e);       // 读入顶点数和边数 35     cout<<"输入"<
        
         n<<"个顶点"<
         
          n; i++)              // 立有n个顶点的顶点表 37     { 38         cout<<"输入顶点"<
          <<":"; 39         cin>>a; 40         G->adjlist[i].vertex=a; // 读入顶点信息 41         G->adjlist[i].firstedge = NULL;            // 点的边表头指针设为空 42     } 43     first=G->adjlist[0].vertex; 44     cout<<"first"<
           
            <
            
             e; k++) // 建立边表 47 { 48 // 读入边
             
              的顶点对应序号 49 cout<<"输入弧"<
              
               <<":"; 50 cin>>a>>b>>c; 51 s = new EdgeNode; // 生成新边表结点s 52 i=a-first; 53 j=b-first; 54 // printf("%d %d \n",i,j); 55 s->adjvex = j; // 邻接点序号为j 56 s->next = G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部 57 G->adjlist[i].firstedge = s; 58 59 } 60 61 } 62 63 void DFS(ALGraph *G, int i) 64 { 65 //以vi为出发点对邻接表表示的图G进行深度优先搜索 66 EdgeNode *p; 67 cout<
               
                adjlist[i].vertex; 68 visited[i] = TRUE; //标记vi已访问 69 p = G->adjlist[i].firstedge; //取vi边表的头指针 70 while (p) 71 { //依次搜索vi的邻接点vj，这里j=p->adjvex 72 if (!visited[p->adjvex]) //若vi尚未被访问 73 DFS(G, p->adjvex); //则以Vj为出发点向纵深搜索 74 p = p->next; //找vi的下一邻接点 75 } 76 } 77 void DFSTraverseM(ALGraph *G) 78 { 79 int i; 80 for (i = 0; i < G->n; i++) 81 visited[i] = FALSE; 82 for (i = 0; i < G->n; i++) 83 if (!visited[i]) 84 DFS(G, i); 85 } 86 typedef struct 87 { 88 int front; 89 int rear; 90 int count; 91 int data[QueueSize]; 92 }CirQueue; 93 void InitQueue(CirQueue *Q) 94 { 95 Q->front = Q->rear = 0; 96 Q->count = 0; 97 } 98 int QueueEmpty(CirQueue *Q) 99 {100 return Q->count == 0;101 }102 int QueueFull(CirQueue *Q)103 {104 return Q->count == QueueSize;105 }106 void EnQueue(CirQueue *Q, int x)107 {108 if (QueueFull(Q))109 cout<<"Queue overflow"<
                
                 count++;113 Q->data[Q->rear] = x;114 Q->rear = (Q->rear + 1) % QueueSize;115 }116 }117 int DeQueue(CirQueue *Q)118 {119 int temp;120 if (QueueEmpty(Q))121 {122 cout<<"Queue underflow"<
                 
                  data[Q->front];128 Q->count--;129 Q->front = (Q->front + 1) % QueueSize;130 return temp;131 }132 }133 void BFS(ALGraph*G, int k)134 { // 以vk为源点对用邻接表表示的图G进行广度优先搜索135 int i;136 CirQueue Q; //须将队列定义中DataType改为int137 EdgeNode *p;138 InitQueue(&Q); //队列初始化139 cout<
                  
                   adjlist[k].vertex; //访问源点vk140 visited[k] = TRUE;141 EnQueue(&Q, k); //vk已访问，将其人队。（实际上是将其序号人队）142 while (!QueueEmpty(&Q))143 { //队非空则执行144 i = DeQueue(&Q); //相当于vi出队145 p = G->adjlist[i].firstedge; //取vi的边表头指针146 while (p)147 { //依次搜索vi的邻接点vj(令p->adjvex=j)148 if (!visited[p->adjvex])149 { //若vj未访问过150 // printf("visit vertex:%c\n", G->adjlist[p->adjvex].vertex); //访问vj151 cout<
                   
                    adjlist[p->adjvex].vertex;152 visited[p->adjvex] = TRUE;153 EnQueue(&Q, p->adjvex); //访问过的vj人队154 }155 p = p->next; //找vi的下一邻接点156 }157 }158 }159 void BFSTraverseM(ALGraph *G)160 {161 int i;162 for (i = 0; i < G->n; i++)163 visited[i] = FALSE;164 for (i = 0; i < G->n; i++)165 if (!visited[i])166 BFS(G, i);167 }168 169 void PrintfGraphAL(ALGraph *G)170 {171 for (int i = 0; i < G->n; i++)172 {173 cout<<"vertex"<
                    
                     adjlist[i].vertex;174 EdgeNode *p = G->adjlist[i].firstedge;175 while (p)176 {177 cout<<"→"<
                     
                      adjvex;178 p = p->next;179 }180 cout<
                      
                       n; i++)187 {188 EdgeNode *q;189 EdgeNode *p = G->adjlist[i].firstedge;190 while (p)191 {192 q = p;193 p = p->next;194 delete q;195 }196 G->adjlist[i].firstedge = NULL;197 }198 }199 int main()200 {201 202 ALGraph G;203 CreateGraphAL(&G);204 cout<<"深度优先遍历：\n";205 DFSTraverseM(&G);206 cout<
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
         
        
       
      

邻接矩阵实现

1 #include 
      
         2 #include
       
          3   4 typedef enum{ FALSE, TRUE }Boolean;  5 #define maxSize 20  6 Boolean visited[maxSize];  7 using namespace std;  8 struct g  9 { 10     int w[maxSize][maxSize]; 11     int n,e; 12     char first; 13     char vertex[maxSize]; 14 }; 15 g graph; 16 void creatgraph() 17 { 18  19     int i,j,w; 20     char a,b; 21  22     cout<<"输入顶点数和弧数："<
        
         >graph.n>>graph.e; 24     for(i=0;i
         
          >a; 28         graph.vertex[i]=a; 29     } 30    graph.first=graph.vertex[0]; 31     cout<<"输入"<
          
           <<"条弧"<
           
            >a>>b>>w; 36 graph.w[a-graph.first][b-graph.first]=w; 37 } 38 cout<<"----图----"<
           
          
         
        
       
      

矩阵实现的BFS部分我偷懒了，我为了应付实验验收，没有用队列，而且搜索之后数组全被我清零。这样是有bug的。建议用visited数组来标记是否被访问。