数据结构-无向图(C++)

文章目录

对称矩阵
无向图数据结构

采用形式化的定义，图 $G$ 由两个集合 $V$ 和 $E$ 组成，记为 $G = (V, E)$ ，其中 $V$ 是顶点的有限集合，记为 $V (G)$ ， $E$ 是连接 $V$ 中两个不同顶点(顶点对)的边的有限集合，记为 $E (G)$ 。如果在图 $G$ 中，若 $\lang i,j\rang\in E(G)$ 必有 $\lang j,i\rang\in E(G)$ ，即 $E (G)$ 是对称的，则用 $(i, j)$ 代替这两个顶点对，表示顶点 $i$ 与顶点 $j$ 的一条无向边，则称 $G$ 为无向图。

图的存储结构除了要存储图中各个顶点本身的信息以外，同时还要存储顶点与顶点之间的所有关系(边的信息)。常用的图的存储结构有邻接矩阵和邻接表。由于图的结构是未知的，出于节省存储空间的考虑，采用邻接矩阵作为物理存储结构。

对称矩阵

由于考虑的是特殊的图——无向图，其邻接矩阵是一个对角线全为0的对称矩阵。因此，真正起作用的部分只有对角线上方的元素，若直接使用二维数组处理邻接矩阵将造成巨大的空间浪费。因此，有必要专门写一个“对称矩阵”类。

构造与析构

由于C++语言只提供了数组这种底层结构，并没有“上三角形”结构，因此从第一行开始逐个元素存入数组即可。¹此外，为了后续程序的方便，补写了一个对角元素的静态数据成员并赋值为0。²

template <typename T>
class sy_mat
{
                     // 为了方便存取数据，补全对角线元素，但声明为静态数据成员
    static T diag; // 对角线元素的值，默认为0
    T *a;
    unsigned n;
    sy_mat(T *p, unsigned m) : a(p), n(m) {
   }

public:
    sy_mat() : a(nullptr), n(0) {
   }
    ~sy_mat()
    {
   
        if (a)
            delete[] a;
    }
    sy_mat(const sy_mat &x)
    {
   
        if (x.a)
        {
   
            T *p(x.a);
            *(a = new T[n = x.n]) = *p;
            while (--n)
                *++a = *++p;
            ++a -= n = x.n;
        }
        else
        {
   
            n = 0;
            a = nullptr;
        }
    }
    sy_mat(unsigned k) : n(k), a(new T[k * (k - 1) / 2])
    {
   
        if (n == 1)
            a = nullptr;
    }
    sy_mat &operator=(const sy_mat &x)
    {
   
        if (a)
            delete[] a;
        if (!x.a)
        {
   
            a = nullptr;
            n = x.n;
            return *this;
        }
        T *p(x.a);
        *(a = new T[n = x.n]) = *p;
        while (--n)
            *++a = *++p;
        ++a -= n = x.n;
        return *this;
    }
};
template <typename T>
T sy_mat<T>::diag = 0;

下标访问的实现

由于人为地将上三角强制存入了一维数组，因此需要给出计算给定行列返回元素值的函数。设 $a_{ij}$ 为第 $i$ 行第 $j$ 列元素到第一个实际上存储的元素(即 $a_{12}$ )的距离。当 $i < j$ 时， $a_{ij}=\sum\limits_{k=n-i+1}^{n-1}k+j-i-1=n(i-1)-\dfrac{i(i+1)}2+j-1$ ；当 $i = j$ 时，返回diag即可；当 $i > j$ 时，利用矩阵的对称性， $a_{ij}=a_{ji}=n(j-1)-\dfrac{j(j+1)}2+i-1$ 。由于此函数将会很常用，因此重载了函数调用运算符()，方便后续的操作。

