数据结构 第七章课件.ppt

第7章 图 7.1 图的概念 7.2 图的存储结构 7.3 图的遍历 ;7.1 图的概念 7.1.1 图的定义; 顶点 (Vertex)： 图中的数据元素通常称作顶点。 弧 也称有向边， v, w∈E表示从v到w的一条弧，v称弧尾(Tail)或初始点(Initial node)，w称弧头(Head) 或终端点(Terminal node)，此时的图称为有向图(Directed graph)。 若v, w ∈ E 必有 w, v ∈E，即E是对称的，则以无序对(w, v)代替这两个有序偶，表示w和v之间的一条边(Edge)，此时的图称为无向图(Undirected graph)。 如果E(G)为空集，则G中的顶点均为孤立顶点; (Vi, Vj ) Vi, Vj ;;G1 = (V1, E1) V1 = {v1,v2, v3,v4} E1 = {v1,v2,v1,v3, v3,v4,v4,v1};; 2、顶点的度 无向图中顶点v的度(degree) 为v为端点的边的数目 ，记为D(v)。 有向图中顶点v的入边的数目称为它的入度(indegree) ，记为ID(v) 。 出边的数目称为它的出度(outdegree) ，记为OD(v) 。顶点v的度等于它的入度出度之和。;3、完全图、稀疏图、稠密图;瞪淤夷蜘泰铝刁例蝗遂耕绎羚遥揖哺劝运晋泼招请纤畴坏仓鲸颖铅丢镍古数据结构 第七章课件数据结构 第七章课件;4、子图 若有两个图G = (V, E) 和G’ = (V’, E’)， 且V’ ? V，E ’ ? E，则G’是G的子图。;;; ;; 7.1.3 图的抽象数据类型; void PrintGraph(GraphTypeG, int n); //按照图中的一种表示方法输出一个图 void ClearGraph(GraphTypeGT); //清除图中动态分配的存储空间 void MinSpanGraph(GraphTypeG, int n); //求图中的最小生成树 void MinPathGraph(GraphTypeG, int n); //求图中顶点之间的最短路径 void TopolGraph(GraphTypeG, int n); //求有向图中顶点之间的拓扑序列 void KeyPathGraph(GraphTypeG, int n); //求有向带权图中的关键路径 end GeneralTree ;对于一个图,需要存储的信息应该包括:;2.定义一个邻接矩阵(Adjacency Matrix)：表示图中顶点之间邻接关系的矩阵。;;;;;void Initmatrix(adjmatrix GA, int k) { //假定k等于0为无权图,k不等于0为有权图 int i,j; for (i=0; iMaxVertexNum; i++) for (j=0; jMaxVertexNum; j++) if (i= =j) GA[i][j]=0; else if(k) GA[i][j]=MaxValue; else GA[i][j]=0; };void Create1(vexlist GV, adjmatrix GA, int n, int e) { int i,j,k,w; cout“输入”n“个顶点”endl; for (i=0; in; i++) cinGV[i]; for (i=0; in; i++) for (j=0; jn; j++) { if (i= =j) GA[i][j]=0; else GA[i][j]=MaxValue; cout“输入”e“条边”endl; for (k=1; k=e; k++) { cinijw; GA[i][j]=GA[j][i]=w; } };void PrintMatrix(adjmatrix GA, int n, int k1, int k2) { int i,j; cout“V={“; for (i=0; in-1; i++) couti‘,’; coutn-1}’endl; cout“E={“; if(k2==0){ //无权图 for (i=0; in; i++) for (j=0; jn; j++) if(GA[i][j]==1) if (k1==0) {