现在的位置: 首页 > 综合 > 正文

图::最大流量

2013年09月07日 ⁄ 综合 ⁄ 共 4020字 ⁄ 字号 评论关闭
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
    
<head>
        
<meta http-equiv="Content-Type" content="text/html; charset=gbk"/>
        
<title>Untitled Document</title>
    
</head>
    
<body>
        
<p>
            假设有六个点,各点之间的最大流量如下面的矩阵,求从第零点到第五点的最大流量。
        
</p>
        
<p>
            算法:先找到从第零点到第五点的所有路径(生成树),然后再依次找出每条路径的最大流量
            并同时修改矩阵的流量减该路径的最大流量,最后相加每条路径的流量得到总的最大流量。
        
</p>
        var data=[
        [0,15,0,4,0,0],
        [0,0,12,0,0,0],
        [0,0,0,3,0,7],
        [0,0,0,0,10,0],
        [0,5,0,0,0,10],
        [0,0,0,0,0,0]
        ];
        
<script type="text/javascript">
             
var Max = 6//表明有六个点
            /**
             * 对任何一个点需要继续向下走的情况(类似于迷宫)。深度遍历图形结构,0表示开始的点,Max-1表示结尾的点
             * @param {Object} mazing  图的矩阵数据
             * @param {Object} posotion      对第posotion个点
             * @param {Object} route    还回的路径数据的字符串形式,如1234
             
*/
           
            
function findPath(mazing, position, route){
                
/**
                 * 对任何一个点,要遍历该点的任何一下其它的顶点,如果有值;如果为最后一个
                 * 则成功生成一条路径,否则回退
                 
*/

                
for (var next = 0; next < Max && position<Max; next++
                    
var strRoute=route[route.length-1].join(""); //检测是否已经走过该结点next
                    if ( mazing[position][next] > 0 && strRoute.indexOf(next) < 0
                       route[route.length
-1].push(next);   //有路,就要走
                        /**如果走到未尾的点啦,表明找到一条路径并保存到(length-1),
                         * 同时新增另一条路径(length)。复制现在有记录
                         
*/

                        
if (next == Max - 1
                            route[route.length]
=[];//开始复制记录,保留现场,同时也会得到一条成功的路径
                            for(var index=0;index<route[route.length-2].length;index++){
                                route[route.length
-1][index]=route[route.length-2][index];
                            }

                           
                        }

                        
else {  //
                            findPath(mazing, next, route)
                        }

                        route[route.length
-1].length=route[route.length-1].length-1;  //走完啦,则表明失败,删除最后一个节点。
                    }

                    
                }

            }

            
/**
             * 根据路径找出各路径的最大流量
             * @param {Object} data 图结构
             * @param {Object} route 路径
             * @param {Object} max 各条路径的最大流量
             
*/

            
function findMaxValue(data,route,max){
                
for(var i=0;i<route.length;i++){
                    max[i]
=Math.max;    //默认可以流通最大流量
                    var rows=route[i];
                    
for(var j=0;j<rows.length-1;j++){
                        
//如果当前的值小于最大流量,则赋值给最大流量
                        max[i]=max[i]<data[rows[j]][rows[j+1]]?max[i]:data[rows[j]][rows[j+1]];
                    }

                    
for(var j=0;j<rows.length-1;j++){
                        
//根据图结构数据,已经有流量啦。
                        data[rows[j]][rows[j+1]]=data[rows[j]][rows[j+1]]-max[i];
                    }

                }

            }

            
var data = [[0150400], [0012000], [000307], [0000100], [0500010], [000000]];
            
var route=[];
            route[
0]=[0];
            
var max=[];//各条路径的最大流量
            var MaxValue=0//最终所有路径最大流量的总和
            var position=0;
            findPath(data,position,route);
            
//debugger();
            var lastRow=route[route.length-1];
            
if (lastRow[lastRow.length - 1!= 5{
                route.length 
= route.length - 1;//删除最后一个不成功的
            }

            
/**
            for(var j=0;j<route.length;j++){
                alert(route[j].valueOf());
            }
*/

            findMaxValue(data,route,max);
            
//alert(max.valueOf())
            for(var i=0;i<max.length;i++){
                MaxValue
=MaxValue+max[i];
            }

            alert(
"最大流量为:"+MaxValue);
        
</script>
    
</body>
</html>

 

抱歉!评论已关闭.