数据结构实验四图的有关操作

小咪咪 2022-08-22 11:29 155阅读 0赞

**实验四 图的有关操作**

目的要求：

１．掌握图的存储思想及其存储实现。

２．掌握图的深度、广度优先遍历算法思想及其程序实现。

３．掌握图的常见应用算法的思想及其程序实现。

实验内容：

１．键盘输入数据，建立一个有向图的邻接表。

２．输出该邻接表。

\*３．建立一个无向图的十字链表。

４．在有向图的邻接表的基础上计算各顶点的度，并输出。

５．以有向图的邻接表为基础实现输出它的拓扑排序序列。

\*６．采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。

７．采用邻接表存储实现无向图的深度优先非递归遍历。

８．采用邻接表存储实现无向图的广度优先遍历。

\*９．采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。

\*10．判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。

11．在主函数中设计一个简单的菜单，分别调试上述算法。

\*12．综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #define Maxsize 200
    
    using namespace std;
    
    int indegree[Maxsize],outdegree[Maxsize];
    
    typedef char InfoType;///图的邻接表存储结构
    typedef char VertexType; ///节点数据为字符型
    typedef struct ArcNode ///表节点
    {
        int adjvex; ///存放结点的下标
        struct ArcNode *nextarc;///指向下一条边或弧的指针域
        InfoType *info;///其他信息
    } ArcNode;
    typedef struct VNode ///头结点
    {
        VertexType data;
        ArcNode *firstarc;
    } VNode,AdjList[Maxsize];
    typedef struct ///图结构
    {
        AdjList vertices;
        int vexnum,arcnum;///图中顶点个数和边的个数
        int kind; ///kind==0表示无向图，kind==1表示有向图
    } ALGraph;
    
    int visited[Maxsize];
    
    void Create(ALGraph &G)
    {
        char ch1,ch2;
        int k1,k2;
        printf("Please Input the Vexnum & Arcnum:\n");
        scanf("%d%d",&G.vexnum,&G.arcnum);
        printf("Please Input the Vexnums:\n");
        for(int i=1; i<=G.vexnum; i++) ///图结构的下标从1开始用
        {
            scanf(" %c",&G.vertices[i].data);
            G.vertices[i].firstarc=NULL;
        }
        printf("Please Input the Arcnums:\n");
        for(int i=1; i<=G.arcnum; i++)
        {
            scanf(" %c %c",&ch1,&ch2);
            for(int p=1; p<=G.arcnum; p++)
            {
                if(G.vertices[p].data==ch1)
                {
                    k1=p;
                    break;
                }
            }
            for(int p=1; p<=G.arcnum; p++)
            {
                if(G.vertices[p].data==ch2)
                {
                    k2=p;
                    break;
                }
            }
            ArcNode *pp;///申请一个表节点之后进行前插,前插，特别注意
            pp=(ArcNode*)malloc(sizeof(ArcNode));
            pp->adjvex=k2;
            pp->nextarc=G.vertices[k1].firstarc;
            G.vertices[k1].firstarc=pp;
        }
    }
    
    void Dfs(ALGraph G,VertexType x)///深搜,从节点元素为x开始搜索
    {
        //ALGraph G=GG;
        int k1;
        for(int i=1; i<=G.vexnum; i++)
        {
            if(G.vertices[i].data==x)
            {
                k1=i;
                break;
            }
        }
        printf("%c ",G.vertices[k1].data);
        visited[k1]=1;
        ArcNode *p;
        p=G.vertices[k1].firstarc;
        while(p)///如果该点的第一邻接点存在
        {
            if(visited[p->adjvex]==0) ///如果第一邻接点没有被遍历过
            {
                Dfs(G,G.vertices[p->adjvex].data); ///就去图中以该点的元素为起始点深度优先遍历
            }
            p=p->nextarc;///不然的话，即如果说该点已经被遍历过了，就让p指针后移
        }
    }
    
    void Bfs(ALGraph G,VertexType x)///按广度非递归优先遍历图G
    {
        struct
        {
            ArcNode *Q[Maxsize];
            int front,rear;
        } QQ; ///队列中存放的是表节点的地址
        ArcNode *p;
        QQ.front=QQ.rear=0;///队列初始化
        int k1;
        for(int i=1; i<=G.vexnum; i++)
        {
            if(G.vertices[i].data==x) ///在图中遍历找到元素值为x的点，返回其下标k1
            {
                k1=i;
                break;
            }
        }
        visited[k1]=1;
        printf("%c ",G.vertices[k1].data);
        QQ.rear=(QQ.rear+1)%Maxsize;
        QQ.Q[QQ.rear]=G.vertices[k1].firstarc;
        while(QQ.rear!=QQ.front)
        {
            QQ.front=(QQ.front+1)%Maxsize;
            p=QQ.Q[QQ.front];
            while(p)
            {
                if(visited[p->adjvex]==0)///visited[]中的下标即为每个节点的标号，和图中的下标相对应
                {
                    visited[p->adjvex]=1;
                    printf("%c ",G.vertices[p->adjvex].data);
                    QQ.rear=(QQ.rear+1)%Maxsize;
                    QQ.Q[QQ.rear]=G.vertices[p->adjvex].firstarc;
                }
                p=p->nextarc;
            }
        }
    }
    
    void Output(ALGraph G)
    {
        for(int i=1; i<=G.vexnum; i++)
        {
            printf("%c ",G.vertices[i].data);
            ArcNode *pp;
            pp=G.vertices[i].firstarc;
            while(pp)
            {
                printf("%c ",G.vertices[pp->adjvex].data);
                pp=pp->nextarc;
            }
            printf("\n");
        }
    }
    
    void Degree(ALGraph G)
    {
        ArcNode *pp=NULL;
        for(int i=1; i<=G.vexnum; i++)
        {
            pp=G.vertices[i].firstarc;
            while(pp)
            {
                indegree[pp->adjvex]++;
                outdegree[i]++;
                pp=pp->nextarc;
            }
        }
    }
    
    int TopologicalSort(ALGraph G)
    {
        int S[Maxsize];
        int top=0;
        for(int i=1; i<=G.vexnum; i++)
        {
            if(indegree[i]==0)
            {
                top++;
                S[top]=i;
            }
        }
        int countt=0;
        int ii=1;
        ArcNode *pp=NULL;
        while(top!=0)
        {
            ii=S[top];
            top--;
            printf("%d %c     ",ii,G.vertices[ii].data);
            countt++;
            for(pp=G.vertices[ii].firstarc; pp; pp=pp->nextarc)
            {
                int k=pp->adjvex;
                indegree[k]--;
                if(indegree[k]==0)
                {
                    top++;
                    S[top]=k;
                }
            }
        }
        if(countt<G.vexnum)
            return -1;
        else return 1;
    }
    
    int main()
    {
        ALGraph G;
        char chx;
        Create(G);
        printf("The Adjacency List is:\n");
        Output(G);
        memset(indegree,0,sizeof(indegree));
        memset(outdegree,0,sizeof(outdegree));
        Degree(G);
        cout<<"The List of Indegree:"<<endl;
        for(int i=1; i<=G.vexnum; i++)
        {
            printf("%d ",indegree[i]);
        }
        cout<<endl;
        cout<<"The List of Outdegree:"<<endl;
        for(int i=1; i<=G.vexnum; i++)
        {
            printf("%d ",outdegree[i]);
        }
        cout<<endl;
    
        int flag=0;
        printf("The List of Topological are:\n");
        flag=TopologicalSort(G);
        printf("\n");
        if(flag==-1)
        {
            printf("Can not TopologicalSort!\n");
        }
        else
        {
            printf("Topo Over!\n");
        }
    
        memset(visited,0,sizeof(visited));
        printf("Please Input the Start Data of the DFS:\n");
        while(scanf(" %c",&chx)!=EOF)
        {
            if(chx=='0') break;///当输入起始元素为'0'时，该深度优先遍历结束
            printf("The List of Dfs :\n");
            Dfs(G,chx);
            cout<<endl;
            memset(visited,0,sizeof(visited));
        }
        cout<<"DFS OVER!"<<endl;
        memset(visited,0,sizeof(visited));
        printf("Please Input the Start Data of the BFS:\n");
        while(scanf(" %c",&chx)!=EOF)
        {
            if(chx=='0') break;///当输入起始元素为'0'时，该广度优先遍历结束
            printf("The List of Bfs :\n");
            Bfs(G,chx);
            cout<<endl;
            memset(visited,0,sizeof(visited));
        }
        cout<<"BFS OVER!"<<endl;
        return 0;
    }

///*测试样例
    4 4
    A B C D
    A B
    A D
    B C
    D B
    *///