图论的常用算法及应用

图论的常用算法及应用基本概念和性质1顶点集边集邻接与非邻接点的度数完全图与补图同构基本概念和性质2路径v1,v2,…,vn开路回路真路环连接连通与非连通基本概念和性质3割点割边割边连接的两点是割点两个割点之间的边是割边一个反例最短路径路径v1,v2,…,vn任意两点的最短路径长度小于n vi1,vi2,vi3,…,vimm>n任一环的长度不大于n其他一些图多重图伪图有向图带权图欧拉图哈密顿图平面图图的矩阵表示1图的邻接矩阵图的矩阵表示2图的邻接向量矩阵图的矩阵表示3图的关联矩阵例题1给出一张无向简单图的邻接矩阵A以及正整数k，求任意两点之间长度为k的路径个数。例题1样例K=5求从v1到v3长度为5的路径个数例题1求解1利用图的邻接矩阵Ak(i,j)表示从i到j，长度为k的路径个数例题1求解2递推公式：例题1程序fork:=2to5dofori:=1tondoforj:=1tondoforl:=1tondoA[k,i,j]:=A[k,i,j]+A[k-1,i,l]*A[1,l,j];例题2判定图的同构给出两张图的邻接矩阵，判断他们是否同构例题2样例例题2解法1建立一一映射将图1的顶点与图2的顶点进行映射一个一维数组mm[i]表示图1中的顶点i映射到图2中的顶点m[i]例题2程序1varA,B:array[1..10,1..10]ofinteger;m:array[1..10]ofinteger;n:integer;例题2程序2functionjudge:boolean;vari,j:integer;beginjudge:=false;fori:=1tondoforj:=1tondoifA[i,j]<>B[m[i],m[j]]thenexit;judge:=true;end;例题2解法2如何产生这样的一一映射呢？如何产生排列？例题2循环法form[1]:=1to4doform[2]:=1to4doifm[1]<>m[2]thenform[3]:=1to4doif(m[3]<>m[2])and(m[3]<>m[1])thenform[4]:=1to4doif(m[4]<>m[3])and(m[4]<>m[2])and(m[4]<>m[1])then调用judge且判断;例题2用递归法模拟循环变量定义：var

m:array[1..10]ofinteger;used:array[1..10]ofinteger;n:integer;例题2递归子程序procedurework(d:integer);vari:integer;beginfori:=1tondoifused[i]=0thenbeginused[i]:=1;m[d]:=i;work(d+1);used[i]:=0;end;end;例题2递归终止条件ifd=n+1thenbegin

调用judge判断;

exit;end;例题3最短路径给出一张有向带权图以及两个顶点a,b求从a到b的最短路径长度数据规模：1000个顶点给出2000条边的三元组形式例题3最短路径算法迪卡斯特拉算法（标号法）适用范围，算法复杂度Floyd–Warshall算法适用范围，算法复杂度Bellman–Ford算法适用范围，算法复杂度Bellman–Ford程序解答1变量定义constoo=15000;vars,e,l:array[1..2000]ofinteger;dist:array[1..1000]ofinteger;a,b,i,j,k,n,m:integer;Bellman–Ford程序解答2

fori:=1tondodist[i]:=oo;dist[a]:=0;fori:=1ton-1doforj:=1tomdoifdist[s[j]]+l[j]<dist[e[j]]thendist[e[j]]:=dist[s[j]]+l[j];Bellman–Ford思考题如何进一步提高算法的效率如何判断一个图存在负圈应用举例两个基本算法深度优先搜索（DepthFirstSearch）广度优先搜索（BreadthFirstSearch）深度优先搜索特点复杂度算法和数据结构的实现应用深度优先搜索的搜索顺序深度优先搜索算法程序varn:integer;visited:array[1..100]ofinteger;data:array[1..100,1..100]ofinteger;深度优先搜索算法程序proceduredfs(which:integer);vari:integer;beginvisited[which]:=1;fori:=1tondoif(visited[i]=0)and(data[which][i])thendfs(i);end;广度优先搜索特点复杂度算法和数据结构的实现应用广度优先搜索的搜索顺序广度优先搜索算法程序varn:integer;visited:array[1..100]ofinteger;data:array[1..100,1..100]ofinteger;queue:array[1..100]ofinteger;qh,ql:integer;广度优先搜索算法程序1procedurebfs(which:integer);vari:integer;beginqueue[1]:=which;ql:=1;qh:=1;visited[which]:=1;

广度优先搜索算法程序2whileqh<=qldobeginfori:=1tondoif(visited[i]=0)and(data[queue[qh]][i])thenbegininc(ql);queue[ql]:=i;visited[i]:=1;end;inc(qh);end;end;例题4给出一张无向简单图，求此图的割点经典做法简单做法例题4经典做法使用深度优先搜索在搜索过程中计算每个顶点的两个值dfn

和low如何计算例题4简单做法1删除某个节点判断是否仍然连通例题4简单做法2问题的转换1.是否真的需要删除节点？2.是否真的需要求出所有连通分量？例题4简单做法3问题的答案1.否，只要将visited数组初始赋12.否，只要dfs一个分量例题4解答程序functionjudge(which:integer):booleanvari:integer;beginfori:=1tondovisited[i]:=0;vi