图论算法笔记|01图的存储结构

图是一种表示多对多关系的结构，表示图的数据结构一般有两种形式，一种是邻接矩阵，另一种是邻接表。

1. 邻接矩阵

邻接矩阵，顾名思义，是一个矩阵，它是存储着边信息的矩阵，顶点用矩阵的下标表示。对于一个邻接矩阵M，如果$M(i,j)=1$，则说明顶点$i$和顶点$j$之间存在一条边。

对于无向图来说，$M (j ,i) = M (i, j)$，所以其邻接矩阵是一个对称矩阵；
对于有向图来说，则未必是一个对称矩阵。邻接矩阵的对角线元素都为0。

下图是一个无向图和对应的邻接矩阵：

无向无权图

无向无权图使用矩阵的形式即可表示为：

邻接矩阵

邻接矩阵表示无向无权图邻接矩阵表示有权图的做法也很简单，只需要将矩阵中的值改成对应边上的权值即可。当然，这时候不连通的顶点之间的边的权值就需要设定为指定的值了。下列的代码即为建立无向无权图：

//AdjMatrix.h
#pragma once
#include <fstream>
#include <string>
#include <iostream>

class AdjMatrix
{
public:
    AdjMatrix(std::string path);
    virtual ~AdjMatrix();

private:
    int** graph;
    size_t m_nV;
    size_t m_nE;
    friend std::ostream & operator<<(std::ostream &out, AdjMatrix &m);
};


//AdjMatrix.cpp
#include "AdjMatrix.h"

AdjMatrix::AdjMatrix(std::string path)
{
    std::ifstream f(path);

    // data format: vertex edge
    f >> m_nV >> m_nE;

    graph = new int*[m_nV];
    memset(graph, 0, sizeof(int*)*m_nV);

    for (size_t i = 0; i < m_nV; i++)
    {
        graph[i] = new int[m_nV];
        memset(graph[i], 0, sizeof(int)*m_nV);
    }

    int start, end;
    while (f >> start >> end)
    {
        graph[start][end] = 1;
        graph[end][start] = 1;
    }
}


AdjMatrix::~AdjMatrix()
{
    for (size_t i = 0; i < m_nV; i++)
    {
        if (graph[i]) 
        {
            delete[] graph[i];
            graph[i] = nullptr;
        }
    }

    if (graph)
    {
        delete[] graph;
        graph = nullptr;
    }
}

