图的存储与实现

2017-07-18 本文已影响85人贪婪的君子

图是一种非线性结构，其复杂程度要比树更甚一筹。图这种结构在数学领域中有自己专门的分支——即图论，在离散数学中有过简单的了解。

听名字觉得图论的用处可能不大，但事实上，在所有的数据结构中，图的应用是最广泛的，比如说，寻找最短路径。

1. 图的存储结构

图分为有向图和无向图两大类。顾名思义，每条边都是有方向的图称之为有向图；反之为无向图。

与树类似，图只是一种逻辑表示，不向数组可以直接进行存储。我们是将图的逻辑结构转化为一般的数据形式进行存储的。

我们为图中连接两个结点的边赋值，就得到了一条带权值的边，为所有的边赋值之后，就得到了一幅带权图，我们称之为权图。

1.2 邻接矩阵

就是将图转化为矩阵的形式存储。

两种邻接矩阵

如图是有向带权图和无向非权图的两种邻接矩阵表示。

在有向带权图的邻接矩阵中：

矩阵元素a[i][j]对应边(vi,vj)的权值，若不存在vi到vj的路径，则a[i][j]表示为无穷（存储一个-1或是很大的数值）

若为不带权值的有向图，则a[i][j]存储1或0表示存在或不存在vi到vj的路径。
注：若存在一条由结点vi指向结点vj的有向边，则称其为vi到vj的路径。

在无向非权图的邻接矩阵中：

矩阵元素a[i][j]存储1或0表示存在或不存在vi到vj的路径。

若为带权值的无向图，则a[i][j]存储其对应边的权值。
注：若两个结点有一条边相连，则这条边被称vi到vj或是vj到vi的路径。

1.2 邻接表

邻接表法就是将邻接矩阵的n行表示成n个单链表。

对于上述带权有向图的邻接矩阵转化为邻接表的形式：

邻接表

可以看出，邻接表是由顺序和链接形式共同组成的。

2. 关于图的算法

我们知道图的应用很广，所以可以预见，与图相关的算法也非常的多，遍历算法自不必多说，AOV网的排序，路径等算法则是图特有的。

2.1 图的遍历算法

与树的遍历算法思想类似，图的遍历算法也是自图中的某一顶点出发，访问图中所有的顶点，且使得每个顶点仅被访问一次。

不过由于图的结构较树结构复杂，所以遍历图的实现也并不如树那般简单。

2.1.1 深度优先遍历

深度优先遍历过程为：

首先访问给定的起始顶点v0，从v0出发访问他的一个未曾被访问过的邻接顶点v1；
然后从v1出发，访问v1未曾被访问过的邻接顶点v2；
循环上述步骤，直到到达一个顶点，该顶点不再有未被访问过的邻接顶点。
开始回溯，判断上一个顶点是否有未被访问过的邻接顶点。
- 若有，则从该点出发，重复回溯前的步骤。
- 若无，继续向上回溯。
回溯到达起始顶点v0，结束算法。

以下是递归形式的深度优先算法

