美文网首页数据结构数据结构和算法分析算法与数据结构
数据结构之图、广度优先搜索以及佛洛依德算法

数据结构之图、广度优先搜索以及佛洛依德算法

作者: 辛辛辛烷 | 来源:发表于2019-03-21 00:11 被阅读2次
    实验要求
    • 实现图的抽象数据类型
    • 在邻接矩阵结构上实现图的建立运算
    • 在邻接表结构上实现图的建立运算
    • 实现网的遍历运算(广度优先)
    • 实现最短路径算法(floyd)
    实验代码
    • 实现图的抽象数据类型
    //邻接矩阵结构
    typedef struct ArcCell
    {
        EType adj;
        InfoType info;
    }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    
    typedef struct
    {
        VertexType vexs[MAX_VERTEX_NUM];
        AdjMatrix arcs;
        int vexnum,arcnum;
        GraphKind kind;
    }MGraph;
    
    //邻接表结构
    typedef struct ArcNode
    {   int adjvex;
        struct ArcNode *nextarc;
        InfoType *info;
    }ArcNode;
    
    typedef struct VNode  //define structure ALGraph
    {   VertexType data;
        ArcNode *firstarc;
    }VNode,AdjList[MAX_VERTEX_NUM];
    
    typedef struct
    {   AdjList vertices;
        int vexnum,arcnum;
        int kind;
    }ALGraph;
    
    • 在邻接矩阵结构上实现图的建立运算
    int CreatUDN(MGraph &G)
    {
        int i=0,j=0,k,vi,vj,w;
    
        //-----Demo G.vexnum and G.arcnum------
        G.vexnum=3;
        G.arcnum=5;
        //-----------------------------------------
    
        printf("Please input the number of G.vexnum(eg,G.vexnum=3) : ");
        scanf("%d",&G.vexnum);
        printf("Please input the number of G.arcnum(eg,G.arcxnum=5) : ");
        scanf("%d",&G.arcnum);
    
        for(i=0;i<G.vexnum;++i)
            for(j=0;j<G.vexnum;++j)
            {
                G.arcs[i][j].info=INFINITY;
                if(i==j) G.arcs[i][j].info=0;
            }//end of for(j=0;j<G.vexnum;++j)
    
            cout<<"Please input arc(Vi-->Vj):"<<endl
                <<"For example:"<<endl<<"=============="<<endl
                <<"(Vi=1,Vj=2,Weight=4),(Vi=1,Vj=3,Weight=11),(Vi=2,Vj=1,Weight=6)"<<endl
                <<"(Vi=2,Vj=3,Weight=2),(Vi=3,Vj=1,Weight=3)..."<<endl;
            for(k=0;k<G.arcnum;++k)
            {
                cout<<endl<<"Please input the "<<k+1<<"the arc's vi (0<vi<"<<G.vexnum+1<<"): ";
                    cin>>vi;
                cout<<"Please input the "<<k+1<<"the arc's vj (0<vj<"<<G.vexnum+1<<"): ";
                    cin>>vj;
                cout<<"Please input the "<<k+1<<"the arc's weight (0<weight<"<<INFINITY<<"): ";
                    cin>>w;
                i=vi;
                j=vj;
                while(i<1||i>G.vexnum||j<1||j>G.vexnum||w<0)
                {
                    cout<<"Input ERROR!"<<endl
                        <<"Please input the "<<k+1<<"the arc's vi (0<vi<"<<G.vexnum+1<<"): ";
                    cin>>vi;
                cout<<"Please input the "<<k+1<<"the arc's vj (0<vj<"<<G.vexnum+1<<"): ";
                    cin>>vj;
                cout<<"Please input the "<<k+1<<"the arc's weight (0<weight<"<<INFINITY<<"): ";
                    cin>>w;
                i=vi;
                j=vj;
                }//end of while
                i--;
                j--;
                G.arcs[i][j].info=w;
            }//end of for
            return (OK);
    }//end of CreateUDN() function
    
    • 在邻接表结构上实现图的建立运算
    int CreateDG(ALGraph &G)  //CreateDG() sub-function
    {
        int IncInfo,i,j,k,v1,v2,w;
        cout<<endl<<"请输入图的顶点个数(eg. G.vexnum=4):";
        cin>>G.vexnum;
        cout<<"请输入图的弧的条数(eg. G.arcnum=4):";
        cin>>G.arcnum;
        cout<<"请输入图的弧上的信息(0 for none)   :";
        cin>>IncInfo;
        for(i=0;i<G.vexnum;++i)//initial G.vertices
        {G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;}
    
        cout<<"请输入弧arc(v1->v2),fo example:(v1=1,v2=3),(v1=2,v2=4)...";
        for(k=0;k<G.arcnum;++k)  //input arc(v1,v2)
        {
            cout<<endl<<"请输入第"<<k+1<<"条弧的起始顶点 v1(0<v1<G.vexnum):";
            cin>>v1;
            cout<<"请输入第"<<k+1<<"条弧的终止顶点 v2(0<v2<G.vexnum):";
            cin>>v2;
            i=v1;
            j=v2;
            while(i<1||i>G.vexnum||j<1||j>G.vexnum)//if(v1,v2) illedal again
            {
                cout<<endl<<"请输入第"<<k+1<<"条弧的起始顶点 v1(0<v1<G.vexnum):";
                cin>>v1;
                cout<<"请输入第"<<k+1<<"条弧的终止顶点 v2(0<v2<G.vexnum):";
                cin>>v2;
            }//while end
    
            i--;
            j--;
            ArcNode *p;
            p=(ArcNode *)malloc(sizeof(ArcNode));//allocate memory
            if(!p)
            {cout<<"Overflow!"; return(0);}
            p->adjvex=j;  //assign p
            p->nextarc=G.vertices[i].firstarc;
            p->info=NULL;
            G.vertices[i].firstarc=p;
    
            if(IncInfo)
            {cout<<"请输入info:";
            cin>>*(p->info);}
        }//end of if 
        return (OK);
    }//end of CreateDG()
    
    • 实现网的遍历运算(广度优先)
    void BFSTraverse(ALGraph G)//BFSTraverse() sub-function
    
    {
    
     int v,w,u;
    
     int visited[MAX_VERTEX_NUM];
    
     SqQueue Q;
    
     for(v=0;v<G.vexnum;++v)
    
     visited[v]=0;
    
     InitQueue(Q);
    
     for(v=0;v<G.vexnum;++v)
    
     if(visited[v]==0)
    
     {
    
     visited[v]=1;
    
     cout<<v+1<<"-->";
    
     EnQueue(Q,v);
    
     while(!QueueEmpty(Q))
    
     {
    
     DeQueue(Q,u);
    
     for(w=G.vertices[u].data;
    
     G.vertices[u].firstarc!=NULL;
    
     w=G.vertices[u].firstarc->adjvex,
    
     G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc)//"右)"
    
     if(visited[w]==0)
    
     {
    
     visited[w]=1;
    
     cout<<w+1<<"-->";
    
     EnQueue(Q,w);
    
     }//if end
    
     if(visited[w]==0)
    
     {
    
     visited[w]=1;
    
     cout<<w+1<<"-->";
    
     EnQueue(Q,w);
    
     }//if end
    
     }//while end
    
     }//if end
    }//BFSTraverse() end
    
    • 实现最短路径算法(floyd)
    void ShortestPath_FLOYD(MGraph G,
                          PathMatrix Path[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],
                          DistancMatrix Dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
    {
        int i,j,u,v,w;
        for(v=0;v<G.vexnum;++v)
            for(w=0;w<G.vexnum;++w)
            {   Dist[v][w]=G.arcs[v][w].info;
                for(u=0;u<G.vexnum;++u)
                    Path[v][w][u]=FALSE;
                if(Dist[v][w]<INFINITY)
                {   Path[v][w][v]=TRUE;
                    Path[v][w][w]=TRUE;
                }//end of if
            }//end of for
        for(u=0;u<G.vexnum;++u)
            for(v=0;v<G.vexnum;++v)
                for(u=0;u<G.vexnum;++u)
                    if(Dist[v][u]+Dist[u][w]<Dist[v][w])
                    {   Dist[v][w]=Dist[v][u]+Dist[u][w];
                        for(i=0;i<G.vexnum;++i)
                            Path[v][w][i]=Path[v][u][i]||Path[u][w][i];
                    }//end of if
    //------------print the last Dist[i][j]---------------
                    printf("Vertice");
                    for(i=0;i<G.vexnum;i++)
                        printf("%5d",i+1);
                    printf("\n");
                    for(i=0;i<G.vexnum;i++)
                    {
                        printf("%5d    ",i+1);
                        for(j=0;j<G.vexnum;j++)
                            printf("%5d",Dist[i][j]);
                        printf("\n");
                    }//end of for
    //---------------------------------------------------
    }//shortestPath_FLOYD() end
    

    相关文章:
    数据结构之栈(C语言版)
    数据结构之树的相关问题

    相关文章

      网友评论

        本文标题:数据结构之图、广度优先搜索以及佛洛依德算法

        本文链接:https://www.haomeiwen.com/subject/ruffvqtx.html