您的位置:首页 > 科技 > 能源 > 数据结构与算法-图

数据结构与算法-图

2024/12/23 19:07:54 来源:https://blog.csdn.net/Xxy_1008/article/details/139449174  浏览:    关键词:数据结构与算法-图

图是由顶点(vertex)和边(edge)组成的一种数据结构。顶点代表图中的节点,边代表节点之间的关系。

图可以分为有向图(directed graph)和无向图(undirected graph)。有向图中的边有一个方向,而无向图中的边没有方向。

常见的图算法包括广度优先搜索(BFS)、深度优先搜索(DFS)、拓扑排序(topological sorting)、最短路径算法(如Dijkstra算法和Floyd-Warshall算法)等。

图的表示方法有邻接矩阵(adjacency matrix)和邻接表(adjacency list)两种常见的形式。邻接矩阵用一个二维数组表示图中顶点之间的连接关系,邻接表则用一个数组加上链表的形式表示。

图在实际中的应用非常广泛,比如社交网络中的好友关系可以用图来表示,地图上的城市和道路可以用图来描述。掌握图的数据结构和常用的算法对解决各类问题非常有帮助。

from collections import defaultdictclass Graph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v):self.graph[u].append(v)self.graph[v].append(u)def dfs(self, v, visited):visited[v] = Trueprint(v, end=' ')for i in self.graph[v]:if not visited[i]:self.dfs(i, visited)def dfs_traversal(self, start):visited = [False] * len(self.graph)self.dfs(start, visited)# 创建一个Graph对象
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)print("深度优先搜索结果:")
g.dfs_traversal(0)

在这段代码中,我们首先定义了一个Graph类来表示无向图。通过调用add_edge方法来添加图中的边,然后使用dfs方法来进行深度优先搜索,并使用dfs_traversal方法来遍历整个图。

在示例代码中,我们创建了一个简单的无向图,并从顶点0开始进行深度优先搜索。输出的结果就是深度优先搜索的顺序。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com