第十二章

图的储存

12.1  基本概念

图（Graph）是数据结构中的最后一个“堡垒”——攻下它，数据结构就结束了。但就像在打游戏的最终BOSS一样，BOSS肯定是最强的，图也一样，它比线性表和树都更为复杂。在线性表中，数据元素间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继，也就是“一对一”的关系；在树形结构中，数据元素之间有着比较明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（儿子）相关，但只能和上一层中的一个元素（父亲）相关，也就是它是“一对多”的关系。到了图形结构中，数据元素之间的关系就可以是任意的，图中任意两个数据元素之间都可能相关，即“多对多”的关系。因此，图在200多年的发展中，应用极其广泛。这也造成了大部分高级的算法分析都不可避免地要用到图的知识。

不管图形结构有多复杂，我们要做的第一步必定是要先把它用某种结构储存起来。关于这一点，我们在树里面已经有了体会——对树的学习，关键是学习如何建树以及排序。我们要透过现象看本质，别看书里唧歪了半天，列了好多种储存图的方法，但其核心其实只有一个，那就是邻接矩阵（Adjacency Matrix）。但邻接矩阵的缺点是它对空间的耗费比较大，因为它是用一个二维数组来储存图的顶点和边的信息的——如果有N个顶点，则需要有N ^ 2的空间来储存。因此，如果图是稀疏的，那么我们就可以用邻接表（Adjacency List）来储存它，充分发挥链表的动态规划空间的优点。

下面我就分别给出这两种结构的代码实现。其中，邻接表使用了前面所写的单链表的类，因此在具体的实现上并不会太困难。另外，由于图结构本身比较复杂的原因，我无法把基类写得十分具有通用性，但它们应该已经可以基本满足后面的学习的需要了。

12.2  邻接矩阵

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   MatrixGraph.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 0:01:12
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __MATRIX_GRAPH_H__
#define __MATRIX_GRAPH_H__

#include <iostream>
using namespace std;

#include <assert.h>
#include <crtdbg.h>

#ifdef _DEBUG
#define DEBUG_NEW new (_NORMAL_BLOCK, THIS_FILE, __LINE__)
#endif

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#ifdef _DEBUG
#ifndef ASSERT
#define ASSERT  assert
#endif
#else   // not _DEBUG
#ifndef ASSERT
#define ASSERT
#endif
#endif  // _DEBUG

template<typename T_Vertex, typename T_Edge>
class CMatrixGraph
{
    friend ostream& operator<<(ostream &os, CMatrixGraph<T_Vertex, T_Edge> &g);

private:
    int m_nVertexNum;
    int m_nEdgeNum;
    int m_nMaxVertexNum;
    T_Vertex *m_Vertex;
    T_Edge **m_Edge;
    T_Vertex m_NoVertex;
    T_Edge m_NoEdge;

public:
    CMatrixGraph(const int nMaxVertexNum);
    ~CMatrixGraph();

public:
    int GetVertexNum() const;
    int GetEdgeNum() const;
    T_Vertex& GetVertexAt(const int n);
    T_Vertex  GetVertexAt(const int n) const;
    T_Edge& GetEdgeAt(const int nVertexIndex, const int n);
    T_Edge  GetEdgeAt(const int nVertexIndex, const int n) const;
    int Find(const T_Vertex &v, int *nIndex = NULL) const;
    int InsertVertex(const T_Vertex &v);
    int InsertEdge(const T_Vertex &v1, const T_Vertex &v2, const T_Edge &e);
    int GetFirstAdjVertexIndex(const int n) const;
    int GetNextAdjVertexIndex(const int n, const int nn) const;
};

template<typename T_Vertex, typename T_Edge>
inline CMatrixGraph<T_Vertex, T_Edge>::CMatrixGraph(const int nMaxVertexNum)
                                     : m_nVertexNum(0),
                                       m_nEdgeNum(0),
                                       m_nMaxVertexNum(nMaxVertexNum),
                                       m_NoVertex(0), // this can be customized
                                       m_NoEdge(0)    // this can be customized
{
    int i;

    m_Edge = new T_Edge*[nMaxVertexNum];
    if (NULL == m_Edge)
        return;

    for (i = 0; i < nMaxVertexNum; ++i)
    {
        m_Edge[i] = new T_Edge[nMaxVertexNum];
    }

    m_Vertex = new T_Vertex[nMaxVertexNum];
}

