数据结构第八节(图(下))

• 2020 年 12 月 6 日
• 笔记
• 数据结构与算法

图(下)

前面说过了对一个图，寻找最短路径的问题，这次来说最小生成树，如何把一个联通图，选出最小的边的组合而且还需满足将其所有点链接再一起，这就是最小生成树问题。

最小生成树

什么是最小生成树

最小生成树，首先需要满足树的性质和定义，给顶N个顶点的图，选择N-1条边，将这N个顶点连同，且满足边权重和是所有的生成树中最小的。下面是两种最小生成树的经典算法。

Prim算法

Prim算法的每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加\(V-1\)个边。每次总是添加从生长树包含的节点选取还没被收录的最小权值的边，且加入这条边后不会生成环。（从小树长成大树）

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需\(O（V^2）\)的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为\(O（E logV）\)。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为\(O（E+VlogV）\)。

/*
* 下面实现了一个通过连接矩阵实现的prim算法
* 首先选择第1个节点作为根节点,用一个数组dist[]来保存所有节点到数的距离
* 开始的时候dist[]初始化为和第1个点相距的边
* 如果我们已经实现了把一个节点加入到树，他的dist设置为0
* 每次从dist选择一个离树最近的点
* 将其添加到树中，同时更新其他节点到树的最小距离dist
* parents数组会保存每一个节点的根节点,根节点的根节点为-1.
* 注意所生成的图时，如果边不连同一定要设置为 INFINITY。
*/
#define INFINITY 10000000
#define NotFound -1
//find min vertex
Vertex findMin(Graph G,WeightType dist[]) {
    Vertex v, minv;
    WeightType minDist = INFINITY;
    for (int i = 0; i < G->Nvertex; i++)
    {
        if (dist[i] != 0 && dist[i] < minDist) {
            minv = i;
            minDist = dist[i];
        }
    }
    if (minDist<INFINITY)
    {
        return minv;
    }
    return NotFound;
}

//prim
int prim(Graph G) {
    WeightType dist[MAXSIZE];
    Vertex parent[MAXSIZE];
    //fist sclice 0 is the root of the tree
    for (int i = 0; i < G->Nvertex; i++)
    {
        dist[i] = G->graph[0][i];
        parent[i] = 0;
    }
    //sum of weight and the vertex number in tree
    int TotalWeigth = 0,countV = 0;
    //add 0 int tree and set 0 is root
    countV++;   dist[0] = 0;    parent[0] = -1;
    //loop
    while (true)
    {
        Vertex v = findMin(G, dist);
        //the graph has some problme,doesn't has min...tree
        if (v == NotFound) {
            break;
        }
        TotalWeigth += dist[v];
        dist[v] = 0;
        countV++;
        for (int i = 0; i < G->Nvertex; i++)
        {
            //vertex is not incloude in tree and has edge between the v
            if (dist[i] != 0 && INFINITY> G->graph[v][i]) {
                //Update distance from the tree
                if (dist[i] > G->graph[v][i]) {
                    dist[i] = G->graph[v][i];
                    parent[i] = v;
                }
            }
        }
    }
    if (countV < G->Nvertex-1) {
        return NotFound;
    }
    return TotalWeigth;
}

Kruskal算法

Kruskal算法采用的则是从所有的边种寻找权值最小的边加入生成树中，但是若加入该边会与生成树形成环则不加入该边，直到树中含有\(V-1\)条边为止，或者边用光了停止，这些边组成的就是该图的最小生成树。（将树合并）
Kruskal算法的时间复杂度为\(O（E logE）\)，适合处理稀疏图。
需要注意的是，建立最小堆的时候，记得将容量设置为顶点的平方（翻车了一下午才看出来）。

/*
* 用连接表实现Kruskal算法在于找边，和判断找到的店是否会组成环
*/
#define MINDATA -999999
#define ElementType Edge
typedef struct HeapStruct* Heap;

