数据结构与算法——从零开始学习（六）图

目录 第六章 图

第一节 基本概念

1.1 定义和术语
1.2 基本操作

第二节 存储结构

2.1 邻接矩阵
2.2 邻接表

第三节 图的遍历

3.1 深度优先搜索（Depth First Search，DFS）
3.2 广度优先搜索（Breadth First Search，BFS）

第四节 图的应用

4.1 最小生成树

本章小结

第六章 图

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。

第一节 基本概念
1.1 定义和术语

（1）定语：

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

（2）术语:

1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。

2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。

3、顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；（vj，vj）表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi，vj）来表示，称顶点vi和vj互为邻接点，边<vi,vj>依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi,vj>来表示，有序偶对的第一个节点vi被称为始点(或弧尾），在图中就是不带箭头的一端；有序偶对的第二个节点vj被称为终点(或弧头），在图中就是带箭头的一端。

4、无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n（n-1）/2条边。

5、有向完全图：在有一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。

6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。

7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。

8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。

9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

10、子图：对于图G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，则称图 G'是G的的一个子图。

11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图：

image.png

12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。

13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

1.2 基本操作

1、GreatGraph(G) ： 输入图G的顶点和边，建立图G的存储。
2、DestroyGraph(G) ：释放图G占用的存储空间。
3、GetVex(G，v)：在图G中找到顶点v，并返回顶点v的相关信息。
4、PutVex(G,V,value)：在图G中找到顶点v，并将value值赋予给顶点v。
5、InsertVex(G,v）：在图G中增添新顶点v。
6、DeleteVex(G,v)：在图G中，删除顶点v及所有和顶点v相关的边或弧。
7、InsertArc(G,v,w)：在图G中增添一条从顶点v到顶点w的边或弧。
8、DeleteArc(G,v,w)：在图G中删除一条从顶点v到顶点w的边或弧。
9、DFSTraverse(G,v)：在图G中，从顶点v出发深度优化遍历图G。
10、BFSTtaverse(G,v)：在图G中，从顶点v出发广度优先遍历图G。

在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图还有以下的基本操作。

11、LocateVex（G，u）：在图G中找到顶点u，返回该顶点在图中位置。
12、FirstAdjVex（G，v）：在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。
13、NextAdjVex(G，v，w)：在图G中， 返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回"空”。

第二节 存储结构

图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息及描述顶点之间的关系——边或弧的信息。因此，无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。

2.1 邻接矩阵

所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n个确定的顶点，即V ={v0,v1，···，vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵的元素为：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的边 ；2，若(vi,vj）或<vi,vj>不是E(G)中的边。

若G是网，则邻接矩阵可定义为：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。
其中，wij表示边(Vi,vj)或<vi,vj>上的权值；表示一个计算机允许的、大于所有边上权值的数。

（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。

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

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

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

在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点数和边数。故可将其形式描述如下：

#define MaxVertexNum 100 
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType vexs[MaxVertexNum];//顶点表
    EdgeType edges[MaxVertexNum] [MaxVertexNum];//相邻矩阵，即边表
    int n,e;//顶点数和边数
 }MGraph;
2.2 邻接表

邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。

在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。对于图的边表需再增设一个存储边上的信息（如权值等）的域（info）。形式如下：

#define MaxVerNu
typedef struct node{
    int adjvex;
    struct node*next;
}EdgeNode;
 
typedef struct vnode{
    VertexType vertex;
    EdgeNode *firstedge;
}VertexNode;
 
typedef VertexNode AdjList[MaxVertexNum];
 
typedef struct{
    AdjList adjlist;
    int n ,e;
}ALGraph;

若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏（e<<n(n-1)/2）的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点v1的出度，求入度，必须遍历整个整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向的逆邻接表，即对每个顶点vi建立一个链接以vi为头的弧的链表。

在建立邻接表或逆邻表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(ne)。

在邻接表上容易找到任意顶点的第一个邻接点和下一个邻结点，但要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需查找第i个或第j个链表，因此，不如邻接矩阵方便。

第3节 图的遍历

图的遍历是指从图中的任意顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上的。

3.1 深度优先搜索（Depth First Search，DFS）

类似于树的先根遍历，是树的先根遍历的推广。假设初始化状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依然从v的未被访问的邻接点出发深度优化遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。如下图：

image.png

a所示的无向图G4，进行图的深度优先搜索。假设从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索，以此类推，接着从v4,v8,v5出发进行搜索。在访问了v5之后，由于其邻接点都已经被访问了，则搜索回到v8，同理，搜索继续回到到v4,v2,v1。此时，由于v1的另一个邻接点未被访问，则查找又从v1到v3，v6，v7。显然，这是一个递归的过程。为了遍历过程中便于区分顶点是否已被访问，需要附设访问标志数组visited[0:n-1]，其初值为FALSE,一旦某个顶点被访问，则其相应的分量置为TRUE。

void DFS(Graph G,int v){
    //从第v个顶点出发递归地深度优先遍历图G
    visited[v] =TRUE;
    //访问第v个点
    VisitFunc(v);
    for(w=FirstAdjVex(G,V) ;w ;w =NextAdjVex(G,v,w))
    //对v的尚未访问邻接顶点w递归调用DFS
    if(!visited[w]) 
        DFS(G,W);
}

深度优化搜索算法实现：

void DFSTraverseAL(ALGraph *G){
        /*深度优先遍历以邻接表存储的图G*/
        int i;
        for (i=0; i<G ->n; i++)
             visited[i]=FALSE;              /*标志向量初始化*/
        for (i=0; i<G ->n; i++)
             if (!visited[i]) DFSAL(G, i);  /*vi 未访问过，从vi开始DFS搜索*/
}                                    
 
   /*DFSTraveseAL*/
void DFSAL(ALGraph *G , int i) {
     /*以Vi为出发点对邻接表存储的图G进行DFS搜索*/
      EdgeNode *p;
      printf ("visit vertex:V%c\n", G ->adjlist[i].vertex); /*访问顶点vi*/
      visited[i]=TRUE;                      /*标记vi已访问*/
      p=G ->adjlist[i].firstedge;
      //取vi边表的头指针    
      while(p){
        if(!visited[p->adjvex])
            DFSAL(G,p->adjvex);
        p = p->next;
      }
}
3.2 广度优先搜索（Breadth First Search，BFS）

类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，···的顶点。

如上图中的c，首先访问v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。得到访问序列为：v1 →v2→v3→v4→v5→v6→v7→v8。和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且为了顺次访问路径长度为1，2，3···的顶点，需要附设队列以存储已被访问的路径长度为1，2，···的顶点。从图的某一点v出发，非递归地进行广度优先遍历的过程算法如下所示：

voidBFSTraverse(Grapg G,Status （*Visit）（int v)){
    //按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visied
    for(v =0 ;v =G.vexnum ;++v)
        visited[v] =FALSE;
 
  //置空队列Q
    Init_Queue(Q);
  
//v尚未被访问
    if(!visited[v]){
        In_Queue(Q,v);//v入队列
        while(!QueueEmpty(Q)){
            Out_Queue(Q,u);
            visited[u] =TURE;
            visit(u);
            for(w =FirstAdjVex(G,u) ; w ;w =NextAdjVex(G,u,w))
            if(!visited[w] 
                In_Queue(Q,W);
        }
    }
}

下面算法给出了对以邻接矩阵为存储结构的图G进行广度优先搜索实现的C语言描述。广度优先搜索算法：

 /*广度优先遍历以邻接矩阵存储的图G*/
void BFSTraverseAL(MGraph *G)              
{   int i;
    for (i=0; i<G ->n; i++)
          visited[i]=FALSE;                 /*标志向量初始化*/
          for (i=0; i<G ->n; i++)
            if (!visited[i]) BFSM(G, i);    /* vi 未访问过，从vi开始BFS查找*/
}    
 
/*BFSTraverseAL*/
void BFSM(Mgraph *G , int k)                /*以vk为出发点，对图G进行BFS查找*/
    { int i, j;
        C_Queue Q;
        Init_Queue(&Q);
        printf("visit vertex:V%c\n",G ->vexs[k]); /*访问原点vk*/
        visited[k]=TRUE;
    In_Queue(&Q, k);                        /*原点vk入队列*/
    while (!QueueEmpty(&Q))
        { i=Out_Queue(&Q);                  /*vi 出队列*/
          for (j=0; j<G ->n; j++)           /*依次查找vi的邻接点vj*/
            if (G ->edges[i][j]= =1 && !visited[j]) /*若vj未访问*/
              { printf("visit vertex:V%c\n", G ->vexs[j]); /*访问vj */
                visited[j]=TRUE;
                In_Queue(&Q, j);            /*访问过的vj入队列*/
               }
        }
  } /*BFSM*/

分析上述算法，每个顶点最多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者的不同之处仅在于对顶点访问的顺序不同。

第4节 图的应用
4.1 最小生成树

（1）基本概念：由于生成树的定义可知，无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n-1条边。

如果无向连通图是一个网，那么，它的所有生成树中必有一棵生成树的边的权值总和最小，称这样的一棵生成树为最小代价生成树（Minimum Cost Spanning Tree），简称最小生成树（MST）。一棵生成树的代价就是树中所有的边的代价之和。

最小生成树的概念可以应用到许多实际问题中。例如，以尽可能低的总价建造城市间的通信网络，把十个城市联系在一起。在这十个城市中，任意两个城市之间都可以建造通信线路，通信线路的造价依据城市间的距离不同而不同，可以构造一个通信线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通信线路，每条边的权值表示该条通信线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。

构造最小生成树的方法很多，其中大多数算法都利用了MST性质。MST性质描述如下：
设G=(V,E)是一个连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合，再设集合U用于存放G的最小生成树的顶点。若边（u，v）是G中所有一端在U中而另一端在V-U中 具有最小权值的一条边，则存在一棵包含边（u，v）的最小生成树。关于MST性质的证明请参阅有关书籍，这里略去。

（2）Prim算法和Kruskal算法

假设G =（V，E）为一连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T={}。Prim算法的思想是，从所有u包含U，u包含V-U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U=V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。

Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。

1、U ={U1},T={};
 
2、while(U=!V)do
 
(u,v) =min{wun;u包含U，v包含V-U}
 
T =T+{(u,v)}
 
U=U+{V}
 
3、结束

Prim算法构造最小生成树的过程示意图如下：

image.png

为实现Prim算法，需设置两个辅助一维数组lowcost和closevertex，其中，lowcost用来保存集合V-U中各顶点与集合U中各顶点构成的边中具有最小权值的边的权值；数组closevertex用来保存依附于该边的在集合U中的顶点。假设初始化状态时，U={u1（出发的顶点）},这时有lowcost[0]=0,它表示顶点u1已加入集合中，数组lowcost的其他各分量的值是顶点u1到其余各顶点所构成的直接边的权值。然后不断选取最小的边（ui，uk）（u包含U,uk包含V-U），每选取一条边，就将lowcost（k）置为0，表示顶点uk已加入集合U中。由于顶点uk从集合V-U进入集合U后，这两个集合的内容发生了变化，就需依据具体情况更新数组lowcost和closevertex中部分分量的内容。

当无向网采用二维数组存储的邻接矩阵存储时，Prim算法如下：

void Prim(int gm[][MAXNODE],int n,int closevertex[]){
    //    从序号为0的顶点出发，建立的最小生成树存于数组closevertex中
    int lowcost[100],mincost;
    int i,j,k;
    for(i=1;i<n;i++){
        lowcost[i] =gm[0][i];
        closevertex[i] =0;
    }
    lowcost[0] = 0;//从序号0的顶点出发生成最小生成树
    closevvertex[0] = 0;
    for(i =1 ;i<n; i++){
        mincost =MAXCOST;
        j =1;        
        k =1;
        while(j<n){
            if(lowcost[j]<mincost&&lowcost[j]!=0){
                mincost =lowcost[j];
                k = j;
            }
            j ++;
        }
        lowcost[k] = 0 ;
        for(j =1 ;j<n;j++){
            if(gm[k][j] <lowcost[j]){
                lowcost[j] =gm[k][j];
                closevertex[j] = k;
            }
        }
    }
}

在上述算法中，第一个for循环的执行次数为n-1，第二个for循环中又包含了一个while循环和一个for循环，执行次数为2（n-1）²，所以Prim算法的时间复杂度为O(n²）。

Kruskal算法基本思想如下：设G=(V, E)是连通网，集合T存放G的最小生成树中的边。初始时，最小生成树中已经包含G中的全部顶点，集合T的初值为T={}，这样每个顶点就自成一个连通分量。最小生成树的生成过程是，在图G的边集E中按权值自小至大依次选择边（u, v），若该边端点u、v分别属于当前两个不同的连通分量，则将该边（u, v）加入到T，由此这两个连通分量连接成一个连通分量，整个连通分量数量就减少了一个；若u、v是当前同一个连通分量的顶点，则舍去此边，继续寻找下一条两端不属于同一连通分量的权值最小的边，依此类推，直到所有的顶点都在同一个连通分量上为止。这时集合T中包含了最小生成树的所有边。算法描述如下：

T={};
while(T中的边数<n-1){//n为G中的顶点数
从E中选取当前最短边(u,v)
删除E中条边（u，v）
if((u,v)并入T之后不产生回路)
    将(u,v)并入T中
}

Kruskal 算法构造最小生成树的过程示意图：

image.png

本章小结

图是一种重要的非线性结构。它的特点是每一个顶点都可以与其他顶点相关联，与树不同，图中各个顶点的地位都是平等的，对顶点的编号都是人为的。

通常，定义图由两个集合构成：一是顶点的非空有限集合；二是顶点与顶点之间关系（边）的有限集合。

对图的处理要区分有向图和无向图。它的存储表示可以使用邻接矩阵，也可以使用邻接表，前者属顺序存储结构，后者属链接表示。

本章还着重讨论了图的深度优先搜索和广度优先搜索算法。

对于带权图，给出了构造最小生成树的方法：

Prim算法和Kruskal算法。在解决最短路径问题时，采用了逐步求解的策略。最后讨论的主要概念是拓扑排序，在解决应用问题时它们十分有用。

本章的要点简述如下。

（1）主要要求理解图的基本概念，包括图的定义和术语、图的连通性、图的路径和路径长度、图中各顶点的度、无向连通图和有向强连通图的最大边数和最小边数、最小生成树，以及拓扑排序和最短路径等。

（2）掌握图的存储表示，包括邻接矩阵和邻接表，以及这些存储表示上的典型操作，如图的构造、插入和删除顶点与边、查找一个顶点的某一个邻接顶点与邻接边等操作的实现算法。要求掌握图的两种遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）算法，以及求解连通性问题的方法。

原文链接：https://blog.csdn.net/csdn_aiyang/java/article/details/85047153

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,185评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,445评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,684评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,564评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,681评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,874评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,025评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,761评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,217评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,545评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,694评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,351评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,988评论 3赞 315
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,778评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,007评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,427评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,580评论 2赞 349