请教一个图论算法

wangyanping

我刚看了些网络流方面的问题，主要针对的是边上的容量，而这个问题可以看成节点的容量。

或者网络流中的还有什么方法来解决这个问题？请赐教

dommionr

To wangyanping ( ) :
当K变得很大时，不现实，最好的探测方式应该是求简单路径数，只要有一条恰好=K-2*n（n〉=0）

zhangjk

如果是

      ５－－－－６
　　／　　　　／｜
　／　　　　／　｜
１－－－－２　　｜
｜　　  　｜　　８
｜　　　　｜　／
｜　　　　｜／
３－－－－４　

在3-6之间有几个不相交的简单路径数?

不一般的魔

如图:
    4----------5
   /|         /|
  / |        / |
0--|-------1  |
|  |       |  |
|  6-------|--7
| /        | /
|/         |/
2----------3

求：0 到 1 的路径

#include <iostream.h>

const int MAX = 8;

//建立与图对应的距阵
int num[MAX][MAX]={{1,1,1,0,1,0,0,0}, {1,1,0,1,0,1,0,0},{1,0,1,1,0,0,1,0},
{0,1,1,1,0,0,0,1},{1,0,0,0,1,1,1,0},{0,1,0,0,1,1,0,1},{0,0,1,0,1,0,1,1},
{0,0,0,1,0,1,1,1}};

/**
   检测重复循环的可能
   */
bool test(int s[], int length, int key)
{
        for(int i=0; i<length; i++)
        {
                if(s[i] == key)
                        return false;
        }
        return true;
}

/**
   start:起始点
   end:终点
   */
void Search(int start, int end)
{
        int top = 0;
        int d[MAX]={0};
        int s[MAX] = {0};
        bool is = true;
        d[top] = start;

        while(top > -1)
        {
                is = true;
                while(s[d[top]]++ < MAX)
                {
                        if(d[top] != s[d[top]]-1 && num[d[top]][s[d[top]]-1] == 1)
                        {
                                if(s[d[top]]-1 == end)   //找到输出路径
                                {
                                        for(int i=0; i<=top; i++)
                                        {
                                                cout<<d[i]<<' ';
                                        }
                                        cout<<end<<endl;
                                }
                                else
                                {
                                        if(test(d, top, s[d[top]]-1))
                                        {
                                                top++;
                                                d[top] = s[d[top-1]]-1;
                                                s[d[top]] = 0;
                                                is = false;
                                                break;
                                        }
                                }
                        }
                }
                if(is == true)
                {
                        top--; //回朔
                }
        }
}

void main()
{
        Search(0,1);  //求 0 到 1 的路径
}

输出结果:
0 1
0 2 3 1
0 2 3 7 5 1
0 2 3 7 6 4 5 1
0 2 6 4 5 1
0 2 6 4 5 7 3 1
0 2 6 7 3 1
0 2 6 7 5 1
0 4 5 1
0 4 5 7 3 1
0 4 5 7 6 2 3 1
0 4 6 2 3 1
0 4 6 2 3 7 5 1
0 4 6 7 3 1
0 4 6 7 5 1
Press any key to continue

wangyanping

zhangjk: 3-6间是两条路径

wangyanping

bigc: 对Google那题我没意识到K可能取很大的情况。但是你的算法在下面的图中可能有问题：

1－－－－2－－－－3－－－－4
        / \       |\
       5---6      7--

37为一个长为2的回路，256为一个长为3的回路，那么取k＝22时的求解

wangyanping

bigc：求1－4间长为22时路径

zhangjk

分2步来求出两点间最多的不相交的简单路径数目:
1.求出两点间所有(不考虑相交不相交)的简单路径;
2.从所有简单路径中,再寻找最大不相交路径子集.

wangyanping

这个可以用网络流的方法来做。

将这个图中除uv外的节点都分解T成两个节点T1和T2，而T1只继承那些终点为T的边，T2只继承起点为T的边，并且T1和T2间有一条边。这样就会产生一个新的图，并设置每条边的容量为1，这样就可以求出来了

520520520

一个相似的问题：
给出一组顶点对(ui,vi)，如何尽量的把它们连接起来（ui连接vi），并且通路不相交

更实际的问题：
ui,vi是平面上的点，如何用直线段把它们在这个平面上连接起来，通路不相交，并且线段具有宽度