题目：

给定一个包含N个节点的连通图，节点编号1到n。共有n-1条边。从1号节点出发，问遍历所有节点最短路程多少？

数据输入方式：共n行，第一行是节点个数。下面的n-1行每一行为两个正整数，代表互相连通的两个节点。

！@#￥%：

题目没有明确1号节点是否在图的边缘，也没有提到图的复杂度如何。

网上看了几个别人的程序，但有的程序太过简单，稍微复杂一点的图结果就不对了。下来在VS里编了下，没有调用别的复杂的库，只是用了 vector 。

我这个程序虽然能应对复杂一点的图，但还不是可以应对所有情况，限制条件为：

1）1号节点必须在图的边缘；

2）分支深度不能大于1。如下图，左面的分支为 6-7、6-8，深度均为1；右图分支为 6-7、6-8-9，深度为1和2。

程序（C++）：

头文件 map_gao.h

#pragma once

#include<vector>

#include<iostream>

using namespace std;

namespace gao{

class node {

public:

node() :used(false), num(0) {}

bool used; //是否已被cull

int num; //连接的节点数

vector<int> neigh; //邻居节点序号

vector<int> getchild_id() { return neigh; }

//void add(int a,int b);

};

class Map {

public:

vector<node> nodes;

int distance;

bool checkNode(int id) {

if (nodes[id].num) return true; //非空

else return false;

}

void cull(int id); //裁剪指定节点边

int computeTree(int rootId); //裁剪整个树

void computeDistance(); //计算总路程

void print(); //打印节点和路程信息

};//end class Map

void Map::cull(int id) {

nodes[id].used = true;

vector<int> child_id;

child_id = nodes[id].getchild_id();

int idNum = child_id.size();

for (int i = 0; i < idNum; i++) {

vector<int> *childs;

childs = &nodes[child_id[i]].neigh;

for (vector<int>::iterator it = childs->begin(); it != childs->end();)

if (nodes[*it].used) {

it = childs->erase(it);

nodes[child_id[i]].num--;

}

else it++;

}

}

int Map::computeTree(int rootId) {

if (!checkNode(rootId)) return 0;

else {

cull(rootId);

node childs;

vector<int> child_id;

child_id = nodes[rootId].getchild_id();

int idNum = child_id.size();

for (int i = 0; i < idNum; i++)

computeTree(child_id[i]);

}

}

void Map::computeDistance() {

distance = 0;

for (int i = 1; i < nodes.size(); i++)

if (nodes[i].num) distance += nodes[i].num * 2 - 1;

}

void Map::print() {

cout << "总路程为: " << distance << endl;

//for (int i = 1; i < nodes.size(); i++) {

// cout << "nodes[" << i << "].num: " << nodes[i].num << endl;

//}

}

}//end namespace gao

 

源文件 遍历树.cpp

#include"map_gao.h"

using namespace std;

using namespace gao;

void main() {

int N;

cin >> N;

vector<node> nodes;

nodes.resize(N+1);

int a, b;

for (int i = 0; i < N - 1; i++) {

cin >> a >> b;

nodes[a].neigh.push_back(b);

nodes[a].num++;

nodes[b].neigh.push_back(a);

nodes[b].num++;

}

Map map;

map.nodes = nodes;

int distance = 0;

int startId;

startId = 1; //从哪个节点开始出发

map.computeTree(startId);

map.computeDistance();

distance += map.distance;

map.print();

getchar(); getchar();

}

 

结果：

4个节点（试题样例），路径为 1-2-1-3-4：

8个节点，路径为1-2-3-2-4-5-6-5-7-5-8：

10个节点（对应上面那个10个点的图），路径为1-2-3-4-5-6-7-6-8-6-9-10：