图1、图的基本概念；2、图的存储结构（邻接矩阵、邻接表、十字邻接表）；3、图的遍历（深度优先搜索、广度优先搜索）；4、最小生成树（kruskul算法、prim算法）；5、最短路径（dijkstra算法、floyd算法）；6、AOV网络与拓扑排序；7、AOE网络与关键路径。图的特点7.1图的定义和术语定义：基本操作：{引用型操作}LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在和u相同的顶点，则返回该顶点在图中的位置；否则返回其它信息。NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。DeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。DFSTraverse(G,Visit());初始条件：图G存在，Visit是顶点的访问函数。操作结果：对图G进行深度优先遍历。遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。基本术语：无向图例：两个城市A和B，如果A和B之间的连线的涵义是表示两个城市的距离，则<A,B>和<B,A>是相同的，用(A,B)表示。如果A和B之间的连线的涵义是表示两城市之间人口流动的情况，则<A,B>和<B,A>是不同的。无向图中边的取值范围：0≤e≤n(n-1)/2。（用n表示图中顶点数目，用e表示边的数目。且不考虑顶点到其自身的边。）稀疏图：含有很少条边或弧的图。v3邻接点：若(v,v´)是一条边，则称顶点v和v´互为邻接点，或称v和v´相邻接；称边(v,v´)依附于顶点v和v´，或称(v,v´)与顶点v和v´相关联。度：无向图中顶点v的度是和v相关联的边的数目，记为：TD(v)。路径：从顶点v到v´的路径是一个顶点序列(v=vi,0,vi,1,…,vi,m=v´)，满足(vi,j-1,vi,j)VR或<vi,j-1,vi,j>VR，(1jm)。对无权图用1或0表示相邻否；VexNodexlist[MAX_VERTEX_NUM];//表头向量<v0,v2>,<v2,v3>vertices[i].把工程计划表示为有向图，用顶点表示事件，弧表示下一条路径长度次短的最短路径的特点：MST性质：设N=(V,E)是一个连通网，U是顶点集V指向依附于ivex的下一条边VisitIfmark;//访问标记C4,C2,C3,C5,C7,C8InfoType*info;//该边信息指针#defineMAX_VERTEX_NUM20若<i,j>是网中有向边，则i是连通分量：无向图的极大连通子图（不存在包含它的更大的连通子图）；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。生成树：所有顶点均由边连接在一起但不存在回路的图。生成森林：对于非连通图，其每个连通分量可以构造一棵生成树，合成起来就是一个生成森林。7.2图的存储结构初始令U={u0},(u0V),TE={}。1、将源点到终点的所有路径都列出来，的前面，具有这种性质的线性序列称为拓扑有序adj<closedge[j].从T中选取一个其距离值最小的顶点vj，加入S。非连通图的深度优先搜索遍历答案只能从生成树中找，因为要做到任何两个城市之for(j=0;j<G.“事件(顶点)”的最迟发生时间vl(k)visited[v]=FALSE;//初始化访问标志图的遍历按照深度优先和广度优先规则去实施，通常有深度（用n表示图中顶点数目，用e表示边的数目。#defineMAX_VERTEX_NUM20//最大顶点个数（A）1/2（B）1（C）2（D）43.{结构初始化}CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。（由两条弧组成）；(v0,v2,v3,v4)v2网的邻接矩阵可定义为：图的数组（邻接矩阵）存储表示：7.2.2邻接表（类似于树的孩子链表表示法）v2图的邻接表存储表示：弧结点#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;//该弧的尾和头顶点的位置structArcBox*hlink,*tlink;//分别指向下一个弧头相同和弧尾相同的弧的指针域InfoType*info;//该弧相关信息的指针}ArcBox;typedefstructVexNode{VertexTypedata;ArcBox*firstin,*firstout