图的基本操作

发布时间： 更新时间： 总字数：2115 阅读时间：5m 作者： IP上海 分享 网址
专栏文章
  1. 顺序表的基本操作
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作（当前）
  7. C++ 哈夫曼编码
  8. C++ 排序的基本操作
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Clang 介绍
  18. Cpp
  19. CMake 使用介绍

实验七：图的基本操作

实验七：图的基本操作

  1. 键盘输入数据，建立一个有向图的邻接表。
  2. 输出该邻接表。
  3. 在有向图的邻接表的基础上计算各顶点的度，并输出。
  4. 以有向图的邻接表为基础实现输出它的拓扑排序序列。
  5. 采用邻接表存储实现无向图的深度优先遍历。
  6. 采用邻接表存储实现无向图的广度优先遍历。
  7. 采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。
  8. 采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
  9. 在主函数中设计一个简单的菜单，分别调试上述算法。

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

源码

#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
#define max_vertex_num 20
#define INFINITY  1000000000
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef char vertexType;
typedef struct VNode
{
    vertexType data;
    ArcNode *firstarc;
    int count;
} VNode, AdjList[max_vertex_num];
typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;
    int degree;
} ALGraph; //邻接表
typedef struct ArcCell
{
    int adj;
} ArcCell, AdjMatrix[max_vertex_num][max_vertex_num];
typedef struct
{
    char vex[max_vertex_num];
       AdjMatrix
    arc;
    int vexnum, arcnum;
} MGraph; //邻接矩阵
ALGraph ALG, InsertALG, UALG;
MGraph G;
int visit[max_vertex_num];
struct edge
{
    char adjvex;
    int lowcost;
} closedge[max_vertex_num];
int P[max_vertex_num];
int D[max_vertex_num];
int finial[max_vertex_num];
void print()
{
    printf("（1）键盘输入数据，建立一个有向图的邻接表\n");
    printf("（2）输出该邻接表\n");
    printf("（3）在有向图的邻接表的基础上计算各顶点的度，并输出\n");
    printf("（4）以有向图的邻接表为基础实现输出它的拓扑排序序列\n");
    printf("（5）采用邻接表存储实现无向图的深度优先遍历\n");
    printf("（6）采用邻接表存储实现无向图的广度优先遍历\n");
    printf("（7）采用邻接矩阵存储实现无向图的最小生成树的PRIM算法\n");
    printf("（8）采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径\n");
    printf("（0）退出程序\n");
}
int locatevex(MGraph G, char v)
{
    //查找顶点在图中的位置
    int i = 0;
    while (i < G.vexnum)
    {
        if (v == G.vex[i])
            break;
        else
            i++;
    }
    return i;
}
void CreateALGraph(ALGraph
                   &ALG, ALGraph
                   &InsertALG)
{
    //创建有向邻接表及其逆邻接表并且其顶点用大写字母表示
    int i, j, k;
    ArcNode *s, *r;
    printf("请输入有向邻接表的顶点数和边数：\n");
    scanf("%d%d", &ALG.vexnum, &ALG.arcnum);
    for (i = 0; i < ALG.vexnum; i++)
    {
        ALG.vertices[i].data = 'A' + i;

        ALG.vertices[i].firstarc = NULL;
        InsertALG.vertices[i].data = 'A' + i;

        InsertALG.vertices[i].firstarc = NULL;
    }
    for (k = 0; k < ALG.arcnum; k++)
    {
        scanf("%d%d", &i, &j);
        s = (ArcNode*)malloc(sizeof(ArcNode));
        r = (ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex = j;
        s->nextarc = ALG.vertices[i].firstarc;
        ALG.vertices[i].firstarc = s;
        r->adjvex = i;
        r->nextarc = InsertALG.vertices[j].firstarc;
        InsertALG.vertices[j].firstarc = r;
    }
}
void CeratUALGraph(ALGraph &UALG)
{
    //用头插法建立无向邻接表
    int i, j, k;
    ArcNode *p;
    printf("请输入无向邻接表的的顶点数和边数：\n");
    scanf("%d%d", &UALG.vexnum, &UALG.arcnum);
    for (i = 0; i < UALG.vexnum; i++)
    {
        UALG.vertices[i].data = 'A' + i;
        UALG.vertices[i].firstarc = NULL;
    }
    for (k = 0; k < UALG.arcnum; k++)
    {
        scanf("%d%d", &i, &j);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = UALG.vertices[i].firstarc;

        UALG.vertices[i].firstarc = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = UALG.vertices[j].firstarc;

        UALG.vertices[j].firstarc = p;
    }
}
void CreateUDN(MGraph &G, int a)
{
    //若a==1的时候创建无向邻接矩阵，否则创建有向邻接矩阵
    int i, j, k, w;
    char v1, v2;
    printf("请输入邻接矩阵的顶点数和边数：\n");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    getchar();
    for (i = 0; i < G.vexnum; i++)
        scanf("%c", &G.vex[i]);
    for (i = 0; i < G.vexnum; i++)
        for (j = 0; j < G.vexnum; j++)
            G.arc[i][j].adj = INFINITY;
    for (k = 0; k < G.arcnum; k++)
    {
        getchar();
        scanf("%c %c
              %d", &v1, &v2, &w);
        i = locatevex(G, v1);
        j = locatevex(G, v2);
        G.arc[i][j].adj = w;
        if (a == 1)
            G.arc[j][i].adj = G.arc[i][j].adj;
    }
}
void shuchu(ALGraph ALG)
{
    //遍历邻接表并输出
    int i;
    ArcNode *p;
    for (i = 0; i < ALG.vexnum; i++)
    {
        printf("%d %c ", i, ALG.vertices[i].data);
        for (p = ALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
            printf("%d ", p->adjvex);
        printf("\n");
    }
}
void Degree(ALGraph ALG, ALGraph InsertALG)
{
    //计算邻接表的度=邻接表的出度+逆邻接表的的出度
    int i;
    ArcNode *p;
    for (i = 0; i < ALG.vexnum; i++)
    {
        ALG.vertices[i].count = 0;
        for (p = ALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
            ALG.vertices[i].count++;
    }
    for (i = 0; i < ALG.vexnum; i++)
    {
        InsertALG.vertices[i].count = 0;
        for (p = InsertALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
            InsertALG.vertices[i].count++;
    }
    for (i = 0; i < ALG.vexnum; i++)
    {
        printf("%c的度为：%d\n", 'A' + i, ALG.vertices[i].count + InsertALG.vertices[i].count);
    }
}
void dfs(ALGraph UALG, int v)
{
    //深度优先遍历
    ArcNode *p;
    visit[v] = 1;
    printf("%c\n", UALG.vertices[v].data);
    p = UALG.vertices[v].firstarc;
    while (p)
    {
        if (!visit[p->adjvex])
            dfs(UALG, p->adjvex);
        p = p->nextarc;
    }
}
void DFSTraverse(ALGraph UALG)
{
    for (int i = 0; i < UALG.vexnum; i++)
        visit[i] = 0;
    for (i = 0; i < UALG.vexnum; i++)

        if (!visit[i])
            dfs(UALG, i);
    printf("\n");
}
void BFSTraverse(ALGraph UALG)
{
    //广度优先遍历
    ArcNode *p;
    int v;
    queue<int>q;
    for (int i = 0; i < UALG.vexnum; i++)
        visit[i] = 0;
    for (i = 0; i < UALG.vexnum; i++)
        if (!visit[i])
        {
            visit[i] = 1;
            printf("%c\n", UALG.vertices[i].data);
            q.push(i);
            while (!q.empty())
            {
                v = q.front();
                q.pop();
                p = UALG.vertices[v].firstarc;
                while (p)
                {
                    if (!visit[p->adjvex])
                    {
                        visit[p->adjvex] = 1;
                        printf("%c\n", UALG.vertices[p->adjvex].data);
                        q.push(p->adjvex);
                    }
                    p = p->nextarc;
                }
            }
        }
}
void prim(MGraph G, char v)
{
    //用prim算法求最小生成树
    int i, j, k, min, n;
    k = locatevex(G, v);
    for (i = 0; i < G.vexnum; i++)
    {
        if (i != k)
        {
            closedge[i].adjvex = v;
            closedge[i].lowcost = G.arc[k][i].adj;
        }
    }
    closedge[k].lowcost = 0;
    for (i = 1; i < G.vexnum; i++)
    {
        min = INFINITY;
        for (j = 0; j < G.vexnum; j++)
        {
            if (closedge[j].lowcost != 0 && closedge[j].lowcost < min)
            {
                n = j;
                min = closedge[j].lowcost;
            }
        }
        printf("%c %c\n", closedge[n].adjvex, G.vex[n]);
        closedge[n].lowcost = 0;
        for (j = 0; j < G.vexnum; j++)
            if (G.arc[n][j].adj < closedge[j].lowcost && G.arc[n][j].adj != INFINITY)
            {
                closedge[j].adjvex = G.vex[n];
                closedge[j].lowcost = G.arc[n][j].adj;
            }

    }
    printf("\n");
}
int indegree[max_vertex_num];
int topsort(ALGraph  ALG, ALGraph InsertALG)
{
    //拓扑排序
    ArcNode *p;
    stack<int>s;
    int i, k, count;
    for (i = 0; i < ALG.vexnum; i++)
    {
        InsertALG.vertices[i].count = 0;
        for (p = InsertALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
            InsertALG.vertices[i].count++;
    }
    for (i = 0; i < ALG.vexnum; i++)
    {
        indegree[i] = InsertALG.vertices[i].count;
        printf("%d\n", indegree[i]);
    }
    for (i = 0; i < ALG.vexnum; i++)
        if (indegree[i] == 0)
            s.push(i);
    count = 0;
    while (!s.empty())
    {
        i = s.top();
        s.pop();
        printf("%c ", ALG.vertices[i].data);
        count++;
        for (p = ALG.vertices[i].firstarc; p; p = p->nextarc)
        {
            k = p->adjvex;
            indegree[k]--;
            if (indegree[k] == 0)
                s.push(k);
        }
    }
    if (count < ALG.vexnum)
        return -1;
    else
        return 1;
}
void short_dij(MGraph G, int v0, int *P, int *D)
{
    //用dij球最短路径
    int i, v, w, min;
    for (i = 0; i < G.vexnum; i++)
    {
        finial[i] = 0;
        D[i] = G.arc[v0][i].adj;
        if (D[i] < INFINITY)
            P[i] = v0;
    }
    D[v0] = 0;
    finial[v0] = 1;
    for (i = 1; i < G.vexnum; i++)
    {
        min = INFINITY;
        for (w = 0; w < G.vexnum; w++)
        {
            if (finial[w] == 0)
                if (D[w] < min)
                {
                    v = w;
                    min = D[w];
                }
        }
        if (min < INFINITY)
            finial[v] = 1;
        else
            break;
        for (w = 0; w < G.vexnum; w++)
        {
            if (finial[w] == 0 && min + G.arc[v][w].adj < D[w])
            {
                D[w] = min + G.arc[v][w].adj;
                P[w] = v;
                printf("%d ", P[w]);
            }
        }
        printf("\n");
    }
    printf("路径长度为：\n");
    for (i = 0; i < G.vexnum; i++)
    {
        if (D[i] == INFINITY)
            printf("无法到达!!!\n");
        else
            printf("%d\n", D[i]);
    }
}
int main()
{
    int menu;
    char V;
    do
    {
        void print();
        scanf("%d", &menu);
        switch (menu)
        {
        case 1:
            CreateALGraph(ALG, InsertALG);
            break;
        case 2:
            shuchu(ALG);
            break;

        case 3:
            CreateALGraph(ALG, InsertALG);
            Degree( ALG,
                    InsertALG);
            break;
        case 4:
            CreateALGraph(ALG, InsertALG);
            topsort(
                ALG, InsertALG);
            break;
        case 5:
            CeratUALGraph(UALG);
            DFSTraverse(UALG);
            break;
        case 6:
            CeratUALGraph(UALG);
            BFSTraverse(UALG);
            break;
        case 7:
            CreateUDN(G, 1);
            printf("请输入出发顶点：\n");
            scanf("%c", &V);
            prim(G, V);
            break;
        case 8:
            CreateUDN(G, 0);
            short_dij( G, 0, P, D);
            break;
        case 0:
            return 0;
        }
    }
    while (menu != 0);
    return 0;
}
专栏文章
  1. 顺序表的基本操作
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作（当前）
  7. C++ 哈夫曼编码
  8. C++ 排序的基本操作
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Clang 介绍
  18. Cpp
  19. CMake 使用介绍
最近更新
相关文章
最新评论
Home Archives Categories Tags Statistics
本文总阅读量 次 本站总访问量 次 本站总访客数 人