图论算法对于许多图论问题，并不是必须构建符合graph规则的邻接矩阵
本来邻接矩阵是用来表示2个节点是否可以到达的，对邻接表来说各节点是0，1，2…，所以如果用邻接表来表示图表的话，就有必要制作对象和0，1，2…的数字的对应关系。 多数情况下，图论问题的节点是问题给出的对象，两个节点之间的直接联系关系是基于问题给出的条件得到的，任意两个节点(所以，大多数主题并不是先根据规则构造邻接表，再使用图论算法最短路径DFS实现：递归(代码略) ) ) ) ) ) ) ) ) )最短路径DFS实现：递归(代码略) ) ) ) ) )。
应用：无环形图
对于：状态转移有环，但是并非求最短路径的题目
使用DFS path数组实现如果状态转移出现重叠子问题（即每个节点被多次使用），并且满足最优子结构（即一个节点不管其下面有多少种路径，但返回值只有一个）可以转移到动态规划问题，并使用记忆化搜索BFS实现队列
如果有环，则添加并应用visited数组。 您没有创建图的权限
例题【LeetCode】提示和BFS
将应用浮动算法。 所有图(即，有权和不有权两者)
实现是一种动态规划算法
每个状态有两个决定因素：开始节点和结束节点。 也就是说，dp序列是二维的
状态转移方程
fun(I，j )=max([I，j]，=max([I，k] [k，j] ) )
typedef struct { char vertex [ vertex num ]； //顶点表int edges[VertexNum][VertexNum]； //邻接矩阵(对两边不能到达的是无限的) int n，e； //图中当前顶点数和边数}MGraph； VoidFloyd(mgraphg ) { int A[MAXV][MAXV]； //dp数组int path[MAXV][MAXV]； //路径(对应于dp数组的每个节点的下一步) int i，j，k，n=g.n； //dp初始化序列(DP问题大多初始化或多切一行)。 for(I=0； in； I ) for(j=0； jn； j({a[I][j]=g.Edges[I][j] )； path[i][j]=-1； }//常规动态规划模板//此k为什么放在最外层，是因为状态方程dij(k )=min(dij(k-1 )，dik(k-1 ) dkj ) )、k-1 )、k-1表示k 那么，把状态多的那个属性放在最外层，把里面的二次元看作一个整体，每个外层增加一个来选择最佳。 (和背包问题很相似。 关于k只能选择一次。 一旦选择了k进行中继，如果选择了k进行中继，就会形成一个圈，无法到达I或j。 因此，问题是每个节点只能选择一次。 那么，因为只有选择和不选择这两个，所以是背包问题。 for(k=0； kn； k ) for(I=0； in； I ) for(j=0； jn； j () if ) a[I][j] ) a[I][k]a[k] ) { A[i][j]=A[i][k] A[k][j] )； path[i][j]=k； }}}}最小生成树Prim算法核心：基于贪心算法
状态转移： i - j
条件：未选择j，权重最小。 在这里，I是被选择的所有节点的集合，Prim算法是基于贪婪算法设计的，从一个顶点出发，在从该顶点出发的边中选择权重最小的一个添加到最小生成树中，然后从当前树的所有顶点出发
让我举一个例子来说明。
上图是无向图。 假设从顶点a开始使用Prim算法计算最小生成树。 该算法的执行过程如下。
顶点a出的边包括a、b和a、d和a、f，其中权重最小的边是a、f。 因此，将边a、f追加到最小生成树中。 此时，最小生成树中包含下图的阴影边和灰色的顶点。
然后，在从当前最小生成树顶点开始的所有边中，继续查找权重最小的边a、b、a、d、f、c的边a、d，如下图所示。
继续上述步骤，如下图所示，选择从顶点a、f、d发出的边中权重最小的边，即边a、b，将其添加到树上。
重复上述步骤，最终得到的图的最小生成树如下图所示。