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 に答える