图的遍历

typedef struct{
     int adjvertex;
     struct ArcNode * nextArc;
     infoType info;
}ArcNode;

typedef struct{
     VertexType data;
     struct ArcNode * firstArc;
}VNode,AdjList[20];

typedef struct{
     AdjList vertices;
     int vexnum,arcnum;
     int kind;
}ALGraph;

bool visited[20];
void DFSTraverse(Graph G){
     for(int i=0;i<G.vexnum;i++) visited[i]=false;
     for(int i=0;i<G.vexnum;i++){
          if(!visited[i]){
               DFS(G,i);
          }
     }
}

void DFS(Graph G,int i){
     visited[i]=true; visit(i);
     ArcNode *arc = G.vertices[i].firstArc;
     while(arc!=NULL){
          if(visited[arc.adjvertex]) DFS(G,arc.adjvertex);
          arc = arc->nextArc;
     }
}


void BFSTraverse(Graph G,void (*visit)(int vertex)){   //visit 为 访问顶点为vertex的函数。
     for(int i=0;i<G.vexnum;i++) visited[i]=false;
     InitQueue(Q);
     ArcNode *arc;
     for(int i=0;i<G.vexnum;i++){
          if(!visited[i]){
               visited[i] = true; visit(i);
               EnQueue(Q,i);
               int current;
               while(!QueueEmpty){
                    DeQueue(Q,current);
                    arc = G.vertices[current].firstArc;
                    While(arc!=NULL){
                         if(!visited[arc.adjvertex]){
                              visited[arc.adjvertex] = true; 
                              visit(arc.adjvertex);
                              EnQueue(Q,arc.adjvertex);
                         }
                         arc = arc->nextArc;
                    }
               }
          }
     }
}
上一页 -
- 下一页