离散数学II实验二（Python/C++）

实验二

（一）实验题目

通信网络上的线路设计问题

（二）实验目的

1、 掌握无向连通图生成树的求解方法；

2、 掌握基本回路系统和环路空间的求解方法；

3、 掌握基本割集系统和断集空间的求解方法；

4、 了解生成树、环路空间和断集空间的实际应用。

（三）实验要求

在通信网络中，节点之间有网络线路传输数据包，假设两节点之间最多有一条网络线路，给定该通信网络节点之间的连接关系，求解如下问题：

1、 用图结构描述上述通信网络，如给定相邻矩阵： 。

2、 如何在通信网络中确保消息可以有效地从源节点传播到所有目标节点，以减少了冗余的数据转发？（提示：通过构建一棵生成树，数据可以沿着生成树的拓扑结构进行传输（如给出生成树的关联矩阵）。）

3、 有多少种上述实现方案？（提示：求方阵的行列式和秩见参考代码。）

4、 如何在该通信网络中，解决数据包转发和路由选择的问题？（提示：通过探测和避免环路空间，可以保证数据在网络中的正常传输，并降低数据包丢失和延迟。即输出基本回路系统（输出形式如：{e1e4e3,e2e5e3}）和环路空间（输出形式如：{Φ,e1e4e3,e2e5e3,e1e4e5e2}）。）

5、 在网络安全和隐私保护中，如何识别可能容易遭到攻击或数据泄露的路径或节点？（通过分析断集空间，可以采取相应的保护措施，提高网络安全性和数据隐私性。即输出基本割集系统（输出形式如：{{e1,e4},{e2,e5},{e3,e4,e5}}）和断集空间（输出形式如：{Φ,{e1,e4},{e2,e5},{e3,e4,e5},{e1,e2,e4,e5},{e1,e3,e5},{e2,e3,e4},{e1,e2,e3}}）。）

（四）实验内容和实验步骤

1、需求分析

• （1） 输入的形式和输入值的范围：

  • 输入形式：例如

    

    （可给定任意数量的序列）

  • 输入值的范围：非负整数

• （2） 输出的形式：

  

  • 如图所示，输出时，按照实验要求的顺序依次展开输出

    ──生成树的关联矩阵
    ──方案数
    ──基本回路系统和环路空间
    ──基本割集系统和断集空间

• （3） 程序所能实现的功能：

  • 能通过给定的相邻矩阵输出生成树的关联矩阵，计算生成树的个数，输出基本回路系统和环路空间，输出基本割集系统和断集空间
  • 可循环，反复输入，方便测试多组数据

2、 概要设计

• 我选择的是 Python 进行编程，（后面写的C++同理，就不解析了）

• 下面是各函数的功能分析：

  • 1. 生成树的关联矩阵

       先计算出关联矩阵，然后去除关联矩阵中的任意一行，取出一个结果，其中从m中选出的n-1列就是选出的树枝。采用二进制枚举进行排列组合，判断1~2n+1-1转换成二进制数有多少个1，符合则将它存起来。

    2. 计算生成树的个数，即实现方案数

       设图G的度矩阵为D(G)，邻接矩阵为A(G)。定义拉普拉斯矩阵L(G) = D(G) - A(G)，则L(G)的任意一个余子式的值即为图G的生成树个数。通过分析，我们发现拉普拉斯矩阵的对角线上的元素是相邻矩阵对应行上所有元素的度数之和，而其他元素为相邻矩阵的相反数。得到拉普拉斯矩阵后，我们可以取其第一行第一列的余子式，即去除第一行和第一列的行列式。

       对于求行列式的过程，我们可以采用定义法，按照第一行展开，得到n个代数余子式。这些余子式同样是求行列式，然后按照它们的第一行展开，一直递归到只剩一行时结束，即可计算出整个行列式的值。

    3. 求此生成树对应的基本回路系统

       通过分析生成树的边，我们可以推导出与该生成树相关联的弦。接着，根据每条弦连接的两个顶点，在生成树中找到这两个顶点之间的一条路径。将这条路径与弦一起组合，形成一个回路。这样，我们就能得到基本回路系统。在寻找路径的过程中，采用了广度优先搜索（BFS）算法，以生成树中的某一顶点作为根节点，搜索时记录其子节点。最后，根据保存的子节点信息，为每个子节点找到其对应的父节点。通过以另一个顶点为起点，向上回溯直到根节点，我们就能得到一条完整的回路。

    4. 求此生成树对应的基本割集系统

       对于每一条树枝，可以先将其删除，然后尝试将一条弦加入图中。如果加入弦之后，图仍然是连通的，那么该弦应该属于与这条树枝关联的割集；否则，该弦不属于该割集。连通性的判断可以通过对图的邻接矩阵进行广度优先搜索（BFS）来实现，如果所有节点都被访问过，则图是连通的。

    5. 环路空间和断集空间

       环路空间的计算可以通过选择生成树的基本回路系统中的若干个回路（1~n）进行环合运算来实现。具体过程是先选取第一个回路生成数组A，然后对于后续的每个回路，检查其中的边是否在A中。如果在A中，则将这条边从A中删除，如果不在A中，则将这条边加入A。

       为了实现取若干个回路的操作，可以使用二进制枚举法，从1到2n-1，其中1表示被选中，0表示不被选中。通过这种方式，可以枚举出所有选择的情况。在这里，可以使用 itertools 中的 combination 函数来实现。

       割集空间的计算与环路空间类似，同样可以通过选择生成树的基本回路系统中的若干个割集进行割集合并运算来得到结果。

