第六节：图（上）

6.1 图

1.关于图

图表示的是“多对多”的关系。它包含：

（1）一组顶点：通常用V（Vertex）表示顶点集合。

（2）一组边：通常用E（Edge）表示边的集合，表示顶点与顶点的关系：

①边是顶点对：(v,w)∈E，其中v,w∈V。这是一个双向的。

②有向边：<v,w>，表示从v指向w的边（单行线）。

③不考虑重边和自回路。

其抽象数据类型为：

类型名称：图（Graph）

数据对象集：一非空的顶点集合Vertex和一个边集合Edge，每条边用对应的一对顶点表示。

操作集：对于任意的图G Î Graph，顶点v、v₁和v₂ Î ertex，以及任一访问顶点的函数visit()，操作举例：

Graph Create( )：构造并返回一个空图；

void Destroy( Graph G )：释放图G占用的存储空间；

Graph InsertVertex( Graph G, Vertex v )：返回一个在G中增加了新顶点v的图

Graph InsertEdge( Graph G, Vertex v₁, Vertex v₂ )：返回一个在G中增加了新边 (v₁, v₂) 的图；

Graph DeleteVertex( Graph G, Vertex v )：删除G中顶点v及其相关边，将结果图返回；

Graph DFS（ Graph G, Vertex v, visit()）：在图G中，从顶点v出发进行深度优先遍历；

图的一些分类：

（1）无向图。边（v, w）等同于边（w, v）。用圆括号“（）”表示无向边。

（2）有向图（Directed Graphs）: 边<v, w>不同于边<w, v>。用尖括号“< >”表示有向边；有向边也称“弧（Arc）”。

（3）简单图（Simple Graphs）:没有重边和自回路的图。

（4）邻接点: 如果（v, w）或 < v, w >是图中任意一条边，那么称v和w互为“邻接点（Adjacent Vertices）”。

（5）路径、简单路径、回路、无环图：

图G中从v_p 到 v_q 的路径 = { v_p, v_i₁, v_i₂, ×××, v_in, v_q } 使得( v_p, v_i₁), ( v_i₁, v_i₂), ×××, ( v_in, v_q ) 或 < v_p, v_i₁>, ×××, < v_in, v_q > 都属于E( G )。

路径长度：路径中边的数量。

简单路径：v_i₁, v_i₂, ×××, v_in 都是不同顶点。

回路：起点和终点相同（v_p = v_q ）的路径。

无环图：不存在任何回路的图。

有向无环图：不存在回路的有向图，也称DAG（Directed Acyclic Graph）。

（6）完全图：分为有向完全图（n(n-1)条边）和无向完全图（n(n-1)/2条边）。

（7）度：与顶点v相关的边数。从该点发出的边数为“出度”，指向该点的边数为“入度”。

（8）稠密图、稀疏图：是否满足 |E| > |V|log2|V|，作为稠密图和稀疏图的分界条件。

（9）权（Cost）、网络（Network）。

（10）图G的子图 G’ ： V( G’ ) Í V( G ) && E( G’ ) Í E( G )。

（11）无向图的顶点连通、连通图、连通分量：如果无向图从一个顶点v_i到另一个顶点v_j (i≠j)有路径，则称顶点v_i和v_j是“连通的（Connected）”；无向图中任意两顶点都是连通的，则称该图是“连通图（Connected Graph）”；无向图的极大连通子图称为“连通分量（Connected Component）”。连通分量的概念包含以下4个要点：子图、连通、极大顶点数、极大边数

（12）有向图的强连通图、连通分量：有向图中任意一对顶点v_i 和v_j (i≠j)均既有从v_i到v_j的路径，也有从v_j到v_i的路径，则称该有向图是“强连通图（Strongly Connected Graph）”。有向图的极大强连通子图称为“强连通分量（Strongly Connected Component）”。连通分量的概念也包含前面4个要点。

（13）树、生成树：树是图的特例：无环的无向图。

所谓连通图G的“生成树（Spanning Tree）”，是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。

生成树有可能不唯一。

当且仅当G满足下面4个条件之一（完全等价）：

① G有n-1条边，且没有环；

② G有n-1条边，且是连通的；