void DepthFirstSearch(const int v)
{
    //为辅助数组申请空间
    int *visited = new int[graphsize];
    
    for(int k = 0; k < graphsize; k++)//数组初始化
    {
        visited[k] = 0;
    }
    
    RDFS(v, visited);//从v开始深度遍历
    delete[] visited;//释放辅助数组空间

void RDFS(const int v, int *visited)
{
    cout << v << " "; //输出v的序号
    visited[v-1] = 1;//说明v已被访问过
    int w = GetFirstNeighbor(v);//取得v的第一个邻接顶点序号
    while (w != -1)//若存在顶点w
    {
        if (visited[w-1] != 1)//若w未被访问过，从w递归访问
            RDFS(w, visited);
        w = GetNextNeighbor(v, w);//w为v关于w的下一个邻接顶点
    }
}

可以用递归形式的算法，一般我们也可以通过堆栈的方式来实现。

2.1.2 广度优先遍历

该算法的思想类似于树的层次遍历。

其过程为：

从图中某顶点v0出发，依次访问v0的各个未被访问过的邻接点。
分别从这些邻接顶点出发访问其邻接的顶点，直到图中所有的顶点都被访问过。

此为广度优先遍历算法的非递归实现：

void BFS(const int s)//迭代,利用队列，广度优先
{
    int *visited = new int [graphsize];   //graphsize表示图中顶点的个数，visited表示是否已访问
    for(int k = 0; k < graphsize; k++)
        visited[k] = 0;
    cout << s << " ";   //输出顶点序号
    visited[s-1] = 1;   //该顶点标记为已访问
    Queue q;    //创建队列
    q.QInsert(s);
    while (!q.IsEmpty())
    {
        int d;
        int v = q.QDelete(d);
        int w = GetFirstNeighbor(v);  //获取序号为v的第一个邻接顶点的序号
        while (w!=-1)
        {
            if (!visited[w])
            {
                cout << w <<" ";
                visited[w] = 1;
                q.QInsert(w);
            }
            w = GetNextNeighbor(v, w);   //返回序号为v的顶点相对于序号w的下一个邻接顶点
        }
    }
    delete[] visited;
}

2.2 图的拓扑排序

拓扑排序就是构造一个AOV网的操作。

拓扑序列就是把AOV网中的所有顶点排成一个线性序列（存在环路的AOV网无法排成拓扑序）。

AOV网：一个有向图中，顶点表示活动（或任务），有向边表示活动（或任务）之间的先后关系，这样的有向图就是AOV网。

基于拓扑序列的定义，我们可以得到拓扑排序的基本思想，拓扑排序的基本步骤如下：

从AOV网中选择一个入度为0的顶点并输出该顶点。
从AOV网中删除该顶点及其所有的出边。
重复上述步骤，直到所有顶点已输出或网中剩余顶点的入度均不为0。（不为0说明网中存在回路，无法继续进行拓扑排序。所以拓扑排序的附加功能就是检测图中是否存在回路。）

以下是拓扑排序的过程图：

拓扑排序过程

2.3 关键路径算法

在AOE网中找到具有最大长度的路径，称其为关键路径。

关键路径中的结点称为关键活动。

AOE网是表示多个活动间的时间约束关系，其中，有向边表示活动，边上的权值表示该活动所需时间。AOE网一般用于估算工程计划完成的时间。
称AOE网中，入度为0的结点为源点，出度为0的结点为汇点。

基于最早发生时间、最迟发生时间以及相关的计算式，我们可以推出求关键活动的步骤如下：

对AOE网进行拓扑排序，按顶点的拓扑序列求出格式件的最早发生时间，若网中有回路，则终止算法。
按拓扑序列的逆序求出各顶点事件的最迟发生时间。
根据最早发生时间以及最迟发生时间，求出各活动的最早开始时间以及最迟发生时间。若出现最早发生时间=最迟发生时间结点，则其为关键活动。

注：任意非空的AOE网至少存在一条关键路径。

2.4 最短路径算法

我们最早是在离散数学中接触到第一个求最短路径的算法——Dijkstra算法，该算法解决了正权单源最短路径问题。基于Dijkstra算法，我们可以很容易的就能得出每队顶点间的最短路径。

Dijkstra算法都被讲烂了，这里就不再进行讨论。
想求没对顶点之间的最短路径，我们还可以用到动态规划的方法。

我们说Dijkstra算法解决了正权最短路径问题，那么对应的，我们应该还有一个无权最短路径问题，这个无权是指每条边权值均为1，并非真的“无权”。其主要思想就是从某一顶点出发，找到最短路径为i的顶点，然后可以得到某点到其他各个顶点的所有路径长度，比较即可得出到另一点的最短路径。

不难想象，无权最短路径的实现与图的广度优先遍历类似。

2.5 Prim算法和Kruskal算法

这两种算法是用于求最小支撑树的。

n个顶点的最小支撑树：从源图中取出n-1条边，n个顶点可以组成一个连通图，该连通图的权值和最小。

二者的核心思想相类似，却稍有不同。

Prim算法是从某个顶点开始，顺次寻找使得其路径最小的边。

Prim算法过程图示

Kruskal算法则是找能够直接连接两个顶点的最短路径。

Kruskal算法过程图示

3. 图的实现

下面给出用邻接矩阵和邻接表存储的图类的主要功能清单：

const int MaxGraphSize = 256; //图的最大顶点个数
const int MaxWeight = 1000;  //边最大允许权值

//邻接矩阵实现
class Graph_Maxtrix
{
    private:
        //邻接矩阵
        int edge[MaxGraphSize][MaxGraphSize];
        //当前图中顶点个数
        int graphsize;
    public:
        Graph_Maxtrix();
        virtual ~Graph_Matrix();

        //图的属性操作
        int GraphEmpty()const { return graphsize == 0; }
        int GraphEmpty()const { return graphsize == MaxGraphSzie; }
        int NumberOfVertices()const { return graphsize; }
        int NumberOfEdge()const;   //获取边个数
        int GetWeight(cosnt int &v1, const int &v2);
        int * &GetNeighbors(const int &v); //获取顶点v的邻接顶点表
        int GetFirstNeighbors(const int v);  //获取序号为v的第一个邻接顶点的序号
        int GetNextNeighbor(const int v1, const int v2);   //返回序号为v1的顶点相对于序号v2的下一个邻接顶点
        void InsertVertex(const int &v);   //插入一个顶点
        void InsertEdge(const int &v1, const int &v2, int weight);   //插入一条边
        void DeleteEdge(cosnt int &v1, const int &v2);

        //图的基本算法
        void DepthFirst();   //递归深度优先算法
        void DFS(const int v);   //由顶点v迭代深度优先
        void BFS(const int v);    //由顶点v开始广度优先
        void TopoOrder();   //拓扑排序
        void CriticalPath();   //关键路径算法
        void ShortestPath(cosnt int v);   //非权图中求指定顶点到其他各个顶点的最短路径
        void DShoredstPath(cosnt int v);   //Dijkstra算法
        void AllLength();   //求正权图中每对顶点间的最短路径
        void Prim();
        void Kruskal();
};

struct Edge
{ 
    int VerAdj;   //邻接顶点的序号
    int cost;   //边的权值
    Edge *link;
};

struct Vertex
{
    int VerName;   //顶点名称
    Edge *adjacent;   //边链表头指针
};

//邻接表实现
class Graph_List
{
    private:
        Vertex *Head;   //顶点头指针
        int graphsize;   //图中顶点个数
    public:
        //构造与析构函数
        //图的属性操作
        //图的基本算法
}；