struct HeapStruct
{
    ElementType Elements[MAXSIZE*MAXSIZE];
    int Size;
    int Capacity;
};
//creat heap
Heap CreatHeap(int MaxSize) {
    Heap H = (Heap)malloc(sizeof(struct HeapStruct));
    H->Size = 0;
    H->Capacity = MaxSize;
    Edge e = (Edge)malloc(sizeof(struct ENode));
    e->weight = MINDATA;
    H->Elements[0] = e;
    return H;
}

void Insert(Heap H, Edge e) {
    int i = ++H->Size;
    //if X big than his father,X become father
    for (; H->Elements[i / 2]->weight > e->weight; i /= 2)
    {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = e;
}

//delete
ElementType Delete(Heap H) {
    ElementType MinItem = H->Elements[1];
    ElementType temp = H->Elements[H->Size--];
    int parent, child;
    for (parent = 1; parent * 2 <= H->Size; parent = child) {
        child = parent * 2;
        //if his right son small the the left son
        if ((child != H->Size) && (H->Elements[child]->weight > H->Elements[child + 1]->weight)) {
            child++;
        }
        //the temp is the min item int this sub tree
        if (temp->weight <= H->Elements[child]->weight) {
            break;
        }
        //move the child to the parent location
        else {
            H->Elements[parent] = H->Elements[child];
        }
    }
    H->Elements[parent] = temp;
    return MinItem;
}
//get root
int getRoot(int a, int set[]) {
    while (set[a] >= 0) {
        a = set[a];
    }
    return a;
}

bool marge(int a, int b, int set[]) {
    int root1 = getRoot(a, set);
    int root2 = getRoot(b, set);
    if (root1 == root2) {
        return false;
    }
    if (set[root1] > set[root2]) {
        set[root2] += set[root1];
        set[root1] = root2;
    }
    else {
        set[root1] += set[root2];
        set[root2] = root1;
    }
    return true;
}

int Kruskal(Graph G) {
    int set[MAXSIZE];
    int countE = 0, totalWeight = 0;
    memset(set, -1, sizeof(set));
    Heap H = CreatHeap(G->Nedge);
    for (int i = 0; i < G->Nvertex; i++)
    {
        PtrToAdjVNode temp = G->graph[i].first;
        while (temp)
        {
            Edge  e = (Edge)malloc(sizeof(struct ENode));
            e->begin = i;
            e->weight = temp->Wight;
            e->end = temp->Adjv;
            Insert(H, e);
            temp = temp->Next;
        }
    }
    while (H->Size > 0 && countE < G->Nvertex - 1)
    {
        ElementType e = Delete(H);
        //check 
        if (marge(e->begin, e->end, set)) {
            countE++;
            totalWeight += e->weight;
        }
    }
    if (countE < G->Nvertex - 1) {
        return -1;
    }
    return totalWeight;
}

课后习题(3个小题)

08-图7 公路村村通 (30point(s))

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

题解:
一个简单的最小生成树问题，注意到本题所给的为稀疏图，使用Kruskal算法会更快
prim算法：

#include <cstdio>
#include <stdlib.h>
#include <string.h>
#define WeightType int
#define MAXSIZE 1000
#define DataType int
#define Vertex int
#define NotFound -1
#define INFINITY 10000000
using namespace std;

//Use the adjacency matrix to represent the graph
typedef struct GNode* Graph;
struct GNode
{
    int Nvertex;
    int Nedge;
    WeightType graph[MAXSIZE][MAXSIZE];
    DataType Data[MAXSIZE];
};

typedef struct ENode* Edge;
struct ENode
{
    Vertex begin;
    Vertex end;
    WeightType weight;
};

//build edge
Edge BuildEdge(Vertex begin, Vertex end, WeightType weight) {
    Edge e = (Edge)malloc(sizeof(struct ENode));
    e->begin = begin;
    e->end = end;
    e->weight = weight;
    return e;
}

//creat empty graph
Graph CreateGraph(int VertexNum) {
    Graph G = (Graph)malloc(sizeof(struct GNode));
    G->Nvertex = VertexNum;
    G->Nedge = 0;
    for (int i = 0; i < G->Nvertex; i++)
    {
        for (int j = 0; j < G->Nvertex; j++)
        {
            G->graph[i][j] = INFINITY;
        }
    }
    return G;
}

//insert edge
void InsertEdge(Graph G, Edge e) {
    G->graph[e->begin][e->end] = e->weight;
    //If it is an undirected graph, you need to add the following
    G->graph[e->end][e->begin] = e->weight;
    G->Nedge++;
}

//build graph
Graph BuildGraph() {
    int Nvertex, Nedge;
    scanf("%d %d", &Nvertex, &Nedge);
    Graph G = CreateGraph(Nvertex);
    for (int i = 0; i < Nedge; i++)
    {
        Vertex begin, end;
        WeightType weight;
        scanf("%d %d %d", &begin, &end, &weight);
        InsertEdge(G, BuildEdge(begin-1, end-1, weight));
    }
    return G;
}

//find min vertex
Vertex findMin(Graph G,WeightType dist[]) {
    Vertex v, minv;
    WeightType minDist = INFINITY;
    for (int i = 0; i < G->Nvertex; i++)
    {
        if (dist[i] != 0 && dist[i] < minDist) {
            minv = i;
            minDist = dist[i];
        }
    }
    if (minDist<INFINITY)
    {
        return minv;
    }
    return NotFound;
}

//prim
int prim(Graph G) {
    WeightType dist[MAXSIZE];
    Vertex parent[MAXSIZE];
    //fist sclice 0 is the root of the tree
    for (int i = 0; i < G->Nvertex; i++)
    {
        dist[i] = G->graph[0][i];
        parent[i] = 0;
    }
    //sum of weight and the vertex number in tree
    int TotalWeigth = 0,countV = 0;
    //add 0 int tree and set 0 is root
    countV++;   dist[0] = 0;    parent[0] = -1;
    //loop
    while (true)
    {
        Vertex v = findMin(G, dist);
        //the graph has some problme,doesn't has min...tree
        if (v == NotFound) {
            break;
        }
        TotalWeigth += dist[v];
        dist[v] = 0;
        countV++;
        for (int i = 0; i < G->Nvertex; i++)
        {
            //vertex is not incloude in tree and has edge between the v
            if (dist[i] != 0 && INFINITY> G->graph[v][i]) {
                //Update distance from the tree
                if (dist[i] > G->graph[v][i]) {
                    dist[i] = G->graph[v][i];
                    parent[i] = v;
                }
            }
        }
    }
    if (countV < G->Nvertex) {
        return NotFound;
    }
    return TotalWeigth;
}

int main()
{
    Graph G = BuildGraph();
    printf("%d\n", prim(G));
    return 0;
}

Kruskal算法：

#include <cstdio>
#include <stdlib.h>
#include <string.h>
#define WeightType int
#define MAXSIZE 5001
#define DataType int
#define Vertex int
using namespace std;

//Use the adjacency List to represent the graph
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode {
    Vertex Adjv;
    WeightType Wight;
    PtrToAdjVNode Next;
};

typedef struct VNode AdjList[MAXSIZE];
struct VNode
{
    PtrToAdjVNode first;
    DataType Data;
};

typedef struct GNode* Graph;
struct GNode
{
    int Nvertex;
    int Nedge;
    AdjList graph;
};

typedef struct ENode* Edge;
struct ENode
{
    Vertex begin;
    Vertex end;
    WeightType weight;
};

//build edge
Edge BuildEdge(Vertex begin, Vertex end, WeightType weight) {
    Edge e = (Edge)malloc(sizeof(struct ENode));
    e->begin = begin;
    e->end = end;
    e->weight = weight;
    return e;
}
//creat empty graph
Graph CreateGraph(int VertexNum) {
    Graph G = (Graph)malloc(sizeof(struct GNode));
    G->Nvertex = VertexNum;
    G->Nedge = 0;
    for (int i = 0; i <= G->Nvertex; i++)
    {
        G->graph[i].first = NULL;
    }
    return G;
}

//insert edge
void InsertEdge(Graph G, Edge e) {
    PtrToAdjVNode newnode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    newnode->Wight = e->weight;
    newnode->Adjv = e->end;
    newnode->Next = G->graph[e->begin].first;
    G->graph[e->begin].first = newnode;
    G->Nedge++;
}

//build graph
Graph BuildGraph() {
    int Nvertex, Nedge;
    scanf("%d %d", &Nvertex, &Nedge);
    Graph G = CreateGraph(Nvertex);
    for (int i = 0; i < Nedge; i++)
    {
        Vertex begin, end;
        WeightType weight;
        scanf("%d %d %d", &begin, &end, &weight);
        InsertEdge(G, BuildEdge(begin - 1, end - 1, weight));
    }
    return G;
}

/*
* 用连接表实现Kruskal算法在于找边，和判断找到的店是否会组成环
*/
#define MINDATA -999999
#define ElementType Edge
typedef struct HeapStruct* Heap;

struct HeapStruct
{
    ElementType Elements[MAXSIZE*MAXSIZE];
    int Size;
    int Capacity;
};
//creat heap
Heap CreatHeap(int MaxSize) {
    Heap H = (Heap)malloc(sizeof(struct HeapStruct));
    H->Size = 0;
    H->Capacity = MaxSize;
    Edge e = (Edge)malloc(sizeof(struct ENode));
    e->weight = MINDATA;
    H->Elements[0] = e;
    return H;
}

void Insert(Heap H, Edge e) {
    int i = ++H->Size;
    //if X big than his father,X become father
    for (; H->Elements[i / 2]->weight > e->weight; i /= 2)
    {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = e;
}

//delete
ElementType Delete(Heap H) {
    ElementType MinItem = H->Elements[1];
    ElementType temp = H->Elements[H->Size--];
    int parent, child;
    for (parent = 1; parent * 2 <= H->Size; parent = child) {
        child = parent * 2;
        //if his right son small the the left son
        if ((child != H->Size) && (H->Elements[child]->weight > H->Elements[child + 1]->weight)) {
            child++;
        }
        //the temp is the min item int this sub tree
        if (temp->weight <= H->Elements[child]->weight) {
            break;
        }
        //move the child to the parent location
        else {
            H->Elements[parent] = H->Elements[child];
        }
    }
    H->Elements[parent] = temp;
    return MinItem;
}
//get root
int getRoot(int a, int set[]) {
    while (set[a] >= 0) {
        a = set[a];
    }
    return a;
}

bool marge(int a, int b, int set[]) {
    int root1 = getRoot(a, set);
    int root2 = getRoot(b, set);
    if (root1 == root2) {
        return false;
    }
    if (set[root1] > set[root2]) {
        set[root2] += set[root1];
        set[root1] = root2;
    }
    else {
        set[root1] += set[root2];
        set[root2] = root1;
    }
    return true;
}

int Kruskal(Graph G) {
    int set[MAXSIZE];
    int countE = 0, totalWeight = 0;
    memset(set, -1, sizeof(set));
    Heap H = CreatHeap(G->Nedge);
    for (int i = 0; i < G->Nvertex; i++)
    {
        PtrToAdjVNode temp = G->graph[i].first;
        while (temp)
        {
            Edge  e = (Edge)malloc(sizeof(struct ENode));
            e->begin = i;
            e->weight = temp->Wight;
            e->end = temp->Adjv;
            Insert(H, e);
            temp = temp->Next;
        }
    }
    while (H->Size > 0 && countE < G->Nvertex - 1)
    {
        ElementType e = Delete(H);
        //check 
        if (marge(e->begin, e->end, set)) {
            countE++;
            totalWeight += e->weight;
        }
    }
    if (countE < G->Nvertex - 1) {
        return -1;
    }
    return totalWeight;
}

int main()
{
    Graph G = BuildGraph();
    printf("%d\n", Kruskal(G));
    return 0;
}