数据结构知识点总结12-(第六章.图)-图的存储结构及图的遍历

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html

......

数据结构知识点总结11-(第六章.图)-图的基本概念

数据结构知识点总结13-(第六章.图)-图的应用

数据结构知识点总结14-(第七章.查找)

......

第六章.图

6.4 图的存储结构

图的存储必须要完整准确的反应顶点集和边集的信息。

根据不同图的结构和算法，可以采用不同的存储方式，但不同的存储方式对程序的效率影响相当的大。因此所选的数据结构应该适合于待求解的问题。

不论是有向图还是无向图，主要的存储方式都有两种：邻接矩阵和邻接表。前者属于图的顺序存储结构，后者属于图的链式存储结构。对于十字链表了解即可。

（1）邻接矩阵存储

        所谓邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间的邻接关系的二维数组称为邻接矩阵。 有时候结点按照序号编号，则可以省略存储图顶点信息一维数组。

对于带权图而言，若顶点vi和vj之间有边连接，则邻接矩阵中对应项存放该边对应的权值，若顶点vi和vj不相连，则用∞来表示这两个顶点之间不存在边。

邻接矩阵存储有以下特点：

（1）无向图的邻接矩阵是对称矩阵，并且唯一。

（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。

（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度（出度）。

（4）用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行遍历，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

（5）稠密图适合用邻接矩阵存储表示。

（2）邻接表存储

        当一个图为稀疏图时，是用邻接矩阵表示法显然浪费了大量的存储空间。而图的邻接表存储结合了顺序存储和链式存储的方法，大大的减少了这种不必要的浪费。

        所谓邻接表就是对图G中的每个顶点Vi建立一个单链表，第i个单链表中的结点表示与顶点Vi相连的边（对于有向图则表示以顶点Vi射出的边），这个单链表就成为顶点Vi的边表（对有向图来说是出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

        顶点表结点由顶点域（data）和指向第一条邻接边的指针构成，边表结点由邻接点域和指向下一条邻接边的指针域构成。

图的邻接表存储有以下特点：

（1）如果G为无向图，则所需的存储空间为O(|V| + 2|E|)；如果G为有向图，则所需的存储空间为O(|V| + |E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。

（2）对于稀疏图，采用邻接表存储将节省存储空间。

（3）在邻接表中，给定一顶点，能很容易的找到它的所有邻边，因为只需要读取它的邻接表就可以了。在邻接矩阵中，则需要扫描一行，花费的时间是O(n)。但是如果要确定给定的两个顶点间是否存在边，则在邻接矩阵里可以立即查到，在邻接表中则需要在相应结点对应的边表中查找另一节点，效率较低。

（4）在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中结点个数即可；但求其顶点的入度，则需要遍历全部的邻接表。因此也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然这实际上与邻接表的存储方式是类似的。

（5）图邻接表表示并不唯一，这是因为在每个顶点对应的单链表中，各边结点的链接次序可以任意，取决于建立邻接表的算法以及边的输入次序。

（3）十字链表存储

邻接表和逆邻接表的整合。见图：

        弧结点中有5个域：其中尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点，链域headlink指向弧头相同的下一条弧，链域taillink指向弧尾相同的下一条弧，info域存储该弧的相关信息。这样弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上。

        顶点域中有三个域：data域存放顶点相关的数据信息，如顶点名称，firstin和firstout两个域分别指向以该顶点为弧头和弧尾的第一个弧结点。

6.5 图的遍历

        图的遍历是指从图中的某一顶点出发，按照某种搜索方式沿着途中的边对图中所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看做是一种特殊的图的遍历。图的遍历是图的一种基本的操作，其他许多操作都建立在图的遍历操作基础之上。

        图的遍历主要有两种算法：广度优先搜索和深度优先搜索。

（1）BFS

        广度优先搜索（BFS）类似于二叉树的层次遍历算法，它的基本思想是：首先访问起始顶点v0，接着由v0出发，依次访问v0各个未访问过的邻接顶点，然后再依次访问它们所有未被访问过的邻接顶点，以此类推，直到所有顶点都被访问过。类似的思想将应用于Dijkstra单源最短路径算法和prime最小生成树算法。

        广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批结点，不像深度优先搜索那样有回退的情况。因此他不是一个递归的算法，为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

下面以求解非带权图的单源最短路径问题为例介绍BFS的算法模板。

   如果图G=(V,E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数；如果没有通路，则为d(u,v)=∞。

    使用BFS，我们可以求解一个满足上述定义的非带权路径的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。

//以此模板来熟悉BFS 要背下来
void BFS_MIN_Distance(Graph G, int u){
    for(int i = 0; i < G.vexnum; i++)
        d[i] = INT_MAX;
    visited[u] = true; //标记当前顶点被访问过
    d[u] = 0; //当前节点的最短路径为0，求u到k的最短路，则输出d[k]即可。
    EnQueue(Q, u);
    while( !IsEmpty(Q) ) {
        DeQueue(Q,u);
        for(w = FirstNeighbor(G,u); w >= 0; w = NextNeighbor(G,u,w)) {
            if(!visited[w]) {
                visited[w] = true;
                d[w] = d[u]+1;
                EnQueue(Q,w);
            }
        }
    }
}

（2）DFS

        深度优先搜索(DFS)类似于树的先序遍历。正如其名称中所表达的意思一样，这种搜索算法所遵循的策略是尽可能“深”的搜索一个图。

        它的基本思想如下：首先访问图中某一起始顶点v0，然后从v0出发，访问与v0邻接且未被访问的任一定点w1，再访问与w1邻接且未被访问的任意顶点w2，……重复上述过程。当不能再继续向下访问时，一次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，若它的邻接点均被访问完毕，则继续回退执行相同的操作，直到搜索顶点均被访问过为止。

        深度优先的算法过程时递归定义的，其代码过程如下：

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
    for(v=0;v
        visited[v]=false;
    for(v=0;v
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v)
{
    visit(v);
    visited[v]=true;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w])
            DFS(G,w);
}
 

        DFS算法是一个递归算法，需要借助一个递归工作栈，故她的空间复杂度为O(|V|)。

        遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当以邻接矩阵进行表示时，查找每个顶点的邻接点所需时间为O(|V|)，故总的时间复杂度为O(|V|2)。当以邻接表表示时，查找所有顶点的临接点所需时间为O(|E|)，访问顶点所需时间为O(V)，此时，总的时间复杂度为O(|V|+|E|)。

下一篇介绍图的应用：最小生成树、最短路径、拓扑排序、关键路径

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html

......

数据结构知识点总结11-(第六章.图)-图的基本概念

数据结构知识点总结13-(第六章.图)-图的应用

数据结构知识点总结14-(第七章.查找)

......