template<typename T_Vertex, typename T_Edge>
inline CMatrixGraph<T_Vertex, T_Edge>::~CMatrixGraph()
{
    int i;

    delete[] m_Vertex;

    for (i = 0; i < m_nMaxVertexNum; ++i)
    {
        delete[] m_Edge[i];
    }
    delete[] m_Edge;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::Find(
    const T_Vertex &v,
    int *nIndex
) const
{
    int i;
    int nVertexNum = m_nVertexNum;

    for (i = 0; i < nVertexNum; ++i)
    {
        if (v == m_Vertex[i])
        {
            if (nIndex)
                *nIndex = i;
            return 1;
        }
    }
    return 0;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::InsertVertex(const T_Vertex &v)
{
    int i;

    if ((m_nVertexNum >= m_nMaxVertexNum) || Find(v))
        return 0;

    m_Vertex[m_nVertexNum] = v;

    for (i = 0; i < m_nMaxVertexNum; ++i)
        m_Edge[m_nVertexNum][i] = m_NoEdge;

    ++m_nVertexNum;

    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::InsertEdge(
    const T_Vertex &v1,
    const T_Vertex &v2,
    const T_Edge &e
)
{
    int nIndexV1;
    int nIndexV2;

    if (
        (v1 == v2) ||
        (!Find(v1, &nIndexV1)) ||
        (!Find(v2, &nIndexV2)) ||
        (m_Edge[nIndexV1][nIndexV2] != m_NoEdge)
    )
        return 0;

    m_Edge[nIndexV1][nIndexV2] = e;
    ++m_nEdgeNum;

    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline T_Edge& CMatrixGraph<T_Vertex, T_Edge>::GetEdgeAt(
    const int nVertexIndex,
    const int n
)
{
    if ((0 > nVertexIndex) || (nVertexIndex >= m_nMaxVertexNum))
        return m_NoEdge;

    if ((0 > n) || (n >= m_nMaxVertexNum))
        return m_NoEdge;

    return *(&m_Edge[nVertexIndex][n]);
}

template<typename T_Vertex, typename T_Edge>
inline T_Edge CMatrixGraph<T_Vertex, T_Edge>::GetEdgeAt(
    const int nVertexIndex,
    const int n
) const
{
    if ((0 > nVertexIndex) || (nVertexIndex >= m_nMaxVertexNum))
        return m_NoEdge;

    if ((0 > n) || (n >= m_nMaxVertexNum))
        return m_NoEdge;

    return m_Edge[nVertexIndex][n];
}

template<typename T_Vertex, typename T_Edge>
inline T_Vertex& CMatrixGraph<T_Vertex, T_Edge>::GetVertexAt(const int n)
{
    if ((0 > n) || (n >= m_nMaxVertexNum))
        return m_NoVertex;
    else
        return *(&m_Vertex[n]);
}

template<typename T_Vertex, typename T_Edge>
inline T_Vertex CMatrixGraph<T_Vertex, T_Edge>::GetVertexAt(const int n) const
{
    if ((0 > n) || (n >= m_nMaxVertexNum))
        return m_NoVertex;
    else
        return m_Vertex[n];
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::GetVertexNum() const
{
    return m_nVertexNum;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::GetEdgeNum() const
{
    return m_nEdgeNum;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::GetFirstAdjVertexIndex(
    const int n
) const
{
    int i;

    for (i = 0; i < m_nVertexNum; ++i)
    {
        if (m_Edge[n][i] != m_NoEdge)
            return i;
    }
    return -1;
}

template<typename T_Vertex, typename T_Edge>
inline int CMatrixGraph<T_Vertex, T_Edge>::GetNextAdjVertexIndex(
    const int n,
    const int nn
) const
{
    int i;

    for (i = nn + 1; i < m_nVertexNum; ++i)
    {
        if (m_Edge[n][i] != m_NoEdge)
            return i;
    }
    return -1;
}

template<typename T_Vertex, typename T_Edge>
inline ostream &operator<<(ostream &os, CMatrixGraph<T_Vertex, T_Edge> &g)
{
    int i;
    int j;
    int nVertexNum;

    nVertexNum = g.GetVertexNum();
    for (i = 0; i < nVertexNum; ++i)
    {
        for (j = 0; j < nVertexNum; ++j)
        {
            os << g.GetEdgeAt(i, j) << ' ';
        }
        os << endl;
    }

    return os;
}

#endif  // __MATRIX_GRAPH_H__

测试代码：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   MatrixGraph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 0:02:03
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include "MatrixGraph.h"

int main()
{
    CMatrixGraph<int, int> mgraph(4);

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    // (1)－－>(2)
    // ｜↖
    // ｜  ﹨
    // ↓    ﹨
    // (3)－－>(4)
    mgraph.InsertVertex(1);
    mgraph.InsertVertex(2);
    mgraph.InsertVertex(3);
    mgraph.InsertVertex(4);
    mgraph.InsertEdge(1, 2, 1);
    mgraph.InsertEdge(1, 3, 1);
    mgraph.InsertEdge(3, 4, 1);
    mgraph.InsertEdge(4, 1, 1);

    cout << mgraph << endl;
}

12.3  邻接链表

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   ListGraph.h
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 10:26:20
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#ifndef __LIST_GRAPH_H__
#define __LIST_GRAPH_H__

#include <iostream>
using namespace std;

#include "../../slist/src/slist.h"

template<typename T_Vertex, typename T_Edge>
class CListGraph
{
    friend ostream& operator<<(ostream &os, CListGraph<T_Vertex, T_Edge> &g);

private:
    typedef struct tagLGEdge
    {
        int nextvertexindex;
        T_Edge edata;
    } LGEdge;

    typedef struct tagLGVertex
    {
        T_Vertex vdata;
        CSList<LGEdge> *edgelist;
    } LGVertex;

    int m_nVertexNum;
    int m_nEdgeNum;
    CSList<LGVertex> m_Vertex;

public:
    CListGraph();
    ~CListGraph();
    void Output(ostream &os) const;

private:
    int GetVertexAt(const int n, LGVertex *vertex) const;
    int GetEdgeAt(const int nVertexIndex, const int n, LGEdge *edge) const;

public:
    int GetVertexNum() const;
    int GetEdgeNum() const;
    int GetVertexAt(const int n, T_Vertex *v) const;
    int GetEdgeAt(const int nVertexIndex, const int n, T_Edge *e) const;
    T_Edge GetEdgeAt(const int nVertexIndex, const int n) const;
    int Find(const T_Vertex &v, int *nIndex = NULL) const;
    int InsertVertex(const T_Vertex &v);
    int InsertEdge(const T_Vertex &v1, const T_Vertex &v2, const T_Edge &e);
    int GetFirstAdjVertexIndex(const int n) const;
    int GetNextAdjVertexIndex(const int n, const int nn) const;
};

template<typename T_Vertex, typename T_Edge>
inline CListGraph<T_Vertex, T_Edge>::CListGraph()
                                   : m_nVertexNum(0),
                                     m_nEdgeNum(0)
{
}

template<typename T_Vertex, typename T_Edge>
inline CListGraph<T_Vertex, T_Edge>::~CListGraph()
{
    int i;
    int nVertexNum = m_nVertexNum;
    CSList<LGEdge> *edgelist;

    for (i = 0; i < nVertexNum; ++i)
    {
        edgelist = m_Vertex.GetAt(i + 1).edgelist;
        if (edgelist)
        {
            edgelist->RemoveAll();
            delete edgelist;
        }
    }
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetVertexNum() const
{
    return m_nVertexNum;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetEdgeNum() const
{
    return m_nEdgeNum;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetVertexAt(
    const int n,
    LGVertex *vertex
) const
{
    ASSERT(vertex);

    if ((0 > n) || (n >= m_Vertex.GetCount()))
        return 0;

    *vertex = m_Vertex.GetAt(n + 1);
    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetVertexAt(
    const int n,
    T_Vertex *v
) const
{
    ASSERT(v);

    LGVertex vertex;

    if (GetVertexAt(n, &vertex))
    {
        *v = vertex.vdata;
        return 1;
    }
    else
        return 0;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetEdgeAt(
    const int nVertexIndex,
    const int n,
    LGEdge *edge
) const
{
    ASSERT(edge);

    LGVertex vertex;
    int nVertexEdgelistCount;

    if (0 == GetVertexAt(nVertexIndex, &vertex))
        return 0;

    if (vertex.edgelist)
        nVertexEdgelistCount = vertex.edgelist->GetCount();
    else
        return 0;

    if (
        (0 > n) ||
        (n >= nVertexEdgelistCount)
    )
        return 0;

    *edge = vertex.edgelist->GetAt(n + 1);

    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetEdgeAt(
    const int nVertexIndex,
    const int n,
    T_Edge *e
) const
{
    ASSERT(e);

    LGEdge edge;

    if (GetEdgeAt(nVertexIndex, n, &edge))
    {
        *e = edge.edata;
        return 1;
    }
    else
        return 0;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::Find(
    const T_Vertex &v,
    int *nIndex
) const
{
    int i;
    int nVertexNum = m_nVertexNum;
    LGVertex vertex;

    for (i = 0; i < nVertexNum; ++i)
    {
        vertex = m_Vertex.GetAt(i + 1);
        if (v == vertex.vdata)
        {
            if (nIndex)
                *nIndex = i;
            return 1;
        }
    }
    return 0;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::InsertVertex(const T_Vertex &v)
{
    LGVertex vertex;

    if (Find(v))
        return 0;

    vertex.vdata = v;
    vertex.edgelist = NULL;
    m_Vertex.AddTail(vertex);
    ++m_nVertexNum;

    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::InsertEdge(
    const T_Vertex &v1,
    const T_Vertex &v2,
    const T_Edge &e
)
{
    int i;
    int nIndexV1;
    int nIndexV2;
    LGEdge edge;
    CSList<LGEdge> *edgelist;
    int nVertexEdgelistCount;

    if (
        (v1 == v2) ||
        (!Find(v1, &nIndexV1)) ||
        (!Find(v2, &nIndexV2))
    )
        return 0;

    // if there's no edges, let's create it first
    edgelist = m_Vertex.GetAt(nIndexV1 + 1).edgelist;
    if (NULL == edgelist)
    {
        edgelist = new CSList<LGEdge>;
        m_Vertex.GetAt(nIndexV1 + 1).edgelist = edgelist;
    }

    // is there an edge between v1 and v2 already?
    nVertexEdgelistCount = edgelist->GetCount();
    for (i = 0; i < nVertexEdgelistCount; ++i)
    {
        edge = edgelist->GetAt(i + 1);
        if (
            (edge.edata == e) &&
            (edge.nextvertexindex == nIndexV2)
        )
            return 0;
    }

    // new edge's data
    edge.edata = e;
    edge.nextvertexindex = nIndexV2;

    edgelist->AddTail(edge);

    ++m_nEdgeNum;

    return 1;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetFirstAdjVertexIndex(
    const int n
) const
{
    LGVertex vertex;

    if (0 == GetVertexAt(n, &vertex))
        return -1;
    if (vertex.edgelist)
        return vertex.edgelist->GetHead().nextvertexindex;
    return -1;
}

template<typename T_Vertex, typename T_Edge>
inline int CListGraph<T_Vertex, T_Edge>::GetNextAdjVertexIndex(
    const int n,
    const int nn
) const
{
    LGEdge edge;
    LGVertex vertex;
    int nVertexEdgelistCount;

    if (0 == GetVertexAt(n, &vertex))
        return -1;

    if (vertex.edgelist)
        nVertexEdgelistCount = vertex.edgelist->GetCount();
    else
        return -1;

    if (
        (0 > nn) ||
        ((nn + 1) >= nVertexEdgelistCount)
    )
        return -1;

    edge = vertex.edgelist->GetAt((nn + 1) + 1);

    return edge.nextvertexindex;
}

template<typename T_Vertex, typename T_Edge>
inline void CListGraph<T_Vertex, T_Edge>::Output(ostream &os) const
{
    int i;
    int j;
    LGEdge edge;
    LGVertex vertex;
    int nVertexNum;
    int nVertexEdgelistCount;

    nVertexNum = GetVertexNum();
    for (i = 0; i < nVertexNum; ++i)
    {
        if (0 == GetVertexAt(i, &vertex))
            return ;
        os << "(V" << i + 1 << ") ";
        os << 'V' << vertex.vdata;
        if (vertex.edgelist)
            nVertexEdgelistCount = vertex.edgelist->GetCount();
        else
            nVertexEdgelistCount = 0;
        for (j = 0; j < nVertexEdgelistCount; ++j)
        {
            os << " --> ";
            edge = vertex.edgelist->GetAt(j + 1);
            os << 'V' << edge.nextvertexindex + 1;
        }
        os << endl;
    }
}

template<typename T_Vertex, typename T_Edge>
inline ostream& operator<<(ostream &os, CListGraph<T_Vertex, T_Edge> &g)
{
    g.Output(os);
    return os;
}

#endif  // __LIST_GRAPH_H__

测试代码：

///////////////////////////////////////////////////////////////////////////////
//
//  FileName    :   ListGraph.cpp
//  Version     :   0.10
//  Author      :   Luo Cong
//  Date        :   2005-1-27 10:27:55
//  Comment     :  
//
///////////////////////////////////////////////////////////////////////////////

#include "ListGraph.h"

int main()
{
    CListGraph<int, int> lgraph;

#ifdef _DEBUG
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

    // (1)－－>(2)
    // ｜↖
    // ｜  ﹨
    // ↓    ﹨
    // (3)－－>(4)
    lgraph.InsertVertex(1);
    lgraph.InsertVertex(2);
    lgraph.InsertVertex(3);
    lgraph.InsertVertex(4);
    lgraph.InsertEdge(1, 2, 1);
    lgraph.InsertEdge(1, 3, 1);
    lgraph.InsertEdge(3, 4, 1);
    lgraph.InsertEdge(4, 1, 1);

    cout << lgraph << endl;
}