数据结构与算法-图

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

图可以分为有向图（directed graph）和无向图（undirected graph）。有向图中的边有一个方向，而无向图中的边没有方向。

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

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

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

from collections import defaultdict

class 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] = True
        print(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开始进行深度优先搜索。输出的结果就是深度优先搜索的顺序。