"20151910042-刘鹏-DSA实验14-图结构实验1报告"

本次实验的目的是熟悉与图有关的数据结构与算法，并熟悉主讲教材Chapter 14的代码片段。实验内容包括与图有关的数据结构设计与算法设计以及调试主讲教材Chapter 14的Python程序。 实验平台为Windows 10 Enterprise中文版，使用Python 3.6.0和Wing IDE Professional 6.0.5-1集成开发环境。 实验开始，首先进行邻接图的实现。邻接图是一种图的表示方式，可以用于表示有向图和无向图。对于这个实验，需要保证程序能够兼容有向图和无向图。 具体的代码如下： ```Python 1 class Graph: 2 def __init__(self, num_vertices, directed=False): 3 self.num_vertices = num_vertices 4 self.directed = directed 5 self.adj_matrix = [[0] * num_vertices for i in range(num_vertices)] 6 7 def add_edge(self, src, dst, weight=1): 8 if src == dst: 9 print("src and dst are the same vertex.") 10 return 11 12 self.adj_matrix[src][dst] = weight 13 14 if not self.directed: # 如果是无向图 15 self.adj_matrix[dst][src] = weight 16 17 def remove_edge(self, src, dst): 18 self.adj_matrix[src][dst] = 0 19 if not self.directed: # 如果是无向图 20 self.adj_matrix[dst][src] = 0 21 22 def __len__(self): 23 return self.num_vertices 24 25 def display(self): 26 for i in range(self.num_vertices): 27 for j in range(self.num_vertices): 28 print(self.adj_matrix[i][j], end=' ') 29 print() 30def main(): 31 g = Graph(5) 32 g.add_edge(0, 1, 1) 33 g.add_edge(0, 2, 1) 34 g.add_edge(1, 3, 1) 35 g.add_edge(2, 4, 1) 36 37 g.display() 38if __name__ == '__main__': 39 main() ``` 上述代码中，首先定义了一个Graph类，构造函数用于初始化图的相关属性，包括顶点的个数和是否是有向图。add_edge方法用于添加边，参数包括起始顶点、结束顶点和边的权重。remove_edge方法用于删除边。__len__方法返回图中顶点的个数。display方法用于打印出图的邻接矩阵表示。 在主函数中，创建了一个包含5个顶点的图，添加了一些边，并打印出邻接矩阵。 实验结果分析： 运行以上代码，可以得到如下结果： ``` 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 ``` 上面的矩阵是图的邻接矩阵表示。矩阵的行和列分别对应图中的顶点，矩阵元素表示相应顶点之间的边的权重。 本次实验主要目的是通过邻接图的设计与调试，熟悉与图有关的数据结构与算法，并熟悉主讲教材Chapter 14的代码片段。通过本次实验，我对于图的表示以及图的相关操作有了更深的理解，对于邻接图的实现也有了一定的掌握。同时，通过调试代码，我也进一步熟悉了Python语言的使用和调试技巧。总体来说，本次实验对于我的数据结构与算法实践能力的提升有着积极的促进作用。