实验一

（一）实验题目

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

（二）实验目的

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

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

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

4、 掌握图的矩阵表达。

（三）实验要求

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

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

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

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

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

1、需求分析

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

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

  • （2） 输出的形式：

    img

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

img

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

2、 概要设计

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

  • 下面是

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    # 可图化
    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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# 可图化
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++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#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. 总体时空复杂性：

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

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

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

（五）实验结果

img

img

img

img

img

img

img

（六）实验总结

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

    1. 图论知识的应用：

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

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

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

    3. 函数模块化的优势：

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

    4. 异常处理的重要性：

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

  • 经验和教训：

    1. 合理利用函数：

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

    2. 注重异常处理：

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

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

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

    4. 持续学习和改进：

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

  • 总结：

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

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