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

实验一

（一）实验题目

可图化、可简单图化、连通性的判别及图的矩阵表达

（二）实验目的

1、 掌握可图化的定义及判断方法；

2、 掌握可简单图化的定义及判断方法；

3、 掌握连通图的判断方法；

4、 掌握图的矩阵表达。

（三）实验要求

1、 给定非负整数序列（例如：(4,2,2,2,2)）。

2、 判断此非负整数序列是否是可图化的。

3、 请利用Havel定理判断此非负整数序列是否是可简单图化的，要求输出判断过程与结果。

4、 如果是可简单图化的，请输出该序列对应一个简单图的相邻矩阵，并判断该图是否连通。

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

1、需求分析

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

  • 输入形式：例如4,2,2,2,2（可给定任意数量的序列）
  • 输入值的范围：非负整数

• （2） 输出的形式：

  

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

• （3） 程序所能实现的功能：
  • 能通过输入任意个数的非负整数序列判断是否可图化，是否可简单图化，并输出相邻矩阵和判断是否连通
  • 可循环，反复输入，方便测试多组数据

2、 概要设计

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

• 下面是

• 数据结构定义、主程序的流程及各模块之间的调用关系：

  # 可图化
  def Graphitization():
  	# 通过定理d1+d2+…+dn=0(mod 2)判断是否可图化
  
  # 可简单图化
  def Graphitization_simple():
  	# 先通过n-1≥d1筛选判断
  	# 再通过Havel定理判断是否可简单图化
  
  #相邻矩阵
  def Adjacency_matrix():
  	# 通过优化后的Havel-Hakimi 算法将序列转换成
  	# 相邻矩阵并输出
  
  #连通
  def Connected():
  	# 通过DFS深度优先搜索判断是否连通
  
  #主函数
  While True:
  	# 判断是否可图化
  	if Graphitization():
  		# “可图化”
  		# 判断是否可简单图化
  		if Graphitization_simple():
              # “可简单图化”
              # 判断图是否连通
              if Connected():
                  # “可连通”
              else:
                  # “不可连通”
          else:
          # “不可简单图化”
      else:
          # “不可图化”

3、详细设计

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

• Python:

# 可图化
def Graphitization(array):
    sum = 0
    for i in range(len(array)):
        sum += array[i]
    if sum % 2 == 0 and sum != 0:
        return True
    return False

# 可简单图化
def Graphitization_simple(array):
    a = sorted(array, reverse=True)     #降序排序
    if a[0] >= len(array):
        print("但不满足n-1>=d1")
        return False
    string = '('
    for i in range(len(a)):
        if i != len(a)-1:
            string += str(a[i]) + ','
        else:
            string += str(a[i])
    print(string+')可简单图化？')
    while True:
        head = a.pop(0)
        for i in range(head):
            a[i] -= 1
        a = sorted(a, reverse=True)  # 降序排序
        string = '⇔('
        for i in range(len(a)):
            if i != len(a) - 1:
                string += str(a[i]) + ','
            else:
                string += str(a[i])
        print(string + ')可简单图化')
        if a.count(0) == len(a):
            return True
        if a.count(1) == 1 and a.count(0) == len(a)-1:
            return False
        for i in range(len(a)):
            if a[i] < 0:
                return False

# 二维列表排序
def sort_two(a):
    for i in range(len(a[0])):
        for j in range(i, len(a[0])):
            if a[0][i] < a[0][j]:
                a[0][i], a[0][j] = a[0][j], a[0][i]
                a[1][i], a[1][j] = a[1][j], a[1][i]

# 相邻矩阵
def Adjacency_matrix(array, m):
    a = [[0] * len(array) for _ in range(2)]
    a[0] = sorted(array, reverse=True)     #降序排序
    for i in range(len(array)):
        a[1][i] = i
    for i in range(len(array)):
        for j in range(len(array)):
            for k in range(len(array)):
                if a[1][k] ==  i and a[0][k] > 0 and a[0][j] > 0 and i < a[1][j]:
                    m[i][ a[1][j] ] = 1
                    m[ a[1][j] ][i] = 1
                    a[0][j] -= 1
                    a[0][k] -= 1
        sort_two(a)
    print("其相邻矩阵为：")
    for i in range(len(array)):
        for j in range(len(array)):
            print(m[i][j], end=' ')
        print()

# 连通
def Connected(m):
    def dfs(node):
        visited[node] = True
        for neighbor, has_edge in enumerate(m[node]):
            if has_edge and not visited[neighbor]:
                dfs(neighbor)
    n = len(m)
    visited = [False] * n
    # 从第一个节点开始深度优先搜索
    dfs(0)
    # 如果所有节点都被访问到，则图是连通的
    return all(visited)



