【数据结构】图

定义图$G=(V,E)$无序对，$V(G)$记为顶点集，$E(G)$为边集网带权图称做网

存储结构 1.邻接矩阵：顶点$i,j$之间有边则矩阵的$i,j$元为该边权大小,无边设置为inf，环设置为0 具体实现如下：

const int MAXN = 1000; //最大顶点数

int matrix[MAXN][MAXN];

int main()
{
    int u,v,w;
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        cin>>u>>v>>w; //u v 连边 权值w
        matrix[u][v] = w;
        // 下一行在无向图时使用
        // matrix[v][u] = w; // 无向图的对称性
    }
}

2.邻接表：每个顶点是一个动态数组，存放其指向的另一个顶点边。逆邻接表：存放指向该顶点的边。具体实现如下：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000; //最大顶点数

struct Edge{
    int u;
    int v;
    int w;
    Edge(int u,int v,int w):u(u),v(v),w(w){}
}; // 此结构并非必要 在无权图的情况下可以直接存储其到达的其他顶点

vector<vector<Edge>> adject;


int main()
{
    int u,v,w;
    int n,m;
    cin>>n>>m;
    adject.resize(n+1); //n个顶点
    for(int i = 1; i <= n; i++)
    {
        cin>>u>>v>>w; //u v 连边 权值w
        adject[u].push_back(Edge(u,v,w)); // u -> v
        // v -> u 取决于有向图还是无向图
    }
}

基本运算

1.创建图：见上文 2.输出图 3.销毁图

其他结构

1.十字链表：顺邻接表和逆邻接表结合 2.邻接多重表

遍历 1.深度优先遍历递归 2.广度优先遍历用队列每次取出一个进行扩展 3.非连通图遍历即对每个顶点进行搜索（待填坑...）

最小生成树

生成树：含有该图的所有顶点的该图的极小连通子图，同时是一个树的结构（即不能产生回路） 生成树的性质：含有$n$个顶点的生成树一定只有$n-1$条边 最小生成树：生成树集合中权值和最小的树。

求最小生成树的算法 1.Prim算法：

描述：考虑2个顶点集U和V，初始时$U={{v_{0}}}$作为初始点，引入一个变量$d$存储$V-U$集合中每个顶点到当前集合$U$的所有顶点的距离（权值）的最小值（即对$U$中所有顶点$i$，以及$V-U$中所有顶点$j$取$d[j]=min_{i:{1->n}}(matrix[i][j])$）每次在$V-U$集合中加入一个距离$U$最近的顶点，加入该顶点后对两个集合之间的最小距离进行更新，直到所有顶点都已经加入（即统计总共更新次数为$n-1$次）实现：

/* Prim 2024.5.22 */

#include <iostream>
#include <cstring>

#define INF 9999
using namespace std;

const int MAXN = 1000; //最大顶点数


int matrix[MAXN][MAXN];

struct Edge{
    int nodeto;
    int cost;
    Edge(int nodeto,int cost):nodeto(nodeto),cost(cost){}
    Edge():nodeto(INF),cost(INF){}
}min_edge[MAXN]; // 记录V-U中顶点到U中顶点的最小距离。形式上是一个单向边

int main()
{
    int u,v,w;
    int n,m;
    cin>>n>>m;
    memset(matrix,INF,sizeof(matrix));
    for(int i = 1; i <= n ; i++)
    {
        matrix[i][i] = 0;
    }
    for(int i = 1; i <= m; i++)
    {
        cin>>u>>v>>w;
        matrix[u][v] = w;
        matrix[v][u] = w; // 本例使用无向图
    }

    int v0;
    cin>>v0; //作为最小生成树的根节点
    min_edge[v0].cost = 0; //意味着该顶点加入了U

    for(int i = 1;i<=n;i++)
    { // 即初始化 相当于第0步更新
        if(matrix[i][v0]) {
            // 有向图时为v0 i
            min_edge[i] = Edge{v0,matrix[i][v0]};
        }
    }
    for(int i = 1; i < n; i++)
    {
        int mincost = INF;
        int min_node = 0;
        for(int i = 1; i <= n; i++)
        { // 找到当前 V-U 中 距离 U 最小的顶点 注意顶点i的cost不等于0才表示该顶点没有加入U
            if(min_edge[i].cost > 0 and min_edge[i].cost<mincost)
            {
                mincost=min_edge[i].cost;
                min_node = i;
            }
        }
        min_edge[min_node].cost = 0; // 标记该新找出的顶点新加入了U

        cout<<min_edge[min_node].nodeto<<"->"<<min_node<<endl; // 输出该边 或者做其他事情

        /* 通过该新加入的顶点更新V-U中所有顶点与U中顶点的最小权值 */
        for(int i = 1; i <= n; i++)
        {
            if(min_edge[i].cost != 0 and matrix[min_node][i] < min_edge[i].cost)
            {
                min_edge[i].cost = matrix[min_node][i];
                min_edge[i].nodeto = min_node;
            }
        }

    }
}

