考研图知识点总结：
图的概念和基本术语：图由节点和边组成，每个节点可以有一个或多个与之相连的边，边可以有权重或不带权重。常用的图的表示方法有邻接矩阵和邻接表。
图的遍历：深度优先搜索（DFS）和广度优先搜索（BFS）是图的两种常见遍历方法。DFS采用栈的数据结构实现，BFS采用队列的数据结构实现。
最小生成树：最小生成树（MinimumSpanningTree，MST）是连接图中所有节点的一棵生成树，其边权值之和最小。常见的算法有Prim和Kruskal算法。
最短路径：最短路径问题是在给定的带权图中找到两个节点之间的最短路径。常见的算法有Dijkstra算法和Bellman-Ford算法。
拓扑排序：拓扑排序是对有向无环图（DAG）进行的一种排序方法，其中每个节点都必须排在其所有后继节点的前面。拓扑排序算法常用的有Kahn算法和DFS算法。
强连通分量：强连通分量（StronglyConnectedComponent，SCC）是在有向图中定义的一个基本概念，即如果两个节点之间互相可达，则这两个节点属于同一个强连通分量。常见的算法有Tarjan算法和Kosaraju算法。
最大流：最大流（MaximumFlow）问题是在带有容量限制的网络中，找到从源节点到汇节点的最大流量。常见的算法有Ford-Fulkerson算法和Edmonds-Karp算法。
图是由节点和边组成的数据结构，它可以用不同的存储方式来表示。常用的两种表示方法是邻接矩阵和邻接表。
邻接矩阵
邻接矩阵是一个二维数组，它的行和列分别对应着节点的编号，矩阵中的元素表示两个节点之间是否存在一条边。如果矩阵中某个元素的值为1，表示这两个节点之间有一条边；如果值为0，则表示没有边相连。如果图是带权的，矩阵中可以存储边的权重。
邻接矩阵存储方式的优点是查询两个节点之间是否有边的时间复杂度为O(1)，但是它浪费了很多空间，因为大部分节点之间都没有边相连。此外，对于稀疏图，邻接矩阵的空间复杂度很高。
邻接表
邻接表是一种链式存储结构，它用一个数组来存储图的所有节点，每个节点对应一个链表，链表中存储这个节点相邻的节点。链表中的每个节点记录了相邻节点的编号和边的权重。如果图是有向的，邻接表中只存储起始节点指向的终止节点。
邻接表存储方式的优点是可以节省存储空间，对于稀疏图尤其明显。它的缺点是查询两个节点之间是否有边的时间复杂度为O(k)，其中k是相邻节点的平均数，对于稠密图效率较低。
基本操作
在图的存储结构中，常见的基本操作包括：
添加节点和边
删除节点和边
查询节点和边
遍历图
计算最小生成树
计算最短路径
计算强连通分量
计算最大流
这些操作可以通过邻接矩阵和邻接表来实现，具体实现方式会因为使用的存储方式不同而有所区别。
图的遍历是指从图中某个节点出发，按照一定的顺序遍历所有节点的过程。图的遍历算法常用的有深度优先搜索（DFS）和广度优先搜索（BFS）。
以下是DFS和BFS的代码实现：
深度优先搜索（DFS）
DFS的基本思想是从起始节点开始，按照一定的顺序沿着一条路径遍历图，直到不能继续为止，然后回溯到之前的节点继续遍历。
以DFS为例，以下是遍历流程：
从起始节点开始遍历，将其标记为已访问。
访问起始节点的一个邻接节点，若未被访问，则继续以该节点为起点递归遍历，直到该节点没有未被访问的邻接节点为止。
回溯到上一个节点，访问其另一个未被访问的邻接节点，重复步骤2。
当回溯到起始节点时，DFS结束。
邻接表实现：
pythonCopycodedefdfs(graph,start):visited=set()stack=[start]whilestack:node=stack.pop()ifnodenotinvisited:visited.add(node)print(node)forneighboringraph[node]:ifneighbornotinvisited:stack.append(neighbor)
邻接矩阵实现：
pythonCopycodedefdfs(graph,start):visited=set()stack=[start]whilestack:node=stack.pop()ifnodenotinvisited:visited.add(node)print(node)foriinrange(len(graph[node])):ifgraph[node]==1andinotinvisited:stack.append(i)
广度优先搜索（BFS）
BFS的基本思想是从起始节点开始，按照一定的顺序遍历图，先遍历与起始节点距离为1的节点，再遍历距离为2的节点，以此类推。
以BFS为例，以下是遍历流程：
从起始节点开始遍历，将其标记为已访问并将其加入队列。
从队列中取出一个节点，访问它的所有未被访问的邻接节点，并将这些节点加入队列。
重复步骤2，直到队列为空。
邻接表实现：
pythonCopycodefromcollectionsimportdequedefbfs(graph,start):visited=set()queue=deque([start])whilequeue:node=queue.popleft()ifnodenotinvisited:visited.add(node)print(node)forneighboringraph[node]:ifneighbornotinvisited:queue.append(neighbor)
邻接矩阵实现：
pythonCopycodefromcollectionsimportdequedefbfs(graph,start):visited=set()queue=deque([start])whilequeue:node=queue.popleft()ifnodenotinvisited:visited.add(node)print(node)foriinrange(len(graph[node])):ifgraph[node]==1andinotinvisited:queue.append(i)
以上是DFS和BFS的Python代码实现，它们都是基于图的邻接表或邻接矩阵实现的。