3、详细设计

• 源代码：（Python和C++）

Python:

import numpy as np
import copy
import itertools


# 关联矩阵
def Incidence_matrix(l: list) -> list:
    ll = copy.deepcopy(l)
    m = []
    for i in range(len(l)):
        for j in range(len(l)):
            if ll[i][j] > 0:
                for k in range(ll[i][j]):
                    t = [0] * len(l)
                    t[i], t[j] = 1, 1
                    m.append(t)
                    ll[i][j] -= 1
                    ll[j][i] -= 1
    return m


# 生成树
def tree(l: list) -> tuple:
    x = list(itertools.combinations(range(len(l)), len(l[0]) - 1))
    side = []
    for each in x:
        matrix = [l[i][1:] for i in each]
        if np.linalg.det(matrix) != 0:
            side = each
            break
    adj_tree = [[0] * len(l[0]) for _ in range(len(l[0]))]
    inc_tree = [l[i] for i in side]
    for i in inc_tree:
        e = [j for j in range(len(i)) if i[j] == 1]
        adj_tree[e[0]][e[1]], adj_tree[e[1]][e[0]] = 1, 1
    return adj_tree, inc_tree, side


# 计算生成树的个数
def tree_number(l: list) -> int:
    m = []
    for i in range(1, len(l)):
        t = []
        for j in range(1, len(l)):
            if i == j:
                t.append(sum(l[i]))
            else:
                t.append(-l[i][j])
        m.append(t)
    return int(round(np.linalg.det(np.array(m)), 0))


# 定义节点类
class Node:
    def __init__(self, value, pre=None):
        self.pre = pre
        self.value = value
        self.succ = []


# 广度优先搜索
def BFS_loop(adj_tree: list, start: int, end: int):
    nodes = [Node(i) for i in range(len(adj_tree))]
    visited = [False] * len(adj_tree)
    visited[start] = True
    queue = [start]
    # BFS搜索
    while queue:
        now = queue.pop(0)
        if now == end:
            break
        for i in range(len(adj_tree)):
            if adj_tree[now][i] == 1 and visited[i] == False:
                nodes[now].succ.append(nodes[i])
                queue.append(i)
                visited[i] = True
    # 为所有后继节点的pre赋值，方便找到父节点
    for node in nodes:
        for i in node.succ:
            i.pre = node
    path = [end]
    # 从终点向回找，找到根节点结束
    while nodes[end].pre:
        end = nodes[end].pre.value
        path.insert(0, end)
    return path


# 基本回路系统
def Basic_loop_system(adj_tree: list, inc: list, side: list):
    chord = list(set(range(len(inc))) - set(side))
    loop_point = []
    # 计算每条弦的回路中的点
    for each in chord:
        e = [i for i in range(len(inc[0])) if inc[each][i] == 1]
        path = BFS_loop(adj_tree, e[0], e[1])
        path.append(e[0])
        loop_point.append(path)
    loop_side = []
    # 根据回路中的点求出对应的边
    for each in loop_point:
        index = 1
        x = []
        while index < len(each):
            t = [0] * len(inc[0])
            t[each[index - 1]], t[each[index]] = 1, 1
            for i in range(len(inc)):
                if inc[i] == t:
                    x.append('e' + str(i) + ' ')
                    break
            index += 1
        loop_side.append(x)
    return loop_side