2.Kruskal算法：描述：对边从小到大进行建树，具体描述：设$T=(U,TE)$是$G$的最小生成树，初始时将$U$设置为$V$，即包含$G$中所有顶点，而$TE$设置为空，即等待加边，然后从边集中挑选最小的一个边，如果这个边加上之后，$T$不构成回路，则加入该边，直到$TE$有$n-1$条边为止。性质：此算法与Prim算法生成的最小生成树可能是不同的。实现：由于每次加边都需要判断回路，使用搜索判断回路效率过低。因此考虑采用并查集，初始$vset[i]=i$代表顶点$i$属于$i$集合，每次迭代加边时，判断当前边连接的两个顶点是否有相同的集合标号，若没有，则加入该边，并合并并查集。 Kruskal实现如下：

/* Kruskal 2024.5.24 */

#include <vector>
#include <iostream>
#include <algorithm>
#include "union_set.h"

#define INF 9999
#define MAXN 1000

using namespace std;

struct Edge{
    int u,v,w;
    Edge():u(0),v(0),w(0){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
};

vector<Edge> adj; /* 存该图的边 */

bool cmp(Edge A,Edge B)
{
    return A.w<B.w; /* 根据边权值递增 */
}

int main()
{
    int n,m;
    cin>>n>>m;
    int i,j,w;
    for(int ite = 1;ite<=m;ite++)
    {
        cin>>i>>j>>w;
        adj.push_back(Edge(i,j,w));
        adj.push_back(Edge(j,i,w)); /* 无向图存双向边 */
    }
    MAKE_SET(n);
    sort(adj.begin(),adj.end(),cmp);

    i = 0; /* 当前加了多少条边到树中 */
    j = 0; /* 当前指向的待加边 */
    while(i<n-1)
    {
        Edge tmp = adj[j];
        if(FIND_SET(tmp.u)!=FIND_SET(tmp.v))
        {
            /* 不构成回路 加边 */
            cout<<tmp.u<<"-"<<tmp.v<<" "<<tmp.w<<endl;
            UNION(tmp.u,tmp.v);
            i++;
        }
        j++;
    }
}

并查集定义与实现如下： union_set.h

#include <iostream>
#define MAXN 1000
using namespace std;

/* 在这里假定每个元素的编号为它数组的下标 */
int vset_[MAXN]; /* 作为集合的数组 存储每个元素的代表元素 */
int rank_[MAXN]; /* 按秩合并的辅助数组 记录该结点到代表元素的高度 */

/* 初始化并查集，每个元素属于自己代表的集合 */
void MAKE_SET(int n);

/* 查找x元素属于的集合的代表 */
int FIND_SET(int x);

/* 合并2个集合 */
void UNION(int x,int y);

union_set.cpp

#include "union_set.h"

void MAKE_SET(int n)
{
    for (int i = 1; i <= n; i++)
    {
        vset_[i] = i; /* 每个动态集合仅包含自己作为代表 */
        rank_[i] = 0; 
    }
}

int FIND_SET(int x)
{
    return (x==vset_[x]?x:vset_[x]=FIND_SET(vset_[x]));
    /* 若双亲是自己则返回，否则向上查找并缩短路径 */
}

void UNION(int x,int y)
{
    x = FIND_SET(x);
    y = FIND_SET(y);
    if(rank_[x]>rank_[y]) /* 此时将y合并到x树中 */
    {
        vset_[y] = x;
    }else{
        vset_[x] = y;
        if(rank_[x]==rank_[y])
        {
            rank_[y]++;
        }
    }
}

无向图的连通分量和生成树： 对无向图进行一次遍历即可形成生成树 1.深度优先生成树 2.广度优先生成树 3.生成树森林（非联通图的各连通分量的生成树组成的森林）

【数据结构】图

最小生成树

添加新评论

最新文章

最近回复

分类

归档

其它