数据结构(C语言版)严蔚敏---图的操作的相关代码

71 阅读 0 评论 47 点赞

我是靠谱客的博主独特牛排，这篇文章主要介绍数据结构(C语言版)严蔚敏---图的操作的相关代码，现在分享给大家，希望可以做个参考。

1. 将邻接表转换成邻接矩阵

main.cpp

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Convert(ALGraph G,MGraph &M){
    M.vexnum = G.vexnum;
    M.arcnum = G.arcnum;
    for(int i=1;i<=G.vexnum;i++)
        for(int j=1;j<=G.vexnum;j++)
            M.Edge[i][j] = 0;

    for(int i=1;i<=G.vexnum;i++){
        ArcNode *p = G.vertices[i].first->next;
        M.Vex[i] = G.vertices[i].data;
        while(p){
            M.Edge[i][p->adjvex] = 1;
            p = p->next;
        }
    }
}
// 图的邻接表转换成邻接矩阵

运行结果：
请添加图片描述
所表示的图为：

实现邻接表的参考代码在这篇博客：数据结构(C语言版)严蔚敏(线性表、队列、栈、串、树、图等数据结构参考代码，持续更新中。。。)

2. 将邻接矩阵转换成邻接表

main.cpp

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Convert2(MGraph M,ALGraph &G){
    G.arcnum = M.arcnum;
    G.vexnum = M.vexnum;
    for(int i=1;i<=M.vexnum;i++){
        G.vertices[i].data = M.Vex[i];
        G.vertices[i].first = (ArcNode*)malloc(sizeof(ArcNode));
        ArcNode *p = G.vertices[i].first,*q;
        p->next = NULL;
        for(int j=1;j<=M.vexnum;j++){
            if(M.Edge[i][j]!=0){
                q = (ArcNode*)malloc(sizeof(ArcNode));
                q->adjvex = j;
                q->next = p->next;
                p->next = q;
            }
        }
    }
}
// 图的邻接矩阵转换成邻接表

运行结果：
请添加图片描述
所表示的图和1一样。

3. 求图的拓扑排序序列

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int indegree[MaxVertexNum];
void  getIndegree(ALGraph G){
    for(int i=1;i<=G.vexnum;i++)
        indegree[i] = 0;
    for(int i=1;i<=G.vexnum;i++){
        ArcNode *p = G.vertices[i].first->next;
        while(p){
            indegree[p->adjvex]++;
            p = p->next;
        }
    }
}
// 邻接表求图的各顶点的入度
bool TopologicalSort(ALGraph G){
    int Gs[MaxVertexNum];
    // 用栈，这里用数组代替
    int i=0;
    for(int v=1;v<=G.vexnum;v++)
        if(indegree[v] == 0)
            Gs[i++] = v;
    // 将入度为0的顶点入栈
    int count_1 = 0;
    // 计数，记录当前已经输出的顶点数
    while(i>0){
        int v1 = Gs[--i];
        printf("%d",v1);
        count_1++;
        for(ArcNode *p = G.vertices[v1].first->next;p;p=p->next){
            if((--indegree[p->adjvex])==0)
                Gs[i++] = p->adjvex;
        }
    }

    if(count_1<G.vexnum) // 有向图中有回路
        return false;
    else
        return true;
}
// 求拓扑排序序列