# 判断是否连通
def Connected(m: list) -> bool:
    visited = [False] * len(m)
    visited[0] = True
    queue = [0]
    # BFS搜索
    while queue:
        now = queue.pop(0)
        for i in range(len(m)):
            if m[now][i] == 1 and visited[i] == False:
                queue.append(i)
                visited[i] = True
    return all(visited)


# 基本割集系统
def Basic_cutset_system(adj_tree: list, side: list, inc: list):
    chord = list(set(range(len(inc))) - set(side))
    cutset_side = []

    for i in range(len(side)):
        adj_tree_copy = copy.deepcopy(adj_tree)
        # 删除树枝
        e = [_ for _ in range(len(inc[0])) if inc[side[i]][_] == 1]
        adj_tree_copy[e[0]][e[1]], adj_tree_copy[e[1]][e[0]] = 0, 0
        x = ['e' + str(side[i])]
        for each in chord:
            # 加上一条弦
            e = [_ for _ in range(len(inc[0])) if inc[each][_] == 1]
            adj_tree_copy[e[0]][e[1]], adj_tree_copy[e[1]][e[0]] = 1, 1
            if Connected(adj_tree_copy):
                # 如果连通则去除该弦，并加入割集
                x.append('e' + str(each))
                e = [_ for _ in range(len(inc[0])) if inc[each][_] == 1]
                adj_tree_copy[e[0]][e[1]], adj_tree_copy[e[1]][e[0]] = 0, 0
        cutset_side.append(x)
    return cutset_side


# 环路空间和断集空间
def space(side: list):
    rep = copy.deepcopy(side)
    for i in range(2, len(side) + 1):
        x = itertools.combinations(range(len(side)), i)
        for e in x:
            t = copy.deepcopy(side[e[0]])
            for j in e[1:]:
                for each in side[j]:
                    if each in t:
                        t.remove(each)
                    else:
                        t.append(each)
            if t not in rep:
                rep.append(t)
    return rep




#主函数
while True:
    print("请输入相邻矩阵：（输入‘0’退出）")
    adj = []
    cin = input()

    if cin == "0":
        break

    while cin:
        adj.append(list(map(int, cin.split())))
        cin = input()

    inc = Incidence_matrix(adj)
    adj_tree, inc_tree, side = tree(inc)

    print("生成树的关联矩阵：")
    print("   ", end="")
    for i in side:
        print('e' + str(i), end=" ")
    print()
    for i in range(len(inc_tree[0])):
        print("v" + str(i), end="  ")
        for j in range(len(inc_tree)):
            print(inc_tree[j][i], end="  ")
        print()

    tree_num = tree_number(adj)
    print(f"\n有 {tree_num} 种实现方案\n")

    loop_side = Basic_loop_system(adj_tree, inc, side)
    print("基本回路系统：")
    print("{ ", end="")
    for i in range(len(loop_side)):
        if i != len(loop_side) - 1:
            print(''.join(loop_side[i]), end=", ")
        else:
            print(''.join(loop_side[i]), end="")
    print("}")

    beltway = space(loop_side)
    print("环路空间：")
    print("{ Φ, ", end="")
    for i in range(len(beltway)):
        if i != len(beltway) - 1:
            print(''.join(beltway[i]), end=", ")
        else:
            print(''.join(beltway[i]), end="")
    print("}")

    print()

    cutset_side = Basic_cutset_system(adj_tree, side, inc)
    print("基本割集系统：")
    print("{ ", end="")
    for i in range(len(cutset_side)):
        print("{ ", end="")
        if i != len(cutset_side) - 1:
            print(','.join(cutset_side[i]), end=" }, ")
        else:
            print(','.join(cutset_side[i]), end=" }")
    print(" }")

    breakset = space(cutset_side)
    print("断集空间：")
    print("{ Φ, ", end="")
    for i in range(len(breakset)):
        print("{ ", end="")
        if i != len(breakset) - 1:
            print(','.join(breakset[i]), end=" }, ")
        else:
            print(','.join(breakset[i]), end=" }")
    print(" }")

    print()