③ G中的每一对顶点有且只有一条路径相连；

④ G是连通的，但删除任何一条边就会使它不连通。

2.表示图——邻接矩阵

邻接矩阵G[N][N]-N个顶点从0到N-1编号。其中G[i][j]=1（若<v_i,v_j>是G中的边）或0（不是G中的边）。可以看出邻接矩阵有以下特点：

（1）主对角线全为0；

（2）这是一个对称矩阵。

那么，对于无向图来说，怎样可以节省一半空间？

可以用一个长度为N(N+1)/2的1维数组A存储{G00,G10,…,G(n-1)0,…,G(n-1)(n-1)}。则Gij在A中对应的下标是：(i*(i+1)/2+j)。对于网络，只要把G[i][j]的值定义为边<vi,vj>的权重即可。

问题：vi和vj在网络中它们之间没有边该如何表示？

邻接矩阵有以下优点：

（1）直观、简单、好理解；

（2）方便检查任意一对顶点间是否存在边；

（3）方便找任一顶点的所有“邻接点”（有边直接相连的顶点）；

（4）方便计算任一顶点的“度”：

对于无向图来说，对应行（列）非0的元素的个数。对于有向图来说，对应行非0元素的个数是“出度”，对应列非0元素的个数是“入度”。

邻接矩阵的缺点：

（1）浪费空间：存稀疏图有大量无效元素。但是对于稠密图（特别是完全图）还是很合算。

（2）浪费时间：统计系数图中一共有多少条边。

3.表示图——邻接表

邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。对于图G中的每个顶点v_i，将所有邻接于v_i的顶点v_j链成一个单链表，这个单链表就称为顶点v_i的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的邻接表。

一定要够稀疏用邻接表才合算！！！！

邻接表的特点：

（1）方便找任一顶点的所有“邻接点”。

（2）节约稀疏图的空间：需要N个头指针+2E个结点。

（3）方便计算任一顶点的“度”：对于无向图来说是如此，对于有向图来说，这只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”。

6.2 图的遍历

1.深度优先搜索（DFS）

代码实现：

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

void DFS( Graph G,  int V )

{ /* 从第V个顶点出发递归地深度优先遍历图G */

    VertexType W;

      Visited[V] = TRUE;

    VisitFunc(V);      /* 访问第V个顶点 */

    for( W = FirstAdjV(G, V);  W;  W = NextAdjV (G, V, W) )

        if( !Visited[W] )

           DFS(G, W); /* 对V的尚未访问的邻接顶点W递归调用DFS */

}

这段代码的意思是，首先我们开始访问，然后每访问一个节点，都将其标记为True，然后开始访问V的邻接点，如果没访问，那就去访问并且置为True，当看到邻接点都是True时，我们原路返回，若发现没访问过的邻接点，立即去访问；如果没有发现，继续原路返回，直到返回到第一个结点。

若由N个顶点，E跳边，时间复杂度是：

（1）用邻接表存储图：O(N+E)；

（2）用邻接矩阵，有O(N²)。

2.广度优先搜索（BFS）

相当于层序遍历。

void&nbsp;BFS(Graph&nbsp;G){&nbsp;&nbsp;&nbsp;/*&nbsp;按广度优先遍历图G。使用辅助队列Q和访问标志数组Visited&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Queue&nbsp;*Q;&nbsp;&nbsp;&nbsp;&nbsp;VertexType&nbsp;U,&nbsp;V,&nbsp;W;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(&nbsp;U&nbsp;=&nbsp;0;&nbsp;U&nbsp;&lt;&nbsp;G.n;&nbsp;++U&nbsp;)&nbsp;&nbsp;Visited[U]&nbsp;=&nbsp;FALSE;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Q&nbsp;=&nbsp;CreatQueue(&nbsp;MaxSize&nbsp;);&nbsp;/*&nbsp;创建空队列Q&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(&nbsp;U&nbsp;=&nbsp;0;&nbsp;U&lt;G.n;&nbsp;++U&nbsp;)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(!Visited[U]&nbsp;)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;若U尚未访问&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Visited[U]&nbsp;=&nbsp;TRUE;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;VisitFunc(U);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;访问U&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AddQ&nbsp;(Q,&nbsp;U);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;U入队列&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(&nbsp;!&nbsp;IsEmptyQ(Q)&nbsp;)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;V&nbsp;=&nbsp;DeleteQ(&nbsp;Q&nbsp;);&nbsp;&nbsp;/*&nbsp;&nbsp;队头元素出队并置为V&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(&nbsp;W&nbsp;=&nbsp;FirstAdjV(G,&nbsp;V);&nbsp;&nbsp;W;&nbsp;&nbsp;W&nbsp;=&nbsp;NextAdjV(G,&nbsp;V,&nbsp;W)&nbsp;)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(&nbsp;!Visited[W]&nbsp;)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Visited[W]&nbsp;=&nbsp;TRUE;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;VisitFunc&nbsp;(W);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*&nbsp;访问W&nbsp;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AddQ&nbsp;(Q,&nbsp;W);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;/*&nbsp;while结束*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;/*&nbsp;结束从U开始的BFS&nbsp;*/}

