0

我正在尝试在给定某些图形边缘(可以被视为网络)的情况下生成有效的树。以下是从文件中读取图形边的代码;

    FILE *fin = fopen("somefile.txt", "r");

    for (int i = 0; i <=edges; i++) {
    fscanf(fin, "%d%d%d", &u, &v, &w);
            graph[u][v]=w;
    }
    fclose(fin);

现在我想为给定的根u和给定的大小生成最大数量的可能树(或拓扑)给N定这些边。

例如,如果有边;1--->2 ;1--->3; 3--->4。现在如果 N 为 1;u=1 的可能树是 1---->2 和 1--->3。如果 N 为 2,那么可能的树是 1--->2 & 3 或 1--->3---->4 实现这一目标的最佳方法是什么?我不关心复杂性问题。我会很感激帮助!

4

1 回答 1

0

它可能不是最好的实现,但这样的东西应该可以

map<vertex,list<edge>> vertexToedgeThatIncludeIt
void Coloredge(edgeList)
{
  for each edge in list:
     edge.color=True
}


void init()
{
   for each edge:
   {
    vertexToedgeThatIncludeIt[edge.vertex1].append(edge)
    vertexToedgeThatIncludeIt[edge.vertex2].append(edge)
   }
}

edge* findUnColoredvertex(edgeList,startPoistion,founfAt)
{
    skip to startPoistion
    for each edge In edgeList:
          if edge not colored return edge 
    update founfAt
    return NULL
}

void spanTree(vertexToedgeThatIncludeIt,spanTreeList,lastvertex)
{
   if(spanTreeList.size==NumberOfTotalvertex)
   {
        print spanningTree
        return 
   }
   nextedge=findUnColoredvertex(vertexToedgeThatIncludeIt[lastvertex],0,founfAt)
   while(nextedge!=NULL)
   {           
       spanTreeList.append(nextedge);
       Coloredge(vertexToedgeThatIncludeIt[lastvertex]);
       spanTree(vertexToedgeThatIncludeIt,spanTreeList,nextedge.othervertex)
       spanTreeList.pop();
       UnColoredge(vertexToedgeThatIncludeIt[lastvertex])
       nextedge=findUnColoredvertex(vertexToedgeThatIncludeIt[lastvertex],founfAt,founfAt)
   }

 }
于 2012-06-26T10:41:44.400 回答