第4章 第1-2节 图论算法(C++版).ppt

《第4章 第1-2节 图论算法(C++版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章图论算法第一节基本概念一、什么是图？很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合。二、图的一些定义和概念(a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。(b)无向图：图的边没有方向，可以双向。(b)就是一个无向图。结点的度：无向图中与结点相连的边的数目，称为结点的度。结点的入度：在有向图中，以这个结点为终点的有向边的数目。结点的出度：在有向图中，以这个结点为起点的有向边的数目。权值：边的“费用”，可以形象地

2、理解为边的长度。连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V是连通的。回路：起点和终点相同的路径，称为回路，或“环”。完全图：一个n阶的完全无向图含有n*(n-1)/2条边；一个n阶的完全有向图含有n*(n-1)条边；稠密图：一个边数接近完全图的图。稀疏图：一个边数远远少于完全图的图。强连通分量：有向图中任意两点都连通的最大子图。右图中，1-2-5构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量：1-2-5，4，3。12345(a)12345(b)12345三、图的存储结构1.二维

3、数组邻接矩阵存储定义intG[101][101];G[i][j]的值，表示从点i到点j的边的权值，定义如下：上图中的3个图对应的邻接矩阵分别如下：0111011∞58∞3G（A）=1011G（B）=0015∞2∞61100010G（C）=82∞1041100∞∞10∞1136411∞下面是建立图的邻接矩阵的参考程序段：#includeusingnamespacestd;inti,j,k,e,n;doubleg[101][101];doublew;intmain(){inti,j;for(i=1;i<=n;i++)for(j=1

4、;j<=n;j++)g[i][j]=0x7fffffff（赋一个超大值）;//初始化，对于不带权的图g[i][j]=0，表示没有边连通。这里用0x7fffffff代替无穷大。cin>>e;for(k=1;k<=e;k++){cin>>i>>j>>w;//读入两个顶点序号及权值g[i][j]=w;//对于不带权的图g[i][j]=1g[j][i]=w;//无向图的对称性,如果是有向图则不要有这句！}…………return0;}建立邻接矩阵时，有两个小技巧:初始化数组大可不必使用两重for循环。1)　　如果是int数组，采用memset(g,0x7f,

5、sizeof(g))可全部初始化为一个很大的数(略小于0x7fffffff)，使用memset(g,0,sizeof(g))，全部清为0，使用memset(g,0xaf,sizeof(g))，全部初始化为一个很小的数。2)如果是double数组，采用memset(g,127,sizeof(g));可全部初始化为一个很大的数1.38*10306，使用memset(g,0,sizeof(g))全部清为0.2.数组模拟邻接表存储图的邻接表存储法，又叫链式存储法。本来是要采用链表实现的，但大多数情况下只要用数组模拟即可。定义两个数组，例如：intg[10

6、1][101];用来存储这个图。再定义一个一维数组：intnum[101];用来记录与每个点相连的点的数目。如果边有权值，还要定义一个数组intval[101][101]存储边权。以下是用数组模拟邻接表存储的参考程序段：#includeusingnamespacestd;intn,m,i,j,c;intg[101][101];intnum[101];intmain(){memset(g,0x7f,sizeof(g));memset(num,0,sizeof(num));cin>>n;for(i=1;i<=n;i++){cin>

7、>num[i];//第i行说明点i的连接情况，每行的开头读入与之相连的点的数目for(j=1;j<=num[i];j++){cin>>g[i][j];//第j个与i相连的点是g[i][j]val[i][g[i][j]]=v;//有权图还要存下权值}}…………return0;}两种方法各有用武之地，需按具体情况，具体选用。第二节图的遍历一、深度优先与广度优先遍历从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问

8、一次后就改为true。图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。1.深度优先遍历深度优先遍历与深搜