1

我想构建一个无向二分图，其中一条边将用户与其兴趣联系起来。该图看起来像这个模型，其中用户由绿色圆圈表示，兴趣由红色圆圈表示。

兴趣图

为了找到两个用户之间的相似性，我尝试找到第一个用户和第二个用户之间的所有可能路径。例如，用户 0 和用户 4 之间有两种可能的路径（0 --> 6 --> 2 --> 8 --> 4 和 0 --> 5 --> 1 --> 7 --> 3 --> 8 --> 4)。这是我到目前为止所尝试的：

private int v = 4;
public static void Main()
{
    var graph = new UndirectedGraph<int, SEdge<int>>();
    List<int> vertices = new List<int>();
    for (int i = 0; i < 11; i++)
    {
        vertices.Add(i);
    }

    graph.AddVertexRange(vertices);
    //Edges incident to 0
    graph.AddEdge(new SEdge<int>(vertices[0], vertices[5]));
    graph.AddEdge(new SEdge<int>(vertices[0], vertices[6]));  
    //Edges incident to 1
    graph.AddEdge(new SEdge<int>(vertices[1], vertices[5]));
    graph.AddEdge(new SEdge<int>(vertices[1], vertices[6]));
    //Edges incident to 2
    graph.AddEdge(new SEdge<int>(vertices[2], vertices[6]));
    graph.AddEdge(new SEdge<int>(vertices[2], vertices[8]));
    //Edges incident to 3
    graph.AddEdge(new SEdge<int>(vertices[3], vertices[7]));
    graph.AddEdge(new SEdge<int>(vertices[3], vertices[8]));
    //Edges incident to 4
    graph.AddEdge(new SEdge<int>(vertices[4], vertices[8]));

    Func<SEdge<int>, double> edgeWeights = se => 1.0;
    //Vertex distance observer
    var observer = new UndirectedVertexPredecessorRecorderObserver<int, SEdge<int>>();

    //DFS Algortihm
    var dfs = new UndirectedDepthFirstSearchAlgorithm<int, SEdge<int>>(graph);
//    dfs.FinishVertex += VertexFinished;
//    dfs.ForwardOrCrossEdge += TransverseEdge;
    dfs.TreeEdge += TransverseEdge;
    dfs.Compute(0);        
}

public void TransverseEdge(object sender, EdgeEventArgs<int, SEdge<int>> ed){
    if(ed.Edge.Source == v){
        Console.WriteLine("Visited {0}", ed.Edge.Source);
    }
}

上面的代码只打印一次，但应该打印两次，因为有两条路径。

我还尝试实施此答案中给出的解决方案。但是，这会打印出一种可能的路径。那么，如何使用QuickGraph打印两个顶点之间的所有可能路径？

4

1 回答 1

1

实际上，当用户数量和选择增加时，路径的数量可能会呈指数增长。对于 100 个用户和项目，如果所有用户都喜欢大多数项目，则可能路径的数量可能会超过 int64 的最大值。

于 2016-05-17T11:27:17.483 回答