# 主函数
while True:
    # 从用户输入获取非负整数序列
    cin = input("请输入非负整数序列（用逗号分隔），输入0结束: ")

    if cin == '0':
        break

    try:
        # 将输入的字符串转换为非负整数序列
        array = list(map(int, cin.split(',')))
        m = [ [0 for _ in range(len(array))] for _ in range(len(array)) ]

        # 判断是否可图化
        if Graphitization(array):
            print("该序列“可图化”")

            # 判断是否可简单图化
            if Graphitization_simple(array):
                print("故：该序列“可简单图化”")
                Adjacency_matrix(array, m)
                # 判断图是否连通
                if Connected(m):
                    print("且该图是“连通”的")
                else:
                    print("且该图是“不连通”的")
            else:
                print("故：该序列“不可简单图化”")

        else:
            print("该序列“不可图化”")

        print()

    except ValueError:
        print("输入错误！请确保输入为非负整数序列，并使用逗号分隔。")

• C++:

#include <iostream>

using namespace std; 

int n, nn, a[100]={0}, b[2][100] = {0}, array[100]={0}, m[100][100]={0};

//一维降序排序
void sort1()
{
	for (int i=0; i<nn; i++)
	{
		for (int j=i; j<nn; j++)
		{
			if (a[i] < a[j])
			{
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
}

//二维降序排序 
void sort2()
{
	for (int i=0; i<n; i++)
	{
		for (int j=i; j<n; j++)
		{
			if (b[0][i] < b[0][j])
			{
				int temp = b[0][i];
				b[0][i] = b[0][j];
				b[0][j] = temp;
				temp = b[1][i];
				b[1][i] = b[1][j];
				b[1][j] = temp;
			}
		}
	}
}

//可图化
bool Graphitization()
{
	int sum = 0;
	for (int i=0; i<n; i++) sum += array[i];
	if ( sum%2 == 0 ) return true;
	return false;
}

//点数字的个数 
int count(int num)
{
	int sum = 0;
	for (int i=0; i<nn; i++)
	{
		if (a[i] == num) sum++;
	}
	return sum;
}

//可简单图化
bool Graphitization_simple()
{
	sort1();
	if (a[0] >= n)
	{
		cout << "不满足n-1>=d1" << endl;
		return false;
	}
	cout << "(";
	for (int i=0; i<n; i++)
	{
		if (i != n-1) cout << a[i] << ",";
		else cout << a[i];
	}
	cout << ")可简单图化" << endl;
	while(1)
	{
		int head = a[0];
		for (int i=0; i<nn-1; i++) a[i] = a[i+1];
		nn--;
		a[nn]=0;
		for (int i=0; i<head; i++) a[i]--;
		sort1();
		cout << "<=>(";
		for (int i=0; i<n; i++)
		{
			if (i != n-1) cout << a[i] << ",";
			else cout << a[i];
		}
		cout << ")可简单图化" << endl;
		if (count(0) == nn) return true;
		if (count(1) == 1 && count(0) == nn-1) return false;
		for (int i=0; i<nn; i++)
		{
			if (a[i] < 0) return false;
		}
	}
}

//相邻矩阵
void Adjacency_matrix()
{
	for (int i=0; i<n; i++) a[i] = array[i];
	sort1();
	for (int i=0; i<n; i++)
	{
		b[0][i] = a[i];
		b[1][i] = i;
	}
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			for (int k=0; k<n; k++)
			{
				if (b[1][k]==i && b[0][k]>0 && b[0][j]>0 && i<b[1][j])
				{
					m[i][b[1][j]] = 1;
					m[b[1][j]][i] = 1;
					b[0][j]--;
					b[0][k]--;
				}
			}
		}
		sort2();
	}
	cout << "其相邻矩阵为：" << endl;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			cout << m[i][j] << " ";
		}
		cout << endl;
	}
}

//连通 
// 使用深度优先搜索判断图的连通性
void dfs(bool visited[], int node) {
    visited[node] = true;
    for (int neighbor = 0; neighbor < n; ++neighbor) {
        if (m[node][neighbor] == 1 && !visited[neighbor]) {
            dfs(visited, neighbor);
        }
    }
}
// 判断图的连通性
bool Connected() {
    bool visited[n] = {false};

    // 从第一个节点开始进行深度优先搜索
    dfs(visited, 0);

    // 检查所有节点是否都被访问到
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            return false; // 存在未访问到的节点，图不连通
        }
    }

    return true; // 所有节点都被访问到，图连通
}

