【数据结构】:图

概念:
图是另一种非线性结构,由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构。
这里写图片描述
完全图:在由n个顶点组成的无向图中,若有N(N-1)/2条边,则称为无向完全图。(也就是说任意两个顶点间都有边相连)

权重:在一些图中,边具有与之相关的数值,称为权重。(权重可以表示从一个顶点到另一个顶点的距离/花费的代价/所需的时间/次数等)

临接顶点:如果(u,v)是图中的一条边,则u和v互为临接顶点。

度:与顶点v关联的边的数目称为顶点v的度。

路径:在图G=(V,E)中,若从顶点V1出发,沿着边经过若干顶点V2,V5…到达V10,则称(V1,V2,V5,…V10)为从V1到V10的路径。

连通图:在无向图中V1到V2有路径,则称V1和V2是连通的,如图中任意两个顶点都是连通的,则称此图是连通图。

强连通图:在有向图中,若每一对顶点之间都存在路径,则称此图为强连通图。

生成树:一个无向连通图的生成树是它的极小连通子图,若图中有N个节点,则其生成树有N-1条边构成。

图的存储
一,临接矩阵
临接矩阵:将所有的顶点的信息组织成一个顶点表,然后利用矩阵来表示各顶点之间的临接关系,称为临接矩阵。
无向图的临接矩阵:
这里写图片描述
有向图的临接矩阵
这里写图片描述

//临接矩阵
template<class V,class W,bool digraph = false>
class GraphMartix
{
public:
    GraphMartix(V* vertexs, size_t n)
    {
        _vertexs.reserve(n);//扩容
        for (size_t i = 0; i < n; ++i)
        {
            _vertexs.push_back(vertexs[i]);
            _indexMap[vertexs[i]] = i;//用下标记录
        }

        _martix.resize(n);//初始化二维数组
        for (size_t i = 0; i < _martix.size(); ++i)
        {
            _martix[i].resize(n);
        }
    }

    //获取顶点下标
    size_t GetVertexIndex(const V& v)
    {
        assert(_indexMap.count(v) == 1);//已经存在
        return _indexMap[v];
    }

    //添加边 源 目标 权值
    void AddEdge(const V& src, const V& dst, const W& w)
    {
        size_t srcIndex = GetVertexIndex(src);
        size_t dstIndex = GetVertexIndex(dst);
        //权值
        _martix[srcIndex][dstIndex] = w;
        if (digraph == false)//是无向图
           _martix[dstIndex][srcIndex] = w;
    }

protected:
    map<V, size_t> _indexMap;//顶点和权值
    vector<V> _vertexs;//顶点集合
    //W** _martix; //临接矩阵
    vector<vector<W>> _martix;//二维数组临接矩阵
};

可以看出,临接矩阵虽然简单,但浪费的空间太多,尤其是有向图时,大多空间是0,解决这种问题的方法我们使用临接表来存储。

无向图的临接表:
这里写图片描述
有向图的临接表:
这里写图片描述

//临接表
template<class W>
struct LinKEdge
{
    W _w;
    size_t _srcIndex;//下标
    size_t _dstIndex;//临接顶点

    LinKEdge<W>* _next;

    LinKEdge(size_t srcIndex, size_t dstIndex, const W& w)
        :_srcIndex(srcIndex)
        , _dstIndex(dstIndex)
        , _w(w)
    {}
};

template<class V,class W,bool digraph = false>
class GraphTable
{
    typedef LinKEdge<W> Edge;
public:
    GraphTable(V* vertex, size_t n)
    {
        _vertex.reserve(n);
        for (size_t i = 0; i < n; ++i)
        {
            _vertex.push_back(vertex[i]);
            _indexMap[vertex[i]] = i;
        }
        _linkTables.resize(n, NULL);
    }

    //获取顶点下标
    size_t GetVertexIndex(const V& v)
    {
        assert(_indexMap.count(v) == 1);//已经存在
        return _indexMap[v];
    }

    void _AddEdge(size_t srcIndex, size_t dstIndex, const W& w)
    {
        Edge* tmp = new Edge(srcIndex, dstIndex, w);
        tmp->_next = _linkTables[srcIndex];
        _linkTables[srcIndex] = tmp;
    }

    void AddEdge(const V& src, const V& dst, const W& w)
    {
        size_t srcIndex = GetVertexIndex(src);
        size_t dstIndex = GetVertexIndex(dst);

        _AddEdge(srcIndex, dstIndex, w);
        if (digraph ==  false)//无向
            _AddEdge(dstIndex, srcIndex, w);
    }

private:
    vector<V> _vertex;
    map<V, size_t> _indexMap;
    vector<Edge*> _linkTables;
};

图的遍历
广度优先遍历(GFS)
广度优先遍历相当于将一个图按照一圈一圈由里及外进行遍历,即遍历完一个父节点,就开始一次遍历它的孩子节点,所以,二叉树的层序遍历其实就是广度优先遍历.

void GFS(const V& src)
    {
        size_t srcIndex = GetVertexIndex(src);
        queue<size_t> q;
        //标记已经访问过的
        vector<bool> visited;
        while (!q.empty())
        {
            size_t front = q.front();
            q.pop();
            if (visited[front] == true)//已经访问过了
                continue;
            cout << front << _vertex[front] << "->";
            visited[front] = true;
            Edge* cur = _linkTables[front];
            while (cur)
            {
                if (visited[cur->_dstIndex] == false)
                {
                    q.push(cur->_dstIndex);
                }
                cur = cur->_next;
            }
        }
    }

深度优先遍历(DFS)
深度优先遍历就是一条路走到底,相当于二叉树的前序遍历。

void DFS(const V& src)
    {
        size_t srcIndex = GetVertexIndex(src);
        vector<bool> visited;
        visited.resize(_vertex.size(), false);
        _DFS(srcIndex, visited);
    }

    void _DFS(size_t srcIndex, vector<bool>& visited)
    {
        cout << srcIndex << _vertex[srcIndex] << "->";
        visited[srcIndex] = true;

        Edge* cur = _linkTables[srcIndex];
        while (cur)
        {
            if (visited[cur->_dstIndex] == false)
            {
                _DFS(cur->_dstIndex, visited);//子问题
            }
            cur = cur->_next;
        }
    }
相关文章
相关标签/搜索