路径法与极大路径"/>
扩大路径法与极大路径
极大路径定义
设P = v0v1…vk
无向图极大路径性质:
(1) P的顶点和边都不重复
(2) 起点v0和终点vk所有关联边的端点都在路径P上
有向图极大路径性质
(1) P的顶点和边都不重复的路径
(2) 起点v0的前驱顶点和终点vk的后继顶点都在路径P上
北大离散数学教材p121页对于极大路径的定义
扩大路径法
无向图的极大路径
FIND-MAXIMUM-PATH(G) //求无向图G的极大路径P = v0e1v1 //初始化u = v0;v = v1;visited[u] = true;visited[v] = true;//对路径起点u扩展while(itr[u].hasNext()) {//对路径起点u扩展e = itr[u].next();//获取顶点u的下一条关联边w = e.v;//(w, u) = (u, w)if(!visited[w]) {visited[w] = ture;P = wePu = w;//记录路径P的起点,继续下一次迭代}} //对路径终点v扩展while(itr[v].hasNext()) {//对路径起点v扩展e = itr[v].next();//获取顶点v的下一条关联边w = e.v;//(v, w)if(!visited[w]) {visited[w] = ture;P = Pewv = w;//更新路径P的起点,继续下一次迭代}} return P //P是无向图G的一条极大路径
有向图的极大路径
FIND-MAXIMUM-PATH(G) //求有向图G的极大路径P = v0e1v1 //初始化u = v0;v = v1;visited[u] = true;visited[v] = true;//对路径终点v扩展while(itr[v].hasNext()) {//对路径起点v扩展e = itr[v].next();//获取顶点v的下一条出边w = e.v;//有向边<v, w>if(!visited[w]) {visited[w] = ture;P = Pewv = w;//更新路径P的起点,继续下一次迭代}}//对路径起点u扩展//计算有向图G的逆邻接表reverseAdjList[G]//终点u的入边迭代器revItr[u]while(revItr[u].hasNext()) {//对路径起点u扩展e = itr[u].next();//获取顶点u的下一条入边w = e.v;//有向边<w, u>if(!visited[w]) {visited[w] = ture;P = wePu = w;//记录路径P的起点,继续下一次迭代}} return P //P是无向图G的一条极大路径
总结
使用扩大路径法可以在线性时间O(V + E)找出一条极大路径P,设 P = v0v1v2…vk, 再使用极大路径的性质证明图论中的一些定理。
更多推荐
扩大路径法与极大路径
发布评论