7.1基本术语7.2存储结构7.3图的遍历7.4图的其他运算7.5图的应用1）类型定义#defineMAXV20//最大顶点数typedefstruct{Intno;Elemtypeinfo;}Vertextype;//顶点类型//图的类型定义typedefstruct{intedges[MAXV][MAXV];//邻接矩阵定义intn,e;Vertextypevexs[MAXV];//顶点表}MGraph;intLocateVex(MGraphG,Elemtypeu){inti;for(i=0;i<G.n;i++){if(u==G.vexs[i].info)returni;}if(i==G.n){printf("Erroru!\n");exit(1);}return0;}存储表示struct{intadjvex;structArcNode*nextarc;intinfo;}ArcNode;//表结点类型typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAXV];//AdjList是邻接表的类型typedefstruct{AdjListadjlist;//邻接表intn,e;}ALGraph;//图的类型图的深度优先搜索算法intvisited[MAXV];voidDFS(ALGraphG,intv){ArcNode*p;printf("%c",G.adjlist[v].data);visited[v]=1;p=G.adjlist[v].firstarc;while(p){if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;}}//从第v个顶点出发DFS整个图的DFS遍历voidDFSTraverse(ALGraphG){for(intv=0;v<G.n;++v)visited[v]=0;for(v=0;v<G.n;++v)if(!visited[v])DFS(G,v);}对于连通图，从一个顶点出发，调用DFS函数即可将所有顶点都遍历到。7.4图的其他运算1.求图的生成树（小结）例1：画出下图的生成树MinimumCostSpanningTreeKruskal算法示例：对边操作，归并边普利姆（Prim）算法示例：归并顶点一顶点到其余各顶点一、单源最短路径(Dijkstra算法)二、所有顶点之间的最短路径7.5图的应用AOE网络的用途：（1）列出所有的关键路径；（2）完成整个工程至少需要多少时间？（3）事件V5的最早完成时间是多少？（4）活动a6的最早开工时间是多少？“蒙”答有关内容：a2=10讨论：学长谈学（图的应用篇）图