'''
测试数据：
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0

0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

0 2 1 0
2 0 1 1
1 1 0 0
0 1 0 0


教师测试数据：
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 1
1 1 0 1 0

0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
'''

C++:（有点bug）

#include "iostream"
#include "vector"
#include "cmath"
#include "queue"
#include "algorithm"

using namespace std;

vector<vector<int>> guanlianMatrix(vector<vector<int>> l) {
    vector<vector<int>> t;
    for (int i = 0; i < l.size(); i++) {
        for (int j = 0; j < l.size(); j++) {
            if (l[i][j] > 0) {
                for (int k = 0; k < l[i][j]; k++) {
                    vector<int> line;
                    line.assign(l.size(), 0);
                    line[i] = 1;
                    line[j] = 1;
                    t.push_back(line);
                    l[i][j]--;
                    l[j][i]--;
                }
            }
        }
    }
    return t;
}

//获得det[i][j]余子式行列式
vector<vector<int> > complementMinor(vector<vector<int>> det, int i, int j) {

    int n = det.size();//n为det的行，m为det的列；
    vector<vector<int>> ans(n - 1);//保存获得的结果
    for (int k = 0; k < n - 1; k++)
        for (int l = 0; l < n - 1; l++) {
            ans[k].push_back(det[k < i ? k : k + 1][l < j ? l : l + 1]);
        }
    return ans;
}

int Det(vector<vector<int>> det) {
    int ans = 0;
    int n = det.size(), m = det[0].size();//n为det的行，m为det的列；
    if (n != m) {
        exit(1);
    }
    if (det.size() == 1)
        return det[0][0];

    for (int i = 0; i < m; i++) {
        ans += det[0][i] * pow(-1, i) * Det(complementMinor(det, 0, i));
    }
    return ans;
}

int treeNum(vector<vector<int>> l) {
    vector<vector<int>> m;
    for (int i = 1; i < l.size(); i++) {
        vector<int> t;
        for (int j = 1; j < l.size(); j++) {
            if (i == j) {
                int sum = 0;
                for (int k: l[j]) {
                    sum += k;
                }
                t.push_back(sum);
            } else {
                t.push_back(-l[i][j]);
            }
        }
        m.push_back(t);
    }
    return Det(m);
}

void
tree(vector<vector<int>> l, vector<vector<int>> &xianglin, vector<vector<int>> &guanlian, vector<unsigned int> &bian) {
    for (int i = 1; i < 1 << l.size(); i++) {
        bian.clear();
        int n = 0;
        unsigned int x = i, place = 0;
        while (x) {
            if (x & 0x1) {
                bian.push_back(place);
                n++;
            }
            x >>= 1;
            place++;
        }
        if (n == l[0].size() - 1) {
            // 去除第一行判断矩阵是否满秩
            vector<vector<int>> matrix;
            for (auto j: bian) {
                vector<int> t;
                for (int k = 1; k < l[j].size(); k++) {
                    t.push_back(l[j][k]);
                }
                matrix.push_back(t);
            }
            if (Det(matrix) != 0) break;
        }
    }
    // 计算关联矩阵
    for (auto x: bian) {
        guanlian.push_back(l[x]);
    }
    for (int i = 0; i < l[0].size(); i++) {
        vector<int> t;
        t.assign(l[0].size(), 0);
        xianglin.push_back(t);
    }
    // 计算相邻矩阵
    for (auto i: guanlian) {
        vector<int> e;
        for (int j = 0; j < i.size(); j++) {
            if (i[j] == 1) e.push_back(j);
            if (e.size() == 2) break;
        }
        xianglin[e[0]][e[1]] = 1;
        xianglin[e[1]][e[0]] = 1;
    }
}

struct Node {
    Node *parent;
    int num;
};

