数据结构——图(下)

这是我参与更文挑战的第24天，活动详情查看：更文挑战

图的应用

最小生成树

假设边的权值不同，所有生成树中权值之和最小的生成树

性质

• 最小生成树不唯一，如果各边权值互不相等，则最小生成树唯一
• 最小生成树的权值和是唯一的
• 最小生成树的边数为顶点数-1

通用算法

GENERIC_MST(G){
    T=NULL;
    while T未形成一棵生成树
        do 找到一条最小代价边(u,v)并且加入T后不会产生回路
            T=T∪(u,v);
}
复制代码

Prim算法

void Prim(G,T){
    T=NULL; //初始化空树
    U={w};  //添加任一顶点w
    while((V-U)!=0){
        找到(u,v)满足u属于U且v属于(V-U)
        边归入。顶点归入
    }
    
}
复制代码

Prim算法复杂度为O(|V|^2^),且与边数无关，因此适用于解边稠密的图的最小生成树

Kruskal算法

void Kruskal(V,T){
    T=V;numS=n; //初始化树，连通分量数
    while(numS>1){
        从E中取出权值最小的边;
        if(v和u属于不同的连通分量){
            边归入;
            numS--;
        }
    }
    
}
复制代码

时间复杂度O(log|E|)

最短路径

针对无权图：广度优先搜索

针对有权图：

• 单源最短路径：Dijkstra算法，时间复杂度O(|V|^2^)
• 求每对顶点的最短路径: Floyd-Warshall

Floyd-Warshall

• 时间复杂度O(|V|^3^)
• 允许带负权值的边，但不允许包含负权值的边组成的回路

拓扑排序

• 有向无环图DAG图
• AOV网：使用DAG表示工程，其中顶点表示活动，有向边表示活动$V_i必须先于活动V_j$

拓扑排序必须满足的条件

• 每个顶点出现且只出现一次
• 若顶点A在序列中排在顶点B的前面。则不存在B——>A的路径

常用思路

• 选择一个没有前驱结点的图并输出
• 删除该结点和所有以他为结点的边

如果发现结点数量不够则是因为存在回路

关键路径

• AOE网：以顶点表示事件，以有向边表示活动，以边上的权值表示该活动的开销
• AOE网仅有一个入度为0的顶点，称为开始顶点（源点），也仅有一个出度为0的顶点，称为结束顶点（汇点）
• 从源点到汇点的最大路径长度的路径为关键路径，关键路径上的活动叫做关键活动，完成整个工程的最短时间称为关键路径的长度