第8章图8.1图的基本概念8.2图的存储结构8.3图的遍历8.4最小生成树8.5一点到其他点最短路径问题8.6拓扑排序8.1图的基本概念�图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y∈V}或E={|x,y∈V&&Path(x,y)}�有向图与无向图是有序的。边就称为弧，x为弧尾，y为弧头。(x,y)是无序的。�完全图00001111222265433�邻接顶点�子图设有两个图G＝(V,E)和G’＝(V’,E’)。若V’⊆V且E’⊆E,则称图G’是图G的子图。0123子图0130123023�权�带权图也叫做网络。�稠密图和稀疏图eclassGraph{//图的类定义protected:intmaxVertices;//图中最大顶点数intnumEdges;//当前边数intnumVertices;//当前顶点数intgetVertexPos(Tvertex);//给出顶点vertex在图中位置public:Graph(intsz=DefaultVertices);//构造函数～Graph();//析构函数boolGraphEmpty()const//判图空否{returnnumEdges==0;}intNumberOfVertices(){returnnumVertices;}//返回当前顶点数intNumberOfEdges(){returnnumEdges;}//返回当前边数virtualTgetValue(inti);//取顶点i的值virtualEgetWeight(intv1,intv2);//取边上权值virtualintgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点virtualintgetNextNeighbor(intv,intw);//取邻接顶点w的下一邻接顶点virtualboolinsertVertex(constTvertex);//插入一个顶点vertexvirtualboolinsertEdge(intv1,intv2,Ecost);//插入边(v1,v2),权为costvirtualboolremoveVertex(intv);//删去顶点v和所有与相关联边virtualboolremoveEdge(intv1,intv2);//在图中删去边(v1,v2)};8.2图的存储表示一、邻接矩阵（相邻矩阵）�图(n个顶点)的邻接矩阵是一个二维数组edge[n][n]，�定义：⎩⎨⎧∈∈=,),(,,]][[.否则或者如果0><1AEjiEjijiEdge0123⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=0101101001011010A.edge012⎥⎥⎦⎤⎢⎢⎣⎡=000101010A.edge�邻接矩阵的特征：�无向图的邻接矩阵是对称的;�有向图的邻接矩阵可能是不对称的。�在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。�在无向图中,统计第i行(列)1的个数可得顶点i的度。网络(带权图)的邻接矩阵⎪⎩⎪⎨⎧==∉>∉<≠∞∈>∈<≠=jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA.edge863129542031⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∞∞∞∞=068053290410A.edge邻接矩阵存储图的类定义templateclassGraphmtx:publicGraph{friendistream&operator>>(istream&in,Graphmtx&G);//输入friendostream&operator<<(ostream&out,Graphmtx&G);//输出private:T*VerticesList;//顶点表E**Edge;//邻接矩阵intgetVertexPos(Tvertex){//给出顶点vertex在图中的位置for(inti=0;i