std::ostream & operator<<(std::ostream &out, AdjMatrix &m)
{
    std::cout << "vertex: " << m.m_nV << ", edge: " << m.m_nE << std::endl;
    for (size_t i = 0; i < m.m_nV; i++)
    {
        for (size_t j = 0; j < m.m_nV; j++)
        {
            std::cout << m.graph[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    return out;
}

2. 邻接表

邻接表同样使用二维的容器来表示，第一维和邻接矩阵一样保存某个顶点，但是第二维保存和这个顶点相连的所有点。

邻接表

从邻接表的使用上可以看出邻接表的第二个维度可以有好几种可选的方式，比如使用简单的动态数组，或者使用一个二分搜索树，或者使用hash table。

首先来看最简单的使用动态数组(std::vector)来表示邻接表第二维数据的情形：

//AdjList.h
#pragma once
#include <fstream>
#include <string>
#include <iostream>
#include <vector>

class AdjList
{
public:
    AdjList(std::string path);
    virtual ~AdjList();
private:
    std::vector<int>* graph;
    size_t m_nV;
    size_t m_nE;
    friend std::ostream & operator<<(std::ostream &out, AdjList &m);
};

//AdjList.cpp
#include "AdjList.h"

AdjList::AdjList(std::string path)
{
    std::ifstream f(path);

    // data format: vertex edge
    f >> m_nV >> m_nE;

    graph = new std::vector<int>[m_nV];
    for (size_t i = 0; i < m_nV; i++)
    {
        graph[i] = std::vector<int>();
    }

    int start, end;
    while (f >> start >> end)
    {
        graph[start].push_back(end);
        graph[end].push_back(start);
    }
}

AdjList::~AdjList()
{
    if (graph) 
    {
        delete[] graph;
        graph = nullptr;
    }
}

std::ostream & operator<<(std::ostream &out, AdjList &m)
{
    std::cout << "AdjList, use vector" << std::endl;
    std::cout << "vertex: " << m.m_nV << ", edge: " << m.m_nE << std::endl;
    for (size_t i = 0; i < m.m_nV; i++)
    {
        std::cout << i << ": ";
        for (size_t j = 0; j < m.graph[i].size(); j++)
        {
            std::cout << m.graph[i][j] << ' ';
        }
        std::cout << std::endl;
    }
    return out;
}

使用动态数组的时候，如果我们想查看两个点$i$和$j$之间是否相连的，那么我们就需要去graph[i]这个vector中去进行一次查找，这个查找的时间复杂度就是O(E), 是否我么有更优的方式呢？二分查找的时间时间复杂度是O(lgN), 所以我们可以考虑将vector的存储方式换成二叉搜索树（set）的形式了。但是这个要注意的是建图的时候vector版本添加一个元素的复杂度是O(1), 但是在set中添加一个元素的复杂度就变成了O(lgn), 所以使用set的建图性能有所下降。使用二分搜索树表示的代码如下：

//AdjSet.h
#pragma once
#include <fstream>
#include <string>
#include <iostream>
#include <set>

class AdjSet
{
public:
    AdjSet(std::string path);
    virtual ~AdjSet();
    std::set<int>* graph;
    size_t m_nV;
    size_t m_nE;
    friend std::ostream & operator<<(std::ostream &out, AdjSet &m);
};

//AdjSet.cpp
#include "AdjSet.h"

AdjSet::AdjSet(std::string path)
{
    std::ifstream f(path);

    // data format: vertex edge
    f >> m_nV >> m_nE;

    graph = new std::set<int>[m_nV];
    for (size_t i = 0; i < m_nV; i++)
    {
        graph[i] = std::set<int>();
    }

    int start, end;
    while (f >> start >> end)
    {
        graph[start].insert(end);
        graph[end].insert(start);
    }
}

AdjSet::~AdjSet()
{
    if (graph)
    {
        delete[] graph;
        graph = nullptr;
    }
}

std::ostream & operator<<(std::ostream &out, AdjSet &m)
{
    std::cout << "AdjList, use set" << std::endl;
    std::cout << "vertex: " << m.m_nV << ", edge: " << m.m_nE << std::endl;
    for (size_t i = 0; i < m.m_nV; i++)
    {
        std::cout << i << ": ";
        for (auto j = m.graph[i].begin(); j != m.graph[i].end(); j++)
        {
            std::cout << *j << ' ';
        }
        std::cout << std::endl;
    }
    return out;
}

在vector版本的基础上我们进行了简单的修改就完成了查找的优化。我们知道在hash table中的查找效率可以达到O(1), 那么我们可以把set版本改成hash table的版本！C++11中提供了unordered_set和unordered_map两个使用hash table实现的容器，这里我们使用unordered_set的表示来实现一下。

#pragma once
#include <fstream>
#include <string>
#include <iostream>
#include <unordered_set>

class AdjHash
{
public:
    AdjHash(std::string);
    virtual ~AdjHash();
private:
    std::unordered_set<int>* graph;
    size_t m_nV;
    size_t m_nE;
    friend std::ostream & operator<<(std::ostream &out, AdjHash &m);
};

#include "AdjHash.h"



AdjHash::AdjHash(std::string path)
{
    std::ifstream f(path);

    // data format: vertex edge
    f >> m_nV >> m_nE;

    graph = new std::unordered_set<int>[m_nV];
    for (size_t i = 0; i < m_nV; i++)
    {
        graph[i] = std::unordered_set<int>();
    }

    int start, end;
    while (f >> start >> end)
    {
        graph[start].insert(end);
        graph[end].insert(start);
    }
}


AdjHash::~AdjHash()
{
    if (graph)
    {
        delete[] graph;
        graph = nullptr;
    }
}

std::ostream & operator<<(std::ostream &out, AdjHash &m)
{
    std::cout << "AdjList, use unordered_set" << std::endl;
    std::cout << "vertex: " << m.m_nV << ", edge: " << m.m_nE << std::endl;
    for (size_t i = 0; i < m.m_nV; i++)
    {
        std::cout << i << ": ";
        for (auto j = m.graph[i].begin(); j != m.graph[i].end(); j++)
        {
            std::cout << *j << ' ';
        }
        std::cout << std::endl;
    }
    return out;
}

对比上述的三种邻接表的表示方式，我们从代码上可以看到他们的结构其实是非常一致的，但是他们的底层实现却迥乎不同。为了方便我们的使用，我们可以设计一个基类然后各种不同数据结构表示的图分别从该基类上进行派生，这样我们在后面设计图算法的时候就不用去管他的底层数据表示的方式了。邻接表

4. 分析各种表示的优劣

邻接表

性能对比上图中需要说明的是最后一行中的复杂度和hash table的实现有很大的关系。这里写的是我们以一种用户的角度去看待时的复杂度。后面再挖源码去看看gcc或者msvc中是怎么实现hash table的。

文章目录

图论算法笔记|01图的存储结构

1. 邻接矩阵

2. 邻接表

4. 分析各种表示的优劣

See Also

Binean

欢迎关注微信公众号

分类

最近文章

友情链接

其它

标签