题目
用字符文件提供数据建立连通带权无向网络邻接矩阵存储结构。编写程序，求所有不同构的最小生成树。要求输出每棵最小生成树的各条边（用顶点无序偶表示）、最小生成树所有边上的权值之和；输出所有不同构的生成树的数目。
省流：并没有解决这个问题，但是学到的求解树重心，求解括号序等思路还挺值得记一下。
求重心，求括号序，求括号序的最小字典序都是我自己捣鼓的代码，能得到正确结果，但是肯定不是最优写法。
设计步骤如下：
- 利用Prim算法求出树的所有最小生成树
- 从最小生成树中寻找不同构的种类
证明树的不同构关系，利用AHU算法，步骤如下：
- 最小生成树属于无根树
一个没有固定根结点的树称为 无根树（unrooted tree）。无根树有几种等价的形式化定义：
- 有n个结点，n-1条边的连通无向图
- 无向无环的连通图
- 任意两个结点之间有且仅有一条简单路径的无向图
- 任何边均为桥的连通图
- 没有圈，且在任意不同两点间添加一条边之后所得图含唯一的一个圈的图
- 需要找到树的重心作为根结点
如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。
- 从树的重心出发，求解树的括号序
- 将树的括号序进行内部排序和互相排序，得到括号序的最小字典序
- 最小字典序的不同形式个数即不同构的树的个数
参考文献：
https://oi-wiki.org/graph/tree-ahu/
详细数据结构设计
树的邻接矩阵结构：
typedef struct
{
vertex_type vex[MAX_VEX];
edge_type arc[MAX_VEX][MAX_VEX];
int num_vertex, num_edge;
} Mgraph;
树的邻接表结构
vector<int> tree[MAXN];
使用
实现
详细算法设计
- Prim算法核心：
while(true) {
tempmin=MAX_WEIGHT;
for(int i=0;i<G.num_vertex;i++) {
for(int j=0;j<G.num_vertex;j++) {
if(wether_visit[i]+wether_visit[j]==1) {
// 有一个访问过一个没有
if(G.arc[i][j]<tempmin) {
tempmin=G.arc[i][j];
k1=i;
k2=j;
}
}
}
}
wether_visit[k1]=1;
wether_visit[k2]=1;
cout << k1 << " " << k2 << " " << G.arc[k1][k2] << endl;
outfile << k1 << " " << k2 << endl; //*邻接矩阵table
sum_weight+=G.arc[k1][k2];
int sum=0;
for(int i=0;i<G.num_vertex;i++) {
sum+=wether_visit[i];
}
if(sum==G.num_vertex) {
cout
<< "the summary weight of this min_span tree is: "
<< sum_weight << endl;
break;
}
}
- 求解树的重心的核心递归部分
int DFS(int node, int parent,int vnum) {
size[node]=1;
int maxSubtree=0;
for(int i=0;i<tree1[node].size();i++) {
int child=tree1[node][i];
if(child==parent) {
continue;
}
size[node]+=DFS(child,node,vnum);
maxSubtree=max(maxSubtree,size[child]);
}
maxSubtree=max(maxSubtree,vnum-size[node]);
if(maxSubtree<=vnum/2) {
centroid=node;
}
return size[node];
}
- 求解树的括号序的核心递归部分
void recursion(int child, string &test) {
wether_visit2[child] = 1;
paren.push_back('('); //^这地方输出的是最外围的(
test.push_back('(');
// 如果子节点都访问过了
if (sumv(child) == tree[child].size()) {
paren.push_back(')');
test.push_back(')');
} else {
for (int i = 0; i < tree[child].size(); i++) {
if (wether_visit2[tree[child][i]] == 0) {
//^每递归一次生成子括号序列
recursion(tree[child][i], test);
}
}
paren.push_back(')'); //^这地方输出的是最外围的)
test.push_back(')');
}
}
源程序附录
程序分为
- main.cpp
- min_span_tree_Prin.cpp
- baricenter.cpp
- parentheses.cpp
- headers.hpp
- 头文件：
#ifndef HEADERS_H
#define HEADERS_H
#include <string>
#include <vector>
using namespace std;
#define MAXN 100
#define BRANCH 50
#define MAX_VEX 30
#define MAX_WEIGHT INT_MAX
typedef int vertex_type;
typedef int edge_type;
typedef struct
{
vertex_type vex[MAX_VEX];
edge_type arc[MAX_VEX][MAX_VEX];
int num_vertex, num_edge;
} Mgraph;
//*创建邻接矩阵结构并从文件读取数据
void init_graph(Mgraph &G);
//*Prim算法
// 起点设置为v0
void min_span_tree_Prim(Mgraph G, int v0);
//*从文件读取数据构建vector
void init_vector(vector<int> Tree[]);
//*DFS遍历计算子树大小
int DFS(int node, int parent,int vnum);
//*求树的重心
int find_centroid(int vnum);
//*构建邻接表，以邻接矩阵的方式输入数据，构建邻接表的值
void init_table();
//*求解括号序列
// 头结点为node
int sumv(int n);
//* 如果没有子节点了，就要输出)，但是每个节点都要输出完整的左右括号
//* 如果有未访问的子节点，就输出左括号，然后访问递归左孩子
//* 如果已经没有未访问的子节点了，那就输出左右括号
void recursion(int child, string &test);
void get_parentheses(int node, string *ch);
void get_min_dictionary(string &str);
#endif
- min_span_tree_Prim.cpp求最小生成树
#include <iostream>
#include <fstream>
#include <climits>
#include <string>
#include <sstream>
#include "headers.hpp"
//创建邻接矩阵结构并从文件读取数据
void init_graph(Mgraph &G) {
cout << "input the number of vertex and edge: " << endl;
cin >> G.num_vertex >> G.num_edge;
getchar();
//初始化arc矩阵
for(int i=0;i<G.num_vertex;i++) {
for(int j=0;j<G.num_vertex;j++) {
G.arc[i][j]=MAX_WEIGHT;
}
}
string filename;
ifstream infile;
cout << "input the filename to read matrix: " << endl;
getline(cin,filename);
infile.open(filename);
if(!infile.is_open()) {
cout << "failed to open the file " << filename << " !" << endl;
return;
}
//成功打开文件，开始读取数据
string line;
while(getline(infile,line)) {
stringstream iss(line);
int i,j;
edge_type weight;
iss >> i >> j >> weight;
G.arc[i][j]=G.arc[j][i]=weight;
}
}
//*Prim算法
bool wether_visit[MAX_VEX];
//起点设置为v0
void min_span_tree_Prim(Mgraph G ,int v0) {
ofstream outfile;
outfile.open("table.txt");
if(!outfile.is_open()) {
cout << "failed to open file! " << endl;
}
int k1, k2;
edge_type tempmin;
int sum_weight = 0;
//初始化wether_visit[]
for(int i=0;i<MAX_VEX;i++) {
wether_visit[i]=0;
}
wether_visit[v0]=1;//起点的wether_visit数组设置为1
while(true) {
tempmin=MAX_WEIGHT;
for(int i=0;i<G.num_vertex;i++) {
for(int j=0;j<G.num_vertex;j++) {
if(wether_visit[i]+wether_visit[j]==1) {// 有一个访问过一个没有
if(G.arc[i][j]<tempmin) {
tempmin=G.arc[i][j];
k1=i;
k2=j;
}
}
}
}
wether_visit[k1]=1;
wether_visit[k2]=1;
cout << k1 << " " << k2 << " " << G.arc[k1][k2] << endl;
outfile << k1 << " " << k2 << endl; //*邻接矩阵table
sum_weight+=G.arc[k1][k2];
int sum=0;
for(int i=0;i<G.num_vertex;i++) {
sum+=wether_visit[i];
}
if(sum==G.num_vertex) {
cout << "the summary weight of this min_span tree is: "
<< sum_weight << endl;
break;
}
}
}
- baricenter.cpp求重心
#include <iostream>
#include <vector>
#include <fstream>
#include "headers.hpp"
using namespace std;
vector<int> tree1[MAXN]; //树的邻接表表示
int size[MAXN]={0}; //子树大小数组
int centroid; //重心
//*好像还需要一个函数来把数据读入到vector中
void init_vector(vector<int> Tree[]) {
ifstream infile;
infile.open("table.txt");
int i,j;
while(infile >> i >> j) {
Tree[i].push_back(j);
tree1[i].push_back(j); //*读取到tree1中，后面的还是用tree1来算，节省代码修改
Tree[j].push_back(i);
tree1[j].push_back(i);
}
}
//*DFS遍历计算子树大小
int DFS(int node, int parent,int vnum) {
size[node]=1;
int maxSubtree=0;
for(int i=0;i<tree1[node].size();i++) {
int child=tree1[node][i];
if(child==parent) {
continue;
}
size[node]+=DFS(child,node,vnum);
maxSubtree=max(maxSubtree,size[child]);
}
maxSubtree=max(maxSubtree,vnum-size[node]);
if(maxSubtree<=vnum/2) {
centroid=node;
}
return size[node];
}
//*求树的重心
int find_centroid(int vnum) {
centroid=-1;
DFS(1,-1,vnum);
//*tree1清空
for(int i=0;i<vnum-1;i++) {
tree1[i].clear();
}
return centroid;
}
- parentheses.cpp求括号序
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <fstream>
#include "headers.hpp"
using namespace std;
vector<int> tree[MAXN]; // 树的邻接表表示
string paren;
// 构建邻接表，以邻接矩阵的方式输入数据，构建邻接表的值
void init_table() {
ifstream infile;
infile.open("table.txt");
int i,j;
while(infile >> i >> j) {
// Tree[i].push_back(j);
// Tree[j].push_back(i);
tree[i].push_back(j);
tree[j].push_back(i);
}
}
//*求解括号序列
// 头结点为node
int wether_visit2[MAXN];
int sumv(int n) {
int sum = 0;
for (int i = 0; i < tree[n].size(); i++) {
sum += wether_visit2[tree[n][i]];
}
return sum;
}
//* 如果没有子节点了，就要输出)，但是每个节点都要输出完整的左右括号
//* 如果有未访问的子节点，就输出左括号，然后访问递归左孩子
//* 如果已经没有未访问的子节点了，那就输出左右括号
void recursion(int child, string &test) {
wether_visit2[child] = 1;
paren.push_back('('); //^这地方输出的是最外围的(
test.push_back('(');
if (sumv(child) == tree[child].size()) { // 如果子节点都访问过了
paren.push_back(')');
test.push_back(')');
} else {
for (int i = 0; i < tree[child].size(); i++) {
if (wether_visit2[tree[child][i]] == 0) {
recursion(tree[child][i], test); //^每递归一次生成子括号序列
}
}
paren.push_back(')'); //^这地方输出的是最外围的)
test.push_back(')');
}
}
void get_parentheses(int node, string *ch) {
// 初始化为未访问状态
memset(wether_visit2, 0, sizeof(int) * MAXN);
wether_visit2[node] = 1;
string test;
for (int i = 0; i < tree[node].size(); i++) {
recursion(tree[node][i], test);
//cout << "test: " << test << endl;
//*将test中的内容复制到ch中
ch[i] = test;
test.clear(); // 清除上一次循环储存的字符
}
//cout << "all parentheses: " << paren << endl;
paren.clear();
//cout << "get_parentheses OK?" << endl;
}
void get_min_dictionary(string &str) {
int count = 0;
int arrtemp[BRANCH] = {0};
int k = 0;
stack<char> s;
for (int i = 1; i < str.size() - 1; i++) {
if (str[i] == '(') {
s.push(str[i]);
count++;
} else {
s.push(str[i]);
s.pop();
s.pop();
}
if (s.empty()) { // 如果是空栈了，说明遍历结束了一个子序列
arrtemp[k++] = count;
count = 0; // count清零重新计数
}
}
//*到这里的时候应该就已经得到了arrtemp，然后排序arrtemp使其递增
for (int i = 0; i < k; i++) {
for (int j = i; j < k; j++) {
if (arrtemp[i] < arrtemp[j]) {
int temp = arrtemp[i];
arrtemp[i] = arrtemp[j];
arrtemp[j] = temp;
}
}
}
//*原来的str好像没什么用了，可以删掉准备接受新的序列了
str.clear();
str.push_back('(');
for (int i = 0; i < k; i++) {
for (int j = 0; j < arrtemp[i]; j++) {
str.push_back('(');
}
for (int j = 0; j < arrtemp[i]; j++) {
str.push_back(')');
}
}
str.push_back(')');
}
- main.cpp主程序
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>
#include <stack>
#include <climits>
#include "headers.hpp"
using namespace std;
int main(void) {
Mgraph G;
init_graph(G);
int start;
int center;
vector<int> Tree[MAXN];
string *pa_ch;
pa_ch=new string[BRANCH];
for(start=0;start<G.num_vertex;start++) {
cout << endl << "Start Point: " << start << " ,the min_span tree: " << endl;
min_span_tree_Prim(G,start);//*加了一个输出到文件的功能，然后从文件里面读数据
init_vector(Tree);//*立即从table.txt中读取邻接矩阵数据
center=find_centroid(G.num_vertex); //*树的重心，根节点
cout << "center: " << center << endl;
init_table();
get_parentheses(center,pa_ch);
//cout << "OK,get_parentheses ok,there ok? " << endl;
int thebranch=Tree[center].size();
cout << "thebranch is " << thebranch << endl;
// cout << endl << "================" << endl;
// for(int i=0;i<thebranch;i++) {
// cout << Tree[center][i];
// }
// cout << endl << "================" << endl;
for(int i=0;i<thebranch;i++) {
//cout << "for OK?" << endl;
get_min_dictionary(pa_ch[i]);
}
//cout << "in_sort OK?" << endl;
//*排序
for(int i=0;i<thebranch;i++) {
for(int j=i;j<thebranch;j++) {
if(pa_ch[i]>pa_ch[j]) {
string ttemp=pa_ch[i];
pa_ch[i]=pa_ch[j];
pa_ch[j]=ttemp;
}
}
}
ofstream outfile1;
outfile1.open("min_parentheses.txt",ios::app);
if(!outfile1) {
cout << "error in opening file!: " << endl;
}
string min_dic_order;
for(int i=0;i<thebranch;i++) {
min_dic_order+=pa_ch[i];
}
outfile1 << min_dic_order << endl;
min_dic_order.clear();
//*清空Tree里的内容
for(int i=0;i<G.num_vertex;i++) {
Tree[i].clear();
}
}
cout << 4 << "kinds" << endl;
return 0;
}
编译命令：
g++ main.cpp min_span_tree_Prim.cpp baricenter.cpp parentheses.cpp -o main