第07章讲图结构.ppt

第七章 图形结构;第七章 图;Leonhard Euler (公元1707-1783年);哥尼斯堡七桥问题;例 旅行售货员问题;有如图1所示的七巧板，试编写程序，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。;问题分析: 把七巧板上每一个区域看成一个顶点, 若两个区域相邻，则相应的顶点用一条边相连，这样该问题就转化为一个图的有哪些信誉好的足球投注网站问题了。;7.1.1 图的概念;暂不讨论;V1;2. 图的基本术语 ;无向完全图：在无向图中，如果任意两个顶点之间存在边。 ;稀疏图：称边数很少的图；反之，称为稠密图。;在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；顶点v出度是指以该顶点为弧尾的弧的数目，记为OD (v)。;路径（通路） ：在无向图G=（V，E）中，从顶点vp到顶点vq之间的路径是一个顶点序列（vp=vi 0,vi1,vi2,…, vim=vq），其中，（vij-1,vij）∈E（1≤j≤m）。若G 是有向图，则路径也是有方向的，顶点序列满足vij-1,vij∈E（1≤j≤m）。 路径长度：路径上边的数目。 回路（环）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。;子图：若图G=（V，E），G=（V，E），如果V?V 且E ? E ，则称图G是G的子图。;0;在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。非连通图的极大连通子图称为连通分量。 ;B;在有向图中，对图中任意一对顶点vi 和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是强连通图。非强连通图的极大强连通子图称为强连通分量。 ;n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。 ;7.2 图的存储结构及实现;7.2 图的存储结构及实现;7.2 图的存储结构及实现;7.2 图的存储结构及实现;度：行之和或列之和;出度：行之和。入度：列之和;7.2 图的存储结构及实现;7.2 图的存储结构及实现;7.2 图的存储结构及实现;7.2 图的存储结构及实现;邻接矩阵中图的基本操作——顶点的增删 ;V2;V2;图的邻接矩阵存储结构;void CreateMGraph(MGraph *G ) { int i,j,k,w; printf(请输入顶点数和边数(输入格式为:顶点数,边数):\n); scanf(%d,%d,(G-n),(G-e)); printf(“请输入顶点信息(顶点号空格:\n); for(i=0;iG-n;i++) { getchar();scanf(%c,(G-vexs[i]));} for(i=0;iG-n;i++) for(j=0;jG-n;j++) G-edges[i][j]=0; printf(请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n); for(k=0;kG-e;k++) { scanf(%d%d,i,j); G-edges[i][j]=1; G-edges[j][i]=1; } };7.2.2 邻接表;1;邻接表有两种结点结构，顶点表结点和边表结点 :;7.2 图的存储结构及实现;7.2 图的存储结构及实现;在图的邻接表存储中容易解决哪些问题?;邻接表中图的基本操作——顶点的增删 ;V3;邻接表中图的基本操作——边的增删 ;V3;V3;#define MaxVertexNum 100 typedef struct node{ //边表结点 int adjvex; struct node *next; }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex; EdgeNode *firstedge; }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; typedef struct { AdjList adjlist; int n,e; }ALGraph;;void CreateGraphAL(ALGraph *G) { int i,j,k; EdgeNode *s; printf(请输入顶点数和边数(输入格式为:顶点数,边数):\n); scanf(%d,%d,(G-n),(G-e)); printf(请输入顶点信息(顶点号回车:\n); for(i=0;iG-n;i+