扩大路径法与极大路径

路径法与极大路径"/>

扩大路径法与极大路径

极大路径定义

设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, 再使用极大路径的性质证明图论中的一些定理。