inline const T &operator()(unsigned i, unsigned j) const
{
    // 以上三角形式存储，节省存储空间
    if (i == j)
        return diag;
    if (i > j)
        return a[n * (j - 1) - j * (j + 1) / 2 + i - 1];
    return a[n * (i - 1) - i * (i + 1) / 2 + j - 1];
}
inline T &operator()(unsigned i, unsigned j)
{
   
    if (i == j)
        return diag;
    if (i > j)
        return a[n * (j - 1) - j * (j + 1) / 2 + i - 1];
    return a[n * (i - 1) - i * (i + 1) / 2 + j - 1];
}

输入

从存储结构很容易发现同一行的元素在物理存储结构上是相邻的，因此在用户输入矩阵的时候只需要将上三角的数据用指针循环存储到数组中即可。此外，还特例化了unsigned char类型的输入。³程序如下：

template <typename T>
std::istream &operator>>(std::istream &c, sy_mat<T> &x)
{
   
    std::cout << "请输入矩阵阶数:\n";
    c >> x.n;
    if (x.a)
        delete[] x.a;
    if (x.n <= 1)
    {
   
        x.a = nullptr;
        return c;
    }
    std::cout << "请输入矩阵:" << std::endl;
    T *p(x.a = new T[x.n * (x.n - 1)]), tem;
    for (unsigned i(1); i < x.n; ++i)
        for (unsigned j(1); j <= x.n; ++j)
            if (i < j)
                c >> *p++;
            else
                c >> tem;
    for (unsigned i(0); i < x.n; ++i)
        c >> tem;
    return c;
}
std::istream &operator>>(std::istream &c, sy_mat<unsigned char> &x)
{
   
    std::cout << "请输入矩阵阶数:\n";
    c >> x.n;
    if (x.a)
        delete[] x.a;
    if (x.n <= 1)
    {
   
        x.a = nullptr;
        return c;
    }
    std::cout << "请输入矩阵:" << std::endl;
    unsigned char *p(x.a = new unsigned char[x.n * (x.n - 1)]);
    unsigned short tem;
    for (unsigned i(1); i < x.n; ++i)
        for (unsigned j(1); j <= x.n; ++j)
        {
   
            c >> tem;
            if (i < j)
                *p++ = tem;
        }
    for (unsigned i(0); i < x.n; ++i)
        c >> tem;
    return c;
}

输出

由于物理存储结构与矩阵的逻辑结构上有较大差距，因此利用下标元素访问的方式套用两层循环来实现输出。程序如下：

template <typename T>
std::ostream &operator<<(std::ostream &c, const sy_mat<T> &x)
{
   
    if (!x.n)
    {
   
        c << "\t[空]" << std::endl;
        return c;
    }
    if (x.n == 1)
    {
   
        c << '0' << std::endl;
        return c;
    }
    for (unsigned i(1); i <= x.n; ++i)
    {
   
        for (unsigned j(1); j <= x.n; ++j)
            c << x(i, j) << '\t';
        c << std::endl;
    }
    return c;
}
std::ostream &operator<<(std::ostream &c, const sy_mat<unsigned char> &x)
{
   
    if (!x.n)
    {
   
        c << "\t[空]" << std::endl;
        return c;
    }
    if (x.n == 1)
    {
   
        c << '0' << std::endl;
        return c;
    }
    for (unsigned i(1); i <= x.n; ++i)
    {
   
        for (unsigned j(1); j <= x.n; ++j)
            c << short(x(i, j)) << '\t';
        c << std::endl;
    }
    return c;
}

删除行列

对于一个数学结构来说，矩阵删除行列的操作是必要的。⁴但是为了保持矩阵的对称性，删除一行的同时也需要删除一列。因此删除后的数组大小为 $\dfrac{(n-1)(n-2)}2$ ，依次赋值即可。程序如下：

sy_mat &del(unsigned k) // 删除第k行及第k列
{
   
    if (!k || k > n || !n)
        return *this;
    if (n == 1)
    {
   
        --n;
        return *this;
    }
    if (n == 2)
    {
   
        delete[] a;
        --n;
        a = nullptr;
        return *this;
    }
    T *p(new T[(n - 2) * (n - 1) / 2]), *q(p);
    for (unsigned i(1); i <= n; ++i)
        for (unsigned j(1); j <= n; ++j)
            if (i < j && i != k && j != k)
                *q++ = this->operator()(i, j);
    a = p;
    --n;
    return *this;
}

