阅微客栈 » 头脑风暴

微软面试题 - 找路径条数

(4 posts)
  • 发起于 1 年 之前，作者 zhang
  • 最新回复 来自于 Yuanyuan

  1. zhang
    神

    在一个由向无圈图中，查找给定的两节点之间的有向路径的条数。

    发布于 1 年 之前 #

  2. lemonutzf
    Member

    反向迭代，有点类似与dijkstra求最短路径

    发布于 7 月 之前 #

  3. apunix
    Member

    void FindPath(Graph& G, int v, int vj, Edge* &path, int l) //G是图，v是当前结点，vj是目标结点，path保存当前路径的数组，l是当前路径的长度
    {
    if(v == vj)
    {
    printPath(path, l);
    return;
    }
    for(Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e))
    {
    if(!InPath(G.ToVetex(e))) { //Inpath判断下一搜索结点是否已经在路径中出现过
    l++;
    path[l] = G.ToVetex(e);
    FindPath(G, G.ToVetex(e), vj, path, l);
    l--; //恢复路径
    }
    }
    就是一个回溯法搜索的过程

    发布于 6 月 之前 #

  4. Yuanyuan
    Member

    呵呵呵呵····还是不会····

    发布于 5 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。