vector<unsigned int> bfs_loop(const vector<vector<int>> &tree, int start, int end) {
    vector<bool> visited;
    visited.assign(tree.size(), false);
    visited[start] = true;
    vector<Node> points;
    for (int i = 0; i < tree.size(); i++) {
        Node t{nullptr, i};
        points.push_back(t);
    }
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < tree.size(); i++) {
            if (tree[now][i] == 1 && !visited[i]) {
                points[i].parent = &points[now];
                q.push(i);
                visited[i] = true;
            }
        }
        if (now == end) break;
    }
    vector<unsigned int> road;
    road.push_back(end);
    while (points[end].parent) {
        end = points[end].parent->num;
        road.insert(road.begin(), end);
    }
    return road;
}

vector<vector<int>> loop(const vector<vector<int>> &xianglin, vector<vector<int>> guanlian, vector<unsigned int> bian) {
    vector<unsigned int> xian;
    for (int i = 0; i < guanlian.size(); i++) {
        if (!count(bian.begin(), bian.end(), i)) {
            xian.push_back(i);
        }
    }
    vector<vector<unsigned int>> points;
    for (auto x: xian) {
        vector<unsigned int> e;
        for (int i = 0; i < guanlian[0].size(); i++) {
            if (guanlian[x][i] == 1) {
                e.push_back(i);
            }
        }
        vector<unsigned int> t = bfs_loop(xianglin, e[0], e[1]);
        t.push_back(e[0]);
        points.push_back(t);
    }
    vector<vector<int>> result;
    for (auto x: points) {
        int n = 1;
        vector<int> t;
        while (n < x.size()) {
            vector<int> m;
            m.assign(guanlian[0].size(), 0);
            m[x[n - 1]] = 1;
            m[x[n]] = 1;
            for (int i = 0; i < guanlian.size(); i++) {
                if (guanlian[i] == m) {
                    t.push_back(i);
                    break;
                }
            }
            n++;
        }
        result.push_back(t);
    }
    return result;
}

