생성 나무

Question

나는 (네트워크로 간주 될 수 있습니다) 특정 그래프 가장자리 주어진 유효한 나무를 생성하기 위해 노력하고있어. 다음은 파일에서 그래프 가장자리를 읽는 코드입니다.

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 이것을 달성하는 가장 좋은 방법은 무엇입니까? 나는 복잡한 문제에 관심이 없다. 도와 주셔서 감사합니다!

Answer 1

는 최고의 구현하지만이 같은 뭔가

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) 
    } 

}