void BFS(Graph G)

{   /* 按广度优先遍历图G。使用辅助队列Q和访问标志数组Visited */

        Queue *Q;    VertexType U, V, W;

        for ( U = 0; U < G.n; ++U )  Visited[U] = FALSE;

        Q = CreatQueue( MaxSize ); /* 创建空队列Q */

        for ( U = 0; U<G.n; ++U )

         if (!Visited[U] ) {           /* 若U尚未访问 */

                 Visited[U] = TRUE;

                          VisitFunc(U);        /* 访问U */

                 AddQ (Q, U);        /* U入队列 */

                 while ( ! IsEmptyQ(Q) ) {

                     V = DeleteQ( Q );  /*  队头元素出队并置为V */

                     for( W = FirstAdjV(G, V);  W;  W = NextAdjV(G, V, W) )

                         if ( !Visited[W] ) {

                  Visited[W] = TRUE;

                                      VisitFunc (W);      /* 访问W */

                             AddQ (Q, W);

              }

                  } /* while结束*/

                  } /* 结束从U开始的BFS */

}

若由N个顶点，E跳边，时间复杂度是：

（1）用邻接表存储图：O(N+E)；

（2）用邻接矩阵，有O(N²)。

6.3 图的应用

1.应用实例：拯救007

如图1所示，如何让007通过这一个个结点（鳄鱼），一步一步跳到岸边呢？这里用深度优先算法更为合适。

原来的总体算法（伪代码）：

void&nbsp;ListComponents(Graph&nbsp;G){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(each&nbsp;V&nbsp;in&nbsp;G)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!visited[V]){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DFS(V);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}}

void ListComponents(Graph G)

{

       for(each V in G)

              if(!visited[V]){

                     DFS(V);

              }

这里的总体算法（伪代码）：

void&nbsp;Save007(Graph&nbsp;G){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(each&nbsp;V&nbsp;in&nbsp;G)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!visited[V]&amp;&amp;&nbsp;FirstJump(V))/*判断是否踩过这个鳄鱼还有是否能够得着*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer&nbsp;=&nbsp;DFS(V);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(answer&nbsp;==YES)&nbsp;break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(answer&nbsp;==YES)&nbsp;output(&quot;YES&quot;);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;output(&quot;BYEBYE&quot;);}

void Save007(Graph G)

{

       for(each V in G)

              if(!visited[V]&& FirstJump(V))/*判断是否踩过这个鳄鱼还有是否能够得着*/

              {

                     answer = DFS(V);

                     if(answer ==YES) break;

              }

              if(answer ==YES) output("YES");

              else output("BYEBYE");

}

DFS部分的伪代码：

int&nbsp;DFS(Vertex&nbsp;V){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visited[V]&nbsp;=&nbsp;True;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(IsSafe(V))&nbsp;answer&nbsp;=&nbsp;YES;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(V的每个邻接点W)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!visited[W]&amp;&amp;&nbsp;Jump(V,W))&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*Jump计算两个鳄鱼之间距离是否小于007最大跳动距离*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;answer=DFS(W);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DFS(W);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;answer;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}

int DFS(Vertex V)

