数据结构ch7.ppt

第7章 图 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:} #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; 顶点结点的结构为： data 域存储和顶点相关的信息； firstin和firstout分别指向以该顶点为弧头或弧尾的第一个弧结点。 #define MAX_VERTEX_NUM 20 typedef struct ArcBox { int tailvex, headvex; // 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; // 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; // 该弧相关信息的指针 } ArcBox; typedef struct VexNode { VertexType data; ArcBox *firstin, *firstout; // 分别指向该顶点第一条入弧和出弧 } VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; // 表头向量 int vexnum, arcnum; // 有向图的当前顶点数和弧数 } OLGraph; #define MAX_VERTEX_NUM 20 typedef emnu {unvisited, visited} VisitIf; typedef struct Ebox { VisitIf mark; // 访问标记 int ivex, jvex; // 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; // 分别指向依附这两个顶点的下一条边 InfoType *info; // 该边信息指针 } EBox; typedef struct VexBox { VertexType data; EBox *firstedge; // 指向第一条依附该顶点的边 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; // 无向图的当前顶点数和边数 } AMLGraph; 与二叉树和树的遍历相同，图的“遍历”是对图中的每个顶点都进行一次访问且仅进行一次访问。但由于图结构较树和二叉树更为复杂，图中任意两个顶点之间都可能存在一条弧或边，反之也可能存在某个顶点和其它顶点之间都不存在弧或边。因此对图的遍历而言，除了要确定一条有哪些信誉好的足球投注网站路径之外，还要解决两个问题： (1)如何确保每个顶点都被访问到； (2)如何确保每个顶点只被访问一次。 //--- 下列算法使用的全局变量 --- Boolean visited[MAX]; // 访问标志数组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) VisitFunc = Visit; for (v=0; vG.vexnum; ++v) visited[v] = FALSE; for (v=0; vG.vexnum; ++v) if (!visited[v]) DFS(G, v); DFS(G,v); } void DFS(Graph G, int v) { // 从第 v 个顶点出发