bool liantong(vector<vector<int>> matrix) {
    vector<bool> visited;
    visited.assign(matrix.size(), false);
    visited[0] = true;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < matrix.size(); i++) {
            if (matrix[now][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    for (auto x: visited) {
        if (!x) return false;
    }
    return true;
}

vector<vector<int>>
geji(vector<vector<int>> xianglin, vector<vector<int>> guanlian, vector<unsigned int> bian) {
    vector<unsigned int> xian;
    for (int i = 0; i < guanlian.size(); i++) {
        if (!count(bian.begin(), bian.end(), i)) {
            xian.push_back(i);
        }
    }
    vector<vector<int>> result;
    for (auto x: bian) {
        vector<vector<int>> t(xianglin.begin(), xianglin.end());
        vector<int> e;
        for (int i = 0; i < guanlian[0].size(); i++) {
            if (guanlian[x][i] == 1) {
                e.push_back(i);
            }
        }
        t[e[0]][e[1]] = 0;
        t[e[1]][e[0]] = 0;
        vector<int> edge;
        edge.push_back(x);
        for (auto y: xian) {
            // 添加一条弦
            e.clear();
            for (int i = 0; i < guanlian[0].size(); i++) {
                if (guanlian[y][i] == 1) {
                    e.push_back(i);
                }
            }
            t[e[0]][e[1]] = 1;
            t[e[1]][e[0]] = 1;
            if (liantong(t)) {
                edge.push_back(y);
                t[e[0]][e[1]] = 0;
                t[e[1]][e[0]] = 0;
            }
        }
        result.push_back(edge);
    }
    return result;
}

vector<vector<int>> space(const vector<vector<int>> &circles) {
    vector<unsigned int> selected;
    vector<vector<int>> result;
    for (int i = 1; i < 1 << circles.size(); i++) {
        selected.clear();
        unsigned int x = i, place = 0;
        while (x) {
            if (x & 0x1) {
                selected.push_back(place);
            }
            x >>= 1;
            place++;
        }
        vector<int> t(circles[selected[0]].begin(), circles[selected[0]].end());
        selected.erase(selected.begin());
        for (auto e: selected) {
            for (auto each: circles[e]) {
                if (count(t.begin(), t.end(), each)) {
                    for (auto it = t.begin(); it != t.end();) {
                        if (*it == each) {
                            it = t.erase(it);
                        } else {
                            it++;
                        }
                    }
                } else {
                    t.push_back(each);
                }
            }
        }
        result.push_back(t);
    }
    return result;
}

int main() {
    int n, t;
    cout << "请输入点的个数:" << endl;
    cin >> n;
    cout << "请输入矩阵" << endl;
    vector<vector<int>> m;
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        for (int j = 0; j < n; j++) {
            cin >> t;
            temp.push_back(t);
        }
        m.push_back(temp);
    }
    vector<vector<int>> g = guanlianMatrix(m);
    cout << "关联矩阵为：" << endl << "   ";
    for (int i = 0; i < g.size(); i++) {
        cout << "e" << i << "\t";
    }
    cout << endl;
    for (int i = 0; i < g[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: g) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "共有" << treeNum(m) << "颗树" << endl;
    vector<vector<int>> xianglin, guanlian;
    vector<unsigned int> bian;
    tree(g, xianglin, guanlian, bian);
    cout << "生成树的相邻矩阵为：" << endl << "   ";
    for (int i = 0; i < xianglin.size(); i++) {
        cout << "v" << i << "\t";
    }
    cout << endl;
    for (int i = 0; i < xianglin[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: xianglin) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "生成树关联矩阵为：" << endl << "   ";
    for (auto x: bian) {
        cout << "e" << x << "\t";
    }
    cout << endl;
    for (int i = 0; i < guanlian[0].size(); i++) {
        cout << "v" << i << "  ";
        for (auto &j: guanlian) {
            cout << j[i] << "\t";
        }
        cout << endl;
    }
    cout << "基本回路系统为：" << endl << "{ ";
    vector<vector<int>> circle = loop(xianglin, g, bian);
    for (int i = 0; i < circle.size(); i++) {
        for (int j = 0; j < circle[i].size(); j++) {
            cout << "e" << circle[i][j];
            if (j == circle[0].size() - 1 && i != circle.size() - 1) cout << ", ";
        }
    }
    cout << " }" << endl;

    vector<vector<int>> huanlu = space(circle);
    cout << "环路空间为：" << endl << "{ Φ ,";
    for (int i = 0; i < huanlu.size(); i++) {
        for (int j = 0; j < huanlu[0].size(); j++) {
            cout << "e" << huanlu[i][j];
            if (j == huanlu[0].size() - 1 && i != huanlu.size() - 1) cout << ", ";
        }
    }
    cout << " }" << endl;

    cout << "基本割集系统为：" << endl << "{ ";
    vector<vector<int>> gj = geji(xianglin, g, bian);
    for (int i = 0; i < gj.size(); i++) {
        cout << "{ ";
        for (int j = 0; j < gj[i].size(); j++) {
            if (j == gj[i].size() - 1) {
                cout << "e" << gj[i][j] << " } ";
                if (i != gj.size() - 1) cout << ",";
            } else {
                cout << "e" << gj[i][j] << ",";
            }
        }
    }
    cout << " }" << endl;

    cout << "断集空间为：" << endl << "{ Φ ,";
    vector<vector<int>> dj = space(gj);
    for (int i = 0; i < dj.size(); i++) {
        cout << "{ ";
        for (int j = 0; j < dj[i].size(); j++) {
            if (j == dj[i].size() - 1) {
                cout << "e" << dj[i][j] << " } ";
                if (i != dj.size() - 1) cout << ",";
            } else {
                cout << "e" << dj[i][j] << ",";
            }
        }
    }
    cout << " }" << endl;
    system("pause");
    return 0;
}

4、调试分析

• （1）调试过程中所遇到的问题及解决方法：

  • 部分环路空间输出不全

    解决方法：暂未解决

  • 未熟练掌握BFS

    解决方法：通过网上的素材借鉴理解学习

• （2）算法的时空分析：

  • 1. Incidence_matrix函数

       时间复杂性：

       • O(n^3)，其中 n 为相邻矩阵的边数。主要由三层循环嵌套引起，其中第一和第二层的长度均为 n，第三层的长度最坏为 n。

       空间复杂性：

       • O(n^2)，由于需要存储生成的关联矩阵。

    2. tree函数

       时间复杂性：

       • O(n^4)，主要由两层嵌套循环引起。内部循环中包含对 numpy 的 det 操作，其时间复杂度为 O(n^3)。
       • O(n^2)，由于需要存储生成的关联矩阵。

       空间复杂性：

       • 除了输入数组外，仅使用了常量级别的额外空间，因此空间复杂性为 O(1)。

    3. tree_number函数

       时间复杂性：

       • O(n^3)，由于需要计算 numpy 的 det 操作。

       空间复杂性：

       • O(n^2)，由于需要存储生成的关联矩阵。

    4. Node类

       时间复杂性：

       • 构造函数为 O(1)。

       空间复杂性：

       • O(1)。

    5. BFS_loop函数

       时间复杂性：

       • O(n^2)，由于广度优先搜索中的两层嵌套循环。

       空间复杂性：

       • O(n)，存储节点和队列。

    6. Basic_loop_system函数

       时间复杂性：

       • O(n^4)，包含两层嵌套循环。内部循环中包含对 BFS_loop 函数的调用，其时间复杂度为 O(n^2)。

       空间复杂性：

       • O(n^2)，存储回路点和回路边。

    7. Connected函数

       时间复杂性：

       • O(n^2)，由于广度优先搜索中的两层嵌套循环。

       空间复杂性：

       • O(n)，存储访问标记和队列。

    8. Basic_cutset_system函数

       时间复杂性：

       • O(n^4)，包含两层嵌套循环。内部循环中包含对 Connected 函数的调用，其时间复杂度为 O(n^2)。

       空间复杂性：

       • O(n^2)，存储割集边。

    9. space函数

       时间复杂性：

       • O(2^n * m)，其中 n 为回路的数量，m 为回路平均长度。由于使用了组合生成函数，会生成指数级的组合情况。

       空间复杂性：

       • O(2^n * m)，存储生成的环路空间。

    10. 整体而言：

        • 这个程序的复杂度主要受到生成树和回路系统的计算部分的影响。由于广度优先搜索和组合生成函数的使用，一些函数的时间复杂度可能较高，特别是在处理大规模图的情况下。因此，在实际应用中，可能需要进一步优化算法或采用更高效的数据结构和算法。

• 实际性能可能会受到不同输入情况的影响。

（五）实验结果

（六）实验总结

• 实验过程中的感悟和体会：

  1. 理解图论概念：

     在编写程序之前，我花了一些时间深入理解了图论的基本概念，包括关联矩阵、生成树、回路等。这为编写相应的算法提供了基础。

  2. 算法设计思路：

     实现图论算法需要清晰的思路和设计。我通过分析问题，将整个流程拆分成多个函数，每个函数负责一个具体的功能。这种模块化的设计使得代码更清晰、易读且易于维护。

  3. 广度优先搜索：

     在实现基本回路系统和基本割集系统时，我使用了广度优先搜索算法。这个算法对于遍历图的特定部分非常有效，对于实现问题的解决方案提供了重要的帮助。

  4. 异常处理的重要性：

     在实现生成树和相关计算时，我充分利用了 numpy 库提供的矩阵操作功能。这使得矩阵计算更为简便，加速了程序的执行。

• 经验和教训：

  1. 函数模块化设计：

     在设计程序时，将大问题拆分成小的、相对独立的函数是一个良好的实践。这样不仅提高了代码的可读性，而且降低了出错的可能性。

  2. 异常处理：

     在用户输入部分，我没有添加足够的异常处理机制。在实际应用中，用户可能输入不符合要求的数据，因此要保证程序能够健壮地处理各种输入情况。

  3. 代码注释：

     在一些复杂的算法部分，我添加了注释来解释代码的逻辑和功能。这对于其他人阅读和理解代码非常有帮助，也有助于自己在未来回顾代码时更容易理解。

  4. 优化思考：

     部分算法的时间复杂度可能较高，特别是当图较大时。在实际应用中，可能需要考虑进一步的优化策略，例如改进算法或者使用更高效的数据结构。

• 总结：

  通过这次实验，我不仅学到了图论算法的实现方法，还提高了对算法设计和代码优化的认识。编写图论算法需要对问题有深入的理解，而模块化的设计和代码注释是确保代码质量的关键。

  在未来的工作中，我将更注重对算法复杂度的优化，并且在程序中添加更多的异常处理机制，以提高程序的稳定性。此外，我还计划进一步学习和掌握图论领域的其他算法，以便更好地解决更复杂的问题。这次实验为我打开了图论算法领域的大门，为我的学术和职业发展提供了有益的经验。

参考文献：离散数学II实验二 ： 白