{

       visited[V] = True;

       if(IsSafe(V)) answer = YES;

       else{

              for(V的每个邻接点W)

                     if(!visited[W]&& Jump(V,W))

                            /*Jump计算两个鳄鱼之间距离是否小于007最大跳动距离*/

                     {

                            answer=DFS(W);

                            DFS(W);

                     }

       return answer;            

}

6.4 图的建立

1.用邻接矩阵表示图

typedef&nbsp;struct&nbsp;GNode&nbsp;*PtrToGNode;struct&nbsp;GNode{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Nv;/*顶点数*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Ne;/*边数*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WeightType&nbsp;G[MaxVertexNum][MaxVertexNum];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DataType&nbsp;Data[MaxVertexNum];/*存顶点的数据*/};typedef&nbsp;PtrToGNode&nbsp;MGraph;/*以邻接矩阵存储的图类型*/

typedef struct GNode *PtrToGNode;

struct GNode{

       int Nv;/*顶点数*/

       int Ne;/*边数*/

       WeightType G[MaxVertexNum][MaxVertexNum];

       DataType Data[MaxVertexNum];/*存顶点的数据*/

};

typedef PtrToGNode MGraph;/*以邻接矩阵存储的图类型*/

2.初始化图

typedef&nbsp;int&nbsp;Vertex;/*用顶点下标表示顶点，为整型*/MGraph&nbsp;CreateGraph(int&nbsp;VertexNum){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Vertex&nbsp;V,W;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MGraph&nbsp;Graph;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph&nbsp;=&nbsp;(MGraph)malloc(sizeof(struct&nbsp;GNode));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;Nv&nbsp;=&nbsp;VertexNum;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;Ne&nbsp;=&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*这里默认顶点标号从0开始，到(Graph-&gt;Nv-1)*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(V=0;V&lt;Graph-&gt;Nv;V++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(W=0;W&lt;Graph-&gt;Nv;W++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[V][W]&nbsp;=&nbsp;0;/*有向图是INFINITY*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Graph;}

typedef int Vertex;/*用顶点下标表示顶点，为整型*/

MGraph CreateGraph(int VertexNum)

{

       Vertex V,W;

       MGraph Graph;

       Graph = (MGraph)malloc(sizeof(struct GNode));

       Graph->Nv = VertexNum;

       Graph->Ne = 0;

       /*这里默认顶点标号从0开始，到(Graph->Nv-1)*/

       for(V=0;V<Graph->Nv;V++)

              for(W=0;W<Graph->Nv;W++)

                     Graph->G[V][W] = 0;/*有向图是INFINITY*/

       return Graph;

}

3.插入边

typedef&nbsp;struct&nbsp;ENode&nbsp;*PtrToGNode;struct&nbsp;ENode{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Vertex&nbsp;V1,V2;/*有向边&lt;V1,V2&gt;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WeightType&nbsp;Weight;/*权重*/};typedef&nbsp;PtrToGNode&nbsp;Edge;&nbsp;void&nbsp;InsertEdge(&nbsp;MGraph&nbsp;Graph,&nbsp;Edge&nbsp;E){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*插入边&lt;V1,V2&gt;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[E-&gt;V1][E-&gt;V2]=E-&gt;Weight;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*无向图*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[E-&gt;V2][E-&gt;V1]=E-&gt;Weight;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}

typedef struct ENode *PtrToGNode;

struct ENode

{

       Vertex V1,V2;/*有向边<V1,V2>*/

       WeightType Weight;/*权重*/

};

typedef PtrToGNode Edge;

void InsertEdge( MGraph Graph, Edge E)

{

       /*插入边<V1,V2>*/

       Graph->G[E->V1][E->V2]=E->Weight;

       /*无向图*/

       Graph->G[E->V2][E->V1]=E->Weight;

}

4.建立图

（1）输入格式：Nv Ne

V1 V2 Weight

代码如下：

MGraph&nbsp;BuildGraph(){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Edge&nbsp;E;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MGraph&nbsp;Graph;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Vertex&nbsp;V;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Nv,i;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&quot;,&amp;Nv);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph&nbsp;=&nbsp;CreateGraph(Nv);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&quot;,&amp;(Graph-&gt;Ne));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(Graph-&gt;Ne!=0)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;E&nbsp;=&nbsp;(Edge)malloc(sizeof(struct&nbsp;ENode));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;Graph-&gt;Ne;i++){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&nbsp;%d&nbsp;%d&quot;,&amp;E-&gt;V1,&amp;E-&gt;V2,&amp;E-&gt;Weight);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;InsertEdge(Graph,&nbsp;E);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*如果顶点有数据的话，读入数据*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(V=0;V&lt;Graph-&gt;Nv;V++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%c&quot;,&amp;(Graph-&gt;Data[V]));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Graph;}

MGraph BuildGraph()

{     

       Edge E;

       MGraph Graph;

       Vertex V;

       int Nv,i;

       scanf("%d",&Nv);

       Graph = CreateGraph(Nv);

       scanf("%d",&(Graph->Ne));

       if(Graph->Ne!=0)

       {

              E = (Edge)malloc(sizeof(struct ENode));

              for(i=0;i<Graph->Ne;i++){

                     scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);

                     InsertEdge(Graph, E);

              }

       /*如果顶点有数据的话，读入数据*/

       for(V=0;V<Graph->Nv;V++)

              scanf("%c",&(Graph->Data[V]));

       return Graph;

}

但是这样来说太麻烦了，如果不要这么麻烦，一个整体的程序（不再需要子程序）可以如下：

int&nbsp;G[MAXN][MAXN],Nv,Ne;void&nbsp;BuildGraph(){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,j,v1,v2,w;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&quot;,&amp;Nv);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*CreateGraph*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;Nv;i++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j=0;j&lt;Nv;j++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G[i][j]=0;/*初始化，有向图为无穷*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&quot;,&nbsp;&amp;Ne);/*输入有多少个结点*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;Ne;i++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf(&quot;%d&nbsp;%d&nbsp;%d&quot;,&nbsp;&amp;v1,&amp;v2,&amp;w);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*将边插入*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G[v1][v2]=w;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;G[v2][v1]=w;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}}

int G[MAXN][MAXN],Nv,Ne;

void BuildGraph()

{

       int i,j,v1,v2,w;

       scanf("%d",&Nv);

       /*CreateGraph*/

       for(i=0;i<Nv;i++)

              for(j=0;j<Nv;j++)

                     G[i][j]=0;/*初始化，有向图为无穷*/

       scanf("%d", &Ne);/*输入有多少个结点*/

       for(i=0;i<Ne;i++)

       {

              scanf("%d %d %d", &v1,&v2,&w);

              /*将边插入*/

              G[v1][v2]=w;

              G[v2][v1]=w;

       }

一气呵成。

5.邻接表表示的图结点的结构

邻接表：G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。

typedef&nbsp;struct&nbsp;GNode&nbsp;*PtrToGNode;struct&nbsp;GNode{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Nv;/*顶点数*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;Ne;/*边数*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AdjList&nbsp;G;/*邻接表*/};typedef&nbsp;PtrToGNode&nbsp;LGraph;&nbsp;typedef&nbsp;struct&nbsp;Vnode{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PtrToAdjVNode&nbsp;FirstEdge;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;DataType&nbsp;Data;/*存顶点的数据*/}AdjList[MaxVertexNum];/*AdjList是邻接表类型*/&nbsp;typedef&nbsp;struct&nbsp;AdjVNode&nbsp;*PtrToAdjVNode;struct&nbsp;AdjVNode{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Vertex&nbsp;AdjV;/*邻接点下标*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WeightType&nbsp;Weight;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PtrToAdjVNode&nbsp;Next;/*指向下一个邻接点的指针*/};

typedef struct GNode *PtrToGNode;

struct GNode{

       int Nv;/*顶点数*/

       int Ne;/*边数*/

       AdjList G;/*邻接表*/

};

typedef PtrToGNode LGraph;

typedef struct Vnode{

       PtrToAdjVNode FirstEdge;

       DataType Data;/*存顶点的数据*/

}AdjList[MaxVertexNum];

/*AdjList是邻接表类型*/

typedef struct AdjVNode *PtrToAdjVNode;

struct AdjVNode{

       Vertex AdjV;/*邻接点下标*/

       WeightType Weight;

       PtrToAdjVNode Next;/*指向下一个邻接点的指针*/

};

6.邻接表表示的图-建立图

（1）初始化一个由VertexNum个顶点但没有边的图

typedef&nbsp;int&nbsp;Vertex;/*用顶点下标表示顶点，为整型*/LGraph&nbsp;CreateGraph(int&nbsp;VertexNum){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Vertex&nbsp;V,W;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LGraph&nbsp;Graph;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph&nbsp;=&nbsp;(LGraph)malloc(sizeof(struct&nbsp;GNode));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;Nv&nbsp;=&nbsp;VertexNum;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;Ne&nbsp;=0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*每一个顶点跟着的链表都是空的为没有边*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(V=0;V&lt;Graph-&gt;Nv;V++)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[V].FirstEdge&nbsp;=&nbsp;NULL;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Graph;}

typedef int Vertex;/*用顶点下标表示顶点，为整型*/

LGraph CreateGraph(int VertexNum)

{

       Vertex V,W;

       LGraph Graph;

       Graph = (LGraph)malloc(sizeof(struct GNode));

       Graph->Nv = VertexNum;

       Graph->Ne =0;

       /*每一个顶点跟着的链表都是空的为没有边*/

       for(V=0;V<Graph->Nv;V++)

              Graph->G[V].FirstEdge = NULL;

       return Graph;

}

（2）向LGraph中插入边

void&nbsp;InsertEdge(LGraph&nbsp;Graph,&nbsp;Edge&nbsp;E){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;PtrToAdjVNode&nbsp;NewNode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*插入边&lt;v1,v2&gt;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode&nbsp;=&nbsp;(PtrToAdjVNode)malloc(sizeof(struct&nbsp;AdjVNode));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-&gt;AdjV=E-&gt;V2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-&gt;Weight&nbsp;=&nbsp;E-&gt;Weight;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*将V2插入V1的表头*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-Next&nbsp;=&nbsp;Graph-&gt;G[E-&gt;V1].FirstEdge;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[E-&gt;V1].FirstEdge&nbsp;=&nbsp;NewNode;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*若是无向图，还要插入边&lt;V2,V1&gt;*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*为V1建立新的邻接点*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode&nbsp;=&nbsp;(PtrToAdjVNode)malloc(sizeof(struct&nbsp;AdjVNode));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-&gt;AdjV=E-&gt;V1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-&gt;Weight&nbsp;=&nbsp;E-&gt;Weight;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*将V1插入V2的表头*/&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;NewNode-Next&nbsp;=&nbsp;Graph-&gt;G[E-&gt;V2].FirstEdge;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Graph-&gt;G[E-&gt;V2].FirstEdge&nbsp;=&nbsp;NewNode;}

void InsertEdge(LGraph Graph, Edge E)

{

       PtrToAdjVNode NewNode;

       /*插入边<v1,v2>*/

       NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

       NewNode->AdjV=E->V2;

       NewNode->Weight = E->Weight;

       /*将V2插入V1的表头*/

       NewNode-Next = Graph->G[E->V1].FirstEdge;

       Graph->G[E->V1].FirstEdge = NewNode;

       /*若是无向图，还要插入边<V2,V1>*/

       /*为V1建立新的邻接点*/

       NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

       NewNode->AdjV=E->V1;

       NewNode->Weight = E->Weight;

       /*将V1插入V2的表头*/

       NewNode-Next = Graph->G[E->V2].FirstEdge;

       Graph->G[E->V2].FirstEdge = NewNode;

}

（3）完整建立LGraph

LGraph&nbsp;BuildGraph(){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LGraph&nbsp;Graph;/*剩余与邻接矩阵完整版类似*/}

LGraph BuildGraph()

{

       LGraph Graph;

/*剩余与邻接矩阵完整版类似*/

}

数据结构【浙江大学】（第6节）整理

第六节：图（上）

6.1 图

6.2 图的遍历

6.3 图的应用

6.4 图的建立

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可

发表评论取消回复

数据结构【浙江大学】（第6节）整理

第六节：图（上）

6.1 图

6.2 图的遍历

6.3 图的应用

6.4 图的建立

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可

发表评论 取消回复

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行许可

发表评论取消回复