图和应用.ppt

邻接矩阵：代码书写简单，找邻接点慢 邻接表：代码书写较复杂，找邻接点快 使用条件： Floyed: 可以有负权，无负权回路。O(n^3) Dijkstra: 不能有负权。O(n^2) 分析： 求出任意两点间的最短距离。 枚举每一个顶点到其他n-1个点的最短距离和。 最小者即所求目标。 1、主席的居住城市 distp.pas/dist.in/dist.out 【问题描述】 OI国共有n个城市，任意两个城市都直接或间接连通，每两个直接相连的城市之间都有一双向公路。OI 国的CHEN主席要选择其中一个城市居住，由于他到每个城市考察的概率是相等的，所以他选择的城市到 其它所有城市的的最短距离 的和应该最小。现在，给出城市间的道路，请帮助CHEN主席确定居住的城市。 【输入】 n n*n的矩阵， ( i , j ) 表示 i到j之间的距离 ( i , j ) = ( j , i ) ( i , j ) = -1 表示 ?i , j 之间没有直接道路。 【输出】 城市编号 （如果有多个城市同时最小，输出编号最小的城市） 最小距离和 【输入样例】 5 -1 31 -1 72 -1 31 -1 30 -1 70 -1 30 -1 76 -1 72 -1 76 -1 40 -1 70 -1 40 -1 【输出样例】 2 234 说明：数据规模： n=100 ( i , j) =100 procedure bfs(i:integer); var j,k:integer; begin fillchar(q,sizeof(q),0); open:=0; closed:=1; q[1]:=i; write(i, ); f[i]:=true; while openclosed do begin inc(open); k:=q[open]; for j:=1 to n do if (a[k][j]=1)and(f[j]=false) then begin write(j, ); f[j]:=true; inc(closed); q[closed]:=j; end; end; end; 3、图的遍历的简单应用 犯罪团伙 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。 输入： 第一行：n（=1000,罪犯数量）； 第二行：m（5000，关系数量）； 以下若干行：每行两个数：i和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。 输出：一个整数，犯罪团伙的数量。 样例输入： 11 8 1 2 4 3 5 4 1 3 5 6 7 10 5 10 8 9 样例输出： 3 说明：共三个犯罪团伙。 把n个人看成图的n个顶点；相互认识的连一条边。相互认识的所有人构成一个极大连通子图。 问题转化为：求无向图的连通分量 （有多少个极大连通子图） procedure main; var i:integer; begin sum:=0; fillchar(f,sizeof(f),false); for i:=1 to n do if not f[i] then begin inc(sum); dfs(i); end; writeln(sum); end; 四、无向图的传递闭包 判断无向图的连通性 1 2 3 4 6 5 7 输入图的边的信息， 输出各点的连通性。 样例输入： 7 1 2 2 3 1 3 3 4 5 6 6 7 样例输出： 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 邻接矩阵 判断结点 i 和 j的连通性： i j k 1、结点i和j之间有边则连通。 2、结点i和j之间没有边： 如果存在另外的一个结点k，满足：i与k连通，k与j连通，则i与j连通； 否则i和j不连通。 Can[i][j]: true ：i与j之间有边；false：无边。 则：C