插入行列

对应地，有删除行列就有插入行列。⁵插入后的数组大小为 $\dfrac{n(n+1)}2$ ，依次赋值即可。程序如下：

sy_mat &add(unsigned k, T *b = nullptr)
{
    // 将b数组插入到第k+1行列
    if (++k > ++n)
        k = n;
    if (n == 1)
        return *this;
    T *p(a), *q(a = new T[n * (n - 1) / 2]), *t(p);
    if (b)
    {
   
        for (unsigned i(1); i <= n; ++i)
            for (unsigned j(1); j <= n; ++j)
                if (i < j)
                    if (i == k || j == k)
                        *q++ = *b++;
                    else
                        *q++ = *p++;
    }
    else
        for (unsigned i(1); i <= n; ++i)
            for (unsigned j(1); j <= n; ++j)
                if (i < j)
                    if (i == k || j == k)
                        *q++ = 0;
                    else
                        *q++ = *p++;
    if (n != 2)
        delete[] t;
    return *this;
}

无向图数据结构

构造与析构

由图的定义可知，图 $G = (V, E)$ 。其中 $V$ 是顶点的有限集合，记为 $V (G)$ ，用一个长度为n的数组存储； $E$ 是连接 $V$ 中两个不同顶点(顶点对)的边的有限集合，记为 $E (G)$ ，用邻接矩阵存储。由于领接矩阵类包含了n，为了避免空间浪费，不再单独设置长度变量来存储顶点数。程序如下：

#include "sy_mat.h"
template <typename T, typename U = unsigned char>
class graph
{
   
    T *node;     // 顶点
    sy_mat<U> W; // 邻接矩阵
public:
    graph() : node(nullptr) {
   }
    ~graph()
    {
   
        if (node)
            delete[] node;
    }
    graph(const graph &x) : W(x.W)
    {
   
        if (W.n)
        {
   
            T *p(x.node);
            *(node = new T[W.n]) = *p;
            while (--W.n)
                *++node = *++p;
            ++node -= W.n = x.W.n;
        }
        else
            node = nullptr;
    }
    graph &operator=(const graph &x)
    {
   
        W = x.W;
        if (node)
            delete[] node;
        if (!x.node)
        {
   
            node = nullptr;
            return *this;
        }
        T *p(x.node);
        *(node = new T[W.n]) = *p;
        while (--W.n)
            *++node = *++p;
        ++node -= W.n = x.W.n;
        return *this;
    }
    inline T &operator[](unsigned i) {
    return node[--i]; }
    inline const T &operator[](unsigned i) const {
    return node[--i]; }
    inline U &operator()(unsigned i, unsigned j)
    {
   
        if (i == j)
            return sy_mat<U>::diag;
        if (i > j)
            return W.a[W.n * (j - 1) - j * (j + 1) / 2 + i - 1];
        return W.a[W.n * (i - 1) - i * (i + 1) / 2 + j - 1];
    }
    inline const U &operator()(unsigned i, unsigned j) const
    {
   
        if (i == j)
            return sy_mat<U>::diag;
        if (i > j)
            return W.a[W.n * (j - 1) - j * (j + 1) / 2 + i - 1];
        return W.a[W.n * (i - 1) - i * (i + 1) / 2 + j - 1];
    }
};

图的顶点数

直接返回领接矩阵的阶数即可。程序如下：

inline unsigned size() const {
    return W.n; }

特殊顶点的操作

查找顶点

给定一个元素值查找顶点所在位置下标，同线性表。程序如下：

unsigned locateVex(T x) const
{
   
    T *p(node);
    unsigned k(1);
    if (*p == x)
        return k;
    while (++k <= W.n)
        if (*++p == x)
            return k;
    return 0;
}

第i个顶点的第1个邻接顶点

