7. 图

7.1 图的定义和基本概念
7.2 图的存储结构
7.3 图的遍历

对应的教材章节

7.1 图的定义和基本概念

教学目的： 掌握图的定义及常用术语
教学重点： 图的常用术语
教学难点： 图的常用术语
授课内容：
一、图的定义
图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型。

ADT Graph{
数据对象V ：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={<v,w>|v,w(-V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}
基本操作P：
CreateGraph(&G,V,VR);
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G
DestroyGraph(&G);
初始条件：图G存在
操作结果：销毁图G
LocateVex(G,u);
初始条件：图G存在，u一G中顶点有相同特征
操作结果：若G中存在顶点u, 则返回该顶点在图中位置；否则返回其它信息。
GetVex(G,v);
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的值。
PutVex(&G,v,value);
初始条件：图G存在，v是G中某个顶点
操作结果：对v赋值value
FirstAdjVex(G,v);
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”
NextAdjVex(G,v,w);
初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。
操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”
InsertVex(&G,v);
初始条件：图G存在，v和图中顶点有相同特征
操作结果：在图G中增添新顶点v
DeleteVex(&G,v);
初始条件：图G存在，v是G中某个顶点
操作结果：删除G中顶点v及其相关的弧
InsertAcr(&G,v,w);
初始条件：图G存在，v和w是G中两个顶点
操作结果：在G中增添弧<v,w>,若G是无向的，则还增添对称弧<w,v>
DeleteArc(&G,v,w);
初始条件：图G存在，v和w是G中两个顶点
操作结果：在G中删除弧<v,w>,若G是无向的，则还删除对称弧<w,v>
DFSTraverser(G,v,Visit());
初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数
操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。
BFSTRaverse(G,v,Visit());
初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数
操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。
}ADT Graph
二、图的常用术语

对上图有：G1=(V1,{A1})
其中：V1={v1,v2,v3,v4} A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
如果用n表示图中顶点数目，用e表示边或弧的数目，则有：
对于无向图，e的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图。
对于有向图，e有取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。
有很少条边或弧的图称为稀疏图，反之称为稠密图。

v1与v2互为邻接点 e1依附于顶点v1和v2 v1和v2相关联 v1的度为3

对有向图，如果每一对顶点之间都有通路，则称该图为强连通图。

三、总结
图的特征
有向图与无向图的主要区别

7.2 图的存储结构

教学目的： 掌握图的二种存储表示方法
教学重点： 图的数组表示及邻接表表示法
教学难点： 邻接表表示法
授课内容：
一、数组表示法
用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。
// 图的数组（邻接矩阵）存储表示
#define INFINITY INT_MAX //最大值无穷大
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef enum{DG,DN,AG,AN} GraphKind;//有向图，有向网，无向图，无向网
typedef struct ArcCell{
VRType adj; //VRType是顶点关系类型。对无权图，用1或0表示相邻否，对带权图，则为权值类型
InfoType *info; //该弧相关停息的指针
}ArcCell,AdjMatrix[max_vertex_num][max_vertex_num];
tpyedef struct{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
GraphKind kind; //图的种类标志
}MGraph;

二、邻接表
邻接表是图的一种链式存储结构。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点，包含链域(firstarc)指向链表中第一个结点，还设有存储顶点vi的名或其它有关信息的数据域(data)。如：

#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; //图的当前顶点数和弧数
int vexnum,arcnum; //图的种类标志
int kind;
}ALGraph;

三、总结
图的存储包括哪些要素？

7.3图的遍历

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
注意：
　 以下假定遍历过程中访问顶点的操作是简单地输出顶点。

布尔向量visited[0．．n-1]的设置
　图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点V_i之后，便将visited[i]置为真。

深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义
　假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
　图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程
　设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

广度优先遍历(Breadth-FirstTraversal)

1、广度优先遍历的递归定义
    　设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w₁，w₂，…，w_t，然后再依次访问与w_l，w₂，…，w_t邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
    　若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。
    　广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。

2、广度优先搜索过程
   　 在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x₁，x₂，…，x_s和y₁，y₂，…，y_t。
    　为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x₁，x₂，…，x_s和y₁，y₂，…，y_t，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。

3、广度优先搜索算法
(1)邻接表表示图的广度优先搜索算法
  void BFS(ALGraph*G，int k)
  {// 以v_k为源点对用邻接表表示的图G进行广度优先搜索
    int i；
    CirQueue Q； //须将队列定义中DataType改为int
    EdgeNode *p；
    InitQueue(&Q)；//队列初始化
     //访问源点v_k
     printf("visit vertex：％e"，G->adjlist[k].vertex)；
    visited[k]=TRUE； 
    EnQueue(&Q，k)；//v_k已访问，将其人队。（实际上是将其序号人队）
    while(!QueueEmpty(&Q)){//队非空则执行
        i=DeQueue(&Q)； //相当于v_i出队
        p=G->adjlist[i].firstedge； //取v_i的边表头指针
        while(p){//依次搜索v_i的邻接点v_j(令p->adjvex=j)
            if(!visited[p->adivex]){ //若v_j未访问过
              printf("visitvertex：％c"，C->adjlistlp->adjvex].vertex)； //访问v_j
              visited[p->adjvex]=TRUE； 
              EnQueue(&Q，p->adjvex)；//访问过的v_j人队
             }//endif
            p=p->next；//找v_i的下一邻接点
         }//endwhile
      }//endwhile
   }//end of BFS