第8章 图报告.ppt

typedef int InfoType; #define MAXV 100 //最大顶点个数 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int n,e; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 //以下定义邻接表类型 typedef struct ANode //弧的结点结构类型 { int adjvex; //该弧的终点位置 struct ANode *nextarc; //指向下一条弧的指针 InfoType info; //该弧的相关信息,这里用于存放权值 } ArcNode; typedef int Vertex; typedef struct Vnode //邻接表头结点的类型 { Vertex data; //顶点信息 int count; //存放顶点入度,只在拓扑排序中用 ArcNode *firstarc; //指向第一条弧 } VNode; typedef VNode AdjList[MAXV]; //AdjList是邻接表类型 typedef struct { AdjList adjlist; //邻接表 int n,e; //图中顶点数n和边数e } ALGraph; //图的邻接表类型 void DFS(ALGraph *G,int v) { ArcNode *p; visited[v]=1; //置已访问标记 printf(%d ,v); //输出被访问顶点的编号 p=G-adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点 while (p!=NULL) { if (visited[p-adjvex]==0) //若p-adjvex顶点未访问,递归访问它 DFS(G,p-adjvex); p=p-nextarc; //p指向顶点v的下一条弧的弧头结点 } } 三、连通图和连通分量 对于连通图，从图中任何一个顶点开始进行深度优先或者广度优先搜索一定可以访问图中所有顶点。 对于非连通图，从一个顶点出发，只能访问到该顶点所在的连通分量。 对于非连通图如何遍历才能访问到所有的顶点呢？ 图遍历的应用 假设图G采用邻接表存储，设计一个算法输出图G中从顶点u到v的所有简单路径。 p=G-adjlist[u].firstarc; //p指向顶点u的第一条弧的弧头结点 while (p!=NULL) { w=p-adjvex; //m为u的邻接顶点 if (visited[w]==0) //若该顶点未标记访问,则递归访问之 PathAll(G,w,v,path,d); p=p-nextarc; //找u的下一个邻接顶点 } visited[u]=0; //恢复环境：使该顶点可重新使用 } 8.5 有向无环图的应用 一个无环的有向图称做有向无环图（DAG图）。 有向无环图是描述一项工程或系统的进行过程的有效工具。 对于整个工程和系统，人们最关心的问题是两个方面： （1）工程是否能够顺利进行； （2）估算整个工程完成所必须的最短时间。 这两个问题就是有向图的拓扑排序和关键路径问题。 2 关键路径 例如：从v1到v9的最长路径是（v1,v2,v5,v8,v9)，路径长度是18，所有v9的最早发生时间是18。 活动a6的最早开始时间是5，最迟开始时间是8。 活动a6推迟3天开始或者延迟3天完成，都不会影响整个工程的进度。 因此，找关键路径的问题就变成了找关键活动的问题。 求ve(j)和vl(