unsigned firstAdjVex(unsigned i) const
{
   
    for (unsigned j(1); j <= W.n; ++j)
        if (W(i, j))
            return j;
    return 0;
}

第i个顶点的下一个邻接顶点

unsigned nextAdjVex(unsigned i) const
{
   
    for (unsigned j(i + 1); j <= W.n; ++j)
        if (W(i, j))
            return j;
    return 0;
}

插入顶点

graph &insertnode(unsigned k, T value, U *w = nullptr)
{
   
    unsigned n((W.add(k, w)).n);
    T *p(node), *q(node = new T[n]), *t(p);
    if (++k > n)
        k = n;
    n -= k;
    while (--k)
        *q++ = *p++;
    *q = value;
    while (n--)
        *++q = *p++;
    delete[] t;
    return *this;
}

删除顶点

graph &deletenode(unsigned k)
{
   
    unsigned n(W.n);
    if (!k || k > n || !n)
        return *this;
    W.del(k);
    if (!n)
    {
   
        delete[] node;
        return *this;
    }
    T *p(node), *q(node = new T[n]), *t(p);
    ++n -= k;
    while (--k)
        *q++ = *p++;
    while (--n)
        *q++ = *++p;
    delete[] t;
    return *this;
}

输入与输出

直接让用户输入顶点集和领接矩阵。但是由于领接矩阵元素类型有可能为unsigned char，因此利用C++语言中的concepts和type_traits来判断类型。⁶

#include <concepts>
#include <type_traits>
template <typename T, typename U>
std::istream &operator>>(std::istream &c, graph<T, U> &x)
{
   
    std::cout << "请输入顶点数:\n";
    c >> x.W.n;
    std::cout << "请输入顶点:\n";
    if (x.node)
        delete[] x.node;
    T *p(x.node = new T[x.W.n]);
    for (unsigned i(0); i < x.W.n; ++i)
        c >> *p++;
    std::cout << "请输入邻接矩阵:\n";
    if (x.W.a)
        delete[] x.W.a;
    if (x.W.n <= 1)
    {
   
        x.W.a = nullptr;
        return c;
    }
    U *q(x.W.a = new U[x.W.n * (x.W.n - 1)]);
    if (std::is_same_v<U, unsigned char>)
    {
   
        unsigned short tem;
        for (unsigned i(1); i < x.W.n; ++i)
            for (unsigned j(1); j <= x.W.n; ++j)
            {
   
                c >> tem;
                if (i < j)
                    *q++ = tem;
            }
        for (unsigned i(0); i < x.W.n; ++i)
            c >> tem;
    }
    else
    {
   
        U tem;
        for (unsigned i(1); i < x.W.n; ++i)
            for (unsigned j(1); j <= x.W.n; ++j)
                if (i < j)
                    c >> *q++;
                else
                    c >> tem;
        for (unsigned i(0); i < x.W.n; ++i)
            c >> tem;
    }
    return c;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &c, const graph<T, U> &x)
{
   
    if (!x.W.n)
    {
   
        c << "\t[空]" << std::endl;
        return c;
    }
    if (x.W.n == 1)
    {
   
        c << "顶点:\n"
          << *x.node << std::endl;
        return c;
    }
    c << "顶点:\n";
    unsigned m(x.W.n);
    T *p(x.node);
    do
        c << *p++ << '\t';
    while (--m);
    c << "\n邻接矩阵:\n"
      << x.W;
    return c;
}

此时数组的大小为 $\sum\limits_{i=1}^{n-1}i=\dfrac{(n-1)n}2$ 。 ↩︎
也可以是当前数据类型中可能的最大值，代表无穷。 ↩︎
防止其直接进行字符输入。 ↩︎
对应到图中，就是删除其中一个顶点。 ↩︎
对应到图中，就是插入一个顶点。 ↩︎
这是由于C++语言不支持函数模板偏特化，因此不能直接重写函数如下：template<typename T>std::istream& operator>>(std::istream& c, graph<T, unsigned char>& x)。 ↩︎