int main()
{
	while(1)
	{
		//从用户输入获取非负整数序列
		cout << "请输入个数n：(输入0退出)" << endl;
		cin >> n;
		nn = n;
		
		if (n==0) break;
		
		for (int i=0; i<n; i++) cin >> array[i];
		for (int i=0; i<n; i++) a[i] = array[i];
		
		for (int i=0; i<100; i++)
		{
			for (int j=0; j<100; j++)
			{
				m[i][j] = 0; 
			}
		}
		
		//判断是否可图化
		if (Graphitization())
		{
			cout << "该序列可图化" << endl;
			
			//判断是否可简单图化
			if (Graphitization_simple())
			{
				cout << "故该序列可简单图化" << endl;
				Adjacency_matrix();
				//判断图是否连通
				if (Connected()) cout << "且该图是连通的" << endl;
				else  cout << "且该图是不连通的" << endl;
			}
			else cout << "故该序列不可简单图化" << endl;
			
		} 
		else cout << "该序列不可图化" << endl;
		cout << endl;
	}
	return 0;
}

4、调试分析

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

  • 判断可图化时未考虑到全0的情况导致出错

    解决方法：将sum!=0加入if判断

  • 判断可简单图化时未考虑到n-1≥d1的情况

    解决方法：已添加

  • 判断连通时未熟练掌握DFS

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

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

  • 1. Graphitization(array)

       时间复杂性：

       • 算法中的循环次数与输入数组的长度成正比，因此时间复杂性为 O(n)。

       空间复杂性：

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

    2. Graphitization_simple(array)

       时间复杂性：

       • 算法中的排序操作为 O(n log n)，其中 n 为数组的长度。

       • 主循环的时间复杂性主要取决于排序操作，因此总体时间复杂性为 O(n log n)。

       空间复杂性：

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

    3. sort_two(a)

       时间复杂性：

       • 该算法是选择排序，时间复杂性为 O(n^2)，其中 n 为二维列表中的列数。

       空间复杂性：

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

    4. Adjacency_matrix(array, m)

       时间复杂性：

       • 该算法中的主循环中包含排序和嵌套循环，因此时间复杂性可能高达 O(n^3)，其中 n 为数组的长度。

       空间复杂性：

       • 除了输入数组和邻接矩阵外，仅使用了常量级别的额外空间，因此空间复杂性为 O(n^2)。

    5. Connected(m)

       时间复杂性：

       • 深度优先搜索的时间复杂性为 O(V + E)，其中 V 为节点数，E 为边数。在这里，E 的最坏情况可能是 O(n^2)，因此总体时间复杂性为 O(n^2)。

       空间复杂性：

       • 除了输入的邻接矩阵和递归调用栈，仅使用了常量级别的额外空间，因此空间复杂性为 O(n)。

    6. 总体时空复杂性：

       • 主程序的循环次数取决于用户输入，可以忽略。

• 这里的分析是基于每个算法的最坏情况。

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

（五）实验结果

（六）实验总结

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

  1. 图论知识的应用：

     通过编写判断序列是否可图化、可简单图化的程序，深入理解了图论中的一些概念，例如图的连通性和邻接矩阵的应用。

  2. 深度优先搜索的重要性：

     实验中通过深度优先搜索判断图的连通性，深刻体会到深度优先搜索在图算法中的重要性。这种算法可以用来遍历图，查找路径，判断连通性等。

  3. 函数模块化的优势：

     将任务分解成不同的函数，每个函数负责一个明确的功能，提高了代码的可读性和可维护性。每个函数成为一个模块，更易于理解和测试。

  4. 异常处理的重要性：

     在用户输入时，通过异常处理机制可以有效地捕获错误，向用户提供友好的提示信息。这对于用户友好性和程序的稳定性都是至关重要的。

• 经验和教训：

  1. 合理利用函数：

     函数的使用使代码更为模块化和结构化，有助于提高代码的可读性。在实验中，函数的设计有助于更好地组织和管理代码。

  2. 注重异常处理：

     在用户输入部分，通过对异常的捕获和处理，提高了程序的健壮性。对于用户可能输入错误的情况，提供清晰的错误提示是良好实践。

  3. 代码注释和输出信息：

     充分利用注释和输出信息，有助于自己和其他人更好地理解代码的逻辑和执行流程。在输出信息中，提供详细和清晰的结果有助于用户理解程序运行的结果。

  4. 持续学习和改进：

     在实验中可能遇到一些挑战和问题，但通过不断学习和改进，能够更好地理解问题的本质，并提高解决问题的能力。

• 总结：

  通过这个实验，不仅巩固了图论的相关知识，还提高了编写图算法的能力。在实践中，注重代码的可读性、异常处理和输出信息，是编写高质量代码的关键。在今后的学习和工作中，将继续保持学习的态度，不断提升编程技能。

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