无向图非递归的深度优先非递归遍历

小咪咪 2022-05-22 08:27 237阅读 0赞

//
    // main.cpp
    // Tu
    //
    // Created by 李奕昕 on 2018/6/16.
    // Copyright © 2018 李奕昕. All rights reserved.
    //
    #include <iostream>
    #include <stdio.h>//注意
    #include <stdlib.h>//注意
    #include <string.h>
    using namespace std;
    #define MAX_VERTEX_NUM 20
    #define MAX_VEX 20
    typedef string VertexType,VexType;
    typedef int ElemType;
    typedef int EdgeType,InfoType;
    int  Visited[MAX_VEX] ;
    
    typedef struct ArcNode{ //边（弧）结点的类型定义
        int  adjvex;   //边（弧）的另一顶点的在数组中的位置
        ArcNode *nextarc;//指向下一边（弧）结点的指针
        InfoType *info;      //该弧相关信息的指针
    }ArcNode;
    typedef struct Vnode{
       //顶点结点及其数组的类型定义
        VertexType data;    //顶点信息
        ArcNode * firstarc;    //指向关联该顶点的边（弧）链表
    } Vnode, AdjList[MAX_VERTEX_NUM];
    typedef struct {
        AdjList  vertices;
        int  vexnum, arcnum;    //图的当前顶点数和弧数
        int  kind;    //图的种类标志
    } ALGraph;    //图邻接表类型
    typedef struct
    {
        ElemType elem[ MAX_VEX ];
        int top;
    }seqstack;
    void initStack(seqstack &s)
    {
        s.top=0;
    }
    void push(seqstack &s, int e)
    {
        s.elem[s.top]=e;
        s.top++;
    }
    int pop(seqstack &s, int &e)
    {
        s.top--;
        return   e=s.elem[s.top];
    }
    int stackEmpty(seqstack s)
    {
        if(s.top==0)
            return 1;
        else return 0;
    }
    
    int  LocateVex(ALGraph  &G , VexType vp)
    {
        int  k=0 ;
        for (k=0 ; k<G.vexnum ; k++)
        {
       if (G. vertices[k].data==vp)
            return(k) ;}
        return(-1) ;     /* 图中无此顶点 */
    }
    void CreatALGraph(ALGraph &G)//无向图的创建
    {
        string v1,v2;
        int i,j,k;
        ArcNode *p1,*p2,*p,*q;
        cin>>G.vexnum>>G.arcnum;//输入顶点数和边数
        for(i=0;i<G.vexnum;i++)
        {
            cin>>G.vertices[i].data;//输入顶点信息
            G.vertices[i].firstarc=NULL;
        }
        for(k=0;k<G.arcnum;k++)
        {
            cin>>v1>>v2;
            i=LocateVex(G,v1);
            j=LocateVex(G,v2);
            p1=new ArcNode;
            p1->adjvex=j;
            p1->nextarc=NULL;
            p=G.vertices[i].firstarc;
            if(p==NULL)
                G.vertices[i].firstarc=p1;
            else
            {
                while(p->nextarc)
                {
                    p=p->nextarc;
                }
                p->nextarc=p1;
            }
            p2=new ArcNode;
            p2->adjvex=i;
            p2->nextarc=NULL;
            q=G.vertices[j].firstarc;
            if(q==NULL)
                G.vertices[j].firstarc=p2;
            else
            {
                while(q->nextarc)
                {
                    q=q->nextarc;
                }
                q->nextarc=p2;
            }
        }
    }
    
    
    void OutputALGraph(ALGraph &G)//邻接表的输出
    {   int i;
        for(i=0;i<G.vexnum;i++)
        {   ArcNode *s;
            cout<<i<<" "<<G.vertices[i].data; //顶点信息
            s=G.vertices[i].firstarc;
            while(s!=NULL)
            {  printf(" %d",s->adjvex);
                s=s->nextarc;   }
            printf("\n");
        }
    }
    
    int FirstAdjvex(ALGraph G,int u)
    {
        ArcNode *t;
        t=G.vertices[u].firstarc;
        if(t!=NULL)
            return t->adjvex;
        else
            return -1;
    }
    int NextAdjvex(ALGraph G,int u,int w)
    {
        ArcNode *t;
        t=G.vertices[u].firstarc;
        while(t!=NULL)
        {
            if(t->adjvex!=w)
                t=t->nextarc;
            else if(t->nextarc!=NULL)
                return t->nextarc->adjvex;
            else
                return -1;
        }
        return -1;
    }
    void BFS(ALGraph G,int v)
    {   seqstack q;
        int u,w;
        cout<<G.vertices[v].data<<" ";
        Visited[v]=true;
        initStack(q);
        push(q,v);
        while(!stackEmpty(q))
        {
            pop(q,u);
            for(w=FirstAdjvex(G,u);w>=0;w=NextAdjvex(G,u,w))
                if(!Visited[w])
                {
                    cout<<G.vertices[w].data<<" ";
                    Visited[w]=true;
                    push(q,w);
                }
        }
    }
    
    void DFS(ALGraph G,int v)
    {
        seqstack s;
        int k,w;
        initStack(s);
        push(s,v);
        while(!stackEmpty(s))
        {
            pop(s,k);
            if(!Visited[k])
            {
                Visited[k]=true; cout<<G.vertices[k].data<<" ";
                for(w=FirstAdjvex(G,k);w>=0;w=NextAdjvex(G,k,w))
                {
                    if(!Visited[w])
                    {
                        push(s,w);
                    }
                }
            }
        }
    }
    int main()
    {
        ALGraph G;
        CreatALGraph(G);
        //OutputALGraph(G);
        DFS(G,0);
        return 0;
    }