移动端网站建设的尺寸石家庄手机网站建设公司

移动端网站建设的尺寸,石家庄手机网站建设公司,wordpress动漫主题,dz怎么做视频网站邻接矩阵 资料#xff1a;https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf 一、邻接矩阵的定义 邻接矩阵是图的一种基础存储方式#xff0c;通过一个二维数组来表示图中顶点之间的邻接关系。对于包含 n 个顶…邻接矩阵资料https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf一、邻接矩阵的定义邻接矩阵是图的一种基础存储方式通过一个二维数组来表示图中顶点之间的邻接关系。对于包含n个顶点的图邻接矩阵是一个n×n的矩阵adj矩阵中的元素adj[i][j]用于标识顶点i和顶点j之间是否存在边以及边的相关属性如权重。邻接矩阵可同时存储无向图、有向图和加权图仅需调整矩阵元素的取值规则。二、邻接矩阵的取值规则1. 无权无向图若顶点i和顶点j之间存在无向边则adj[i][j] 1adj[j][i] 1矩阵对称若不存在边则adj[i][j] 0adj[j][i] 0顶点自身无环时adj[i][i] 0允许自环的场景可设为1。2. 无权有向图若存在从顶点i指向顶点j的有向边则adj[i][j] 1若不存在该方向的边则adj[i][j] 0矩阵非对称adj[i][j]与adj[j][i]无必然相等关系。3. 加权图若顶点i到j存在边且权重为w则adj[i][j] w若不存在边则adj[i][j] ∞通常用一个极大值表示如float(inf)无向加权图的矩阵对称有向加权图的矩阵非对称。三、邻接矩阵的核心特性对称性无向图的邻接矩阵是对称矩阵即adj[i][j] adj[j][i]有向图的邻接矩阵通常非对称仅在两顶点间存在双向边时对应位置元素相等。空间复杂度固定为O(n²)其中n为顶点数量与图的边数无关对于稀疏图边数远小于n²会造成大量空间浪费对于稠密图边数接近n²空间利用率较高。操作效率查询边是否存在时间复杂度为O(1)可直接通过矩阵下标访问查询顶点的度无向图中顶点i的度为第i行或第i列所有元素的和有向图中顶点i的出度为第i行元素和入度为第i列元素和添加/删除边时间复杂度为O(1)仅需修改对应矩阵元素的值遍历顶点邻接边时间复杂度为O(n)需遍历该行所有n个元素效率低于邻接表。四、邻接矩阵的实现示例1. 无权无向图的邻接矩阵实现classAdjMatrixUndirectedGraph:def__init__(self,num_vertices):self.num_verticesnum_vertices# 初始化n×n的零矩阵self.adj_matrix[[0for_inrange(num_vertices)]for_inrange(num_vertices)]defadd_edge(self,u,v):添加无向边(u, v)if0uself.num_verticesand0vself.num_vertices:self.adj_matrix[u][v]1self.adj_matrix[v][u]1defremove_edge(self,u,v):删除无向边(u, v)if0uself.num_verticesand0vself.num_vertices:self.adj_matrix[u][v]0self.adj_matrix[v][u]0defhas_edge(self,u,v):判断是否存在边(u, v)if0uself.num_verticesand0vself.num_vertices:returnself.adj_matrix[u][v]1returnFalsedefget_vertex_degree(self,v):获取顶点v的度if0vself.num_vertices:returnsum(self.adj_matrix[v])return-1defdfs(self,start,visitedNone):深度优先搜索基于邻接矩阵ifvisitedisNone:visited[False]*self.num_vertices visited[start]Trueprint(start,end )foriinrange(self.num_vertices):ifself.adj_matrix[start][i]1andnotvisited[i]:self.dfs(i,visited)2. 加权有向图的邻接矩阵实现classAdjMatrixWeightedDigraph:def__init__(self,num_vertices):self.num_verticesnum_vertices INFfloat(inf)# 初始化n×n矩阵默认无无边权重为无穷大自身到自身权重为0self.adj_matrix[[INFfor_inrange(num_vertices)]for_inrange(num_vertices)]foriinrange(num_vertices):self.adj_matrix[i][i]0defadd_edge(self,u,v,weight):添加有向边u, v权重为weightif0uself.num_verticesand0vself.num_vertices:self.adj_matrix[u][v]weightdefget_edge_weight(self,u,v):获取边u, v的权重if0uself.num_verticesand0vself.num_vertices:returnself.adj_matrix[u][v]returnfloat(inf)deffloyd_warshall(self):Floyd-Warshall算法求解多源最短路径nself.num_vertices# 初始化距离矩阵为邻接矩阵dist[row[:]forrowinself.adj_matrix]# 遍历中间顶点kforkinrange(n):# 遍历起点iforiinrange(n):# 遍历终点jforjinrange(n):# 通过中间顶点k优化i到j的路径ifdist[i][k]dist[k][j]dist[i][j]:dist[i][j]dist[i][k]dist[k][j]returndist使用示例# 无权无向图示例undir_graphAdjMatrixUndirectedGraph(5)undir_graph.add_edge(0,1)undir_graph.add_edge(0,2)undir_graph.add_edge(1,3)print(顶点0的度:,undir_graph.get_vertex_degree(0))# 输出2print(是否存在边(0,1):,undir_graph.has_edge(0,1))# 输出Trueprint(DFS遍历结果:)undir_graph.dfs(0)# 输出0 1 3 2# 加权有向图示例weighted_digraphAdjMatrixWeightedDigraph(4)weighted_digraph.add_edge(0,1,2)weighted_digraph.add_edge(0,2,4)weighted_digraph.add_edge(1,2,1)weighted_digraph.add_edge(1,3,7)weighted_digraph.add_edge(2,3,3)shortest_distweighted_digraph.floyd_warshall()print(\n多源最短路径矩阵:)forrowinshortest_dist:print(row)五、邻接矩阵与邻接表的对比特性邻接矩阵邻接表空间复杂度O(n²)与边数无关O(边存在性查询O(1)效率高O(deg(v))需遍历邻接表邻接边遍历O(n)需遍历整行O(deg(v))仅遍历邻接顶点边添加/删除O(1)直接修改元素链表/数组操作效率视结构而定适用场景稠密图、顶点数少的图稀疏图、顶点数多的图六、邻接矩阵的典型应用稠密图的存储与操作如完全图、社交网络中高连通度的子图邻接矩阵的空间利用率高且查询效率优多源最短路径求解Floyd-Warshall算法基于邻接矩阵实现可高效求解任意两顶点间的最短路径图的连通性快速判断通过矩阵幂运算邻接矩阵的k次幂可表示k步可达性判断顶点间的路径存在性小规模图的可视化邻接矩阵的二维结构可直观展示顶点间的连接关系便于人工分析。