408数据结构学习笔记——图的应用（三）

2022-11-24 76

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 408数据结构学习笔记——图的应用

+关注继续查看

4.王道课后题

1.1→2→3→5→7→4→6

	1	2	3	4	5	6	7
1	0	3	3	6	∞	∞	∞
2	∞	0	4	∞	5	∞	∞
3	∞	∞	0	∞	4	3	∞
4	∞	∞	∞	0	∞	5	∞
5	∞	∞	∞	∞	0	∞	3
6	∞	∞	3	∞	∞	0	7
7	∞	∞	∞	∞	∞	∞	0

2.当一个顶点只有出度没有入度时，它不可能与其它顶点成为一个强连通分量；该图有七个强连通分量

3.1→2→4→6→3→5→7；1→4→2→6→3→5→7

4.prim算法：1→2 1→3 3→6 3→5 5→7 6→4

kruskal算法：1→2 1→3 3→6 5→7 3→5 6→4

顶点2：1→2 7
顶点3：1→3 11
顶点4：1→4 16
顶点5：1→3→5 18
顶点6：1→3→6 19

1.邻接表

v1→v2→v3→v5
v2→v3→v4
v3→v5→v6
v4→v6
v5→v7
v6→v7→v8
v7→v9
v8→v9
v9→NULL

2.16

3.v1→v3→v5→v7→v9

4.a2、a6、a9、a12

2.最早发生时间：A0、B0、C3、D3、E2、F3、G6、H6

最晚发生时间：A1、B0、C4、D4、E2、F5、G6、H7

3.关键路径：BEF（通过最晚发生时间减去最早发生时间得到时间余量，时间余量为0组成的路径为关键路径）

最短时间：8

#define MaxVertexNum 100
 
bool visited[MaxVertexNum] = {false};
int temp[MaxVertexNum] = { 0 };
int res[MaxVertexNum] = { 0 };
int maxTime = -1;
 
//DFS函数调用入口
void DFS_Entrance(Grpah G){
    int time = 0;
    //循环遍历visited数组
    for (int i = 0; i < G.verNum; i++){
        //当前元素未被访问过，则访问当前元素
        if (!visited[i]) DFS(G, i, time);
    }
    int k = 0;
    //res数组保存拓扑序列
    for (time = 0; time <= maxTime; time++){
        for (int i = 0; i < verNum; i++){
            if (temp[i] == time) res[k++] = temp[i];
        }
    }
}
 
void DPS(Graph G, int v, int time){
    //更改当前元素为true，标记为已访问
    visited[v] = true;
    temp[v] = time;
    //输出当前元素
    cout << v << endl;
    int w;
    //循环遍历其邻接顶点
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
        //每执行一次循环，当前层数+1
        time++;
        //更新最高的层数
        if (maxTime < time) maxTime = time;
        if (!visited[w]) DFS(G, w, time);
    }
}