【学习笔记】图的实现和特征

1.图的属性和分类

本部分图的内容，面试的时候应该根据被面试公司的情况看是否需要准备更多内容，文末有相关学习链接 图的属性 Graph(V, E):图是点和边的集合构成的

V -vertex:点 度：入度和出度点与点之间：连通与否 E - edge:边 有向和无向（单行线）权重（边长) 图的表示和分类

图的表示方法有两种，分别是：

邻接矩阵： 有相邻的边加权重，没有的话如果有边加1，没有边的化加 0如果是有向图的话，其邻接矩阵是对称矩阵 邻接表： 用链表来存储和点相连的点的信息，链表最后一个元素为None, 用 / 表示 图的分类 无向无权图 有向无权图 无向有权图 有向有权图

2.基于图相关的算法

DFS代码------递归写法 visited visited visited =set() set() set() set() # 和树中的 DFS 最大的区别

visited = set() # 用来记录访问过的点 def dfs(node,visited): if node in visited: # terminator # already visited return visited.add(node) # proces current node here ... for next_node in node.children(): if not next_node in visited: dfs(next_node,visited)

BFS 代码 visited visited visited =set() set() set() set() # 和树中的 BFS 最大的区别

def BFS(graph,start,end): queue = [] queue.append([start]) visited = set() # 和树中 BFS 的最大区别 while queue: node = queue.pop() visited.add(node) process(node) nodes = generate_related_nodes(node) queue.push(nodes)

图的高级算法 1.连通图的个数 2.拓扑排序 3.最短路径（Dijkstra） 4.最小生成树