有向图的度怎么算图论一般图的定义是什么？-创新互联

2.路径和环我们称无重复点的路径为简单路径。环的定义是基于路径的定义，称为环。同样，我们也有简单的环，也就是说，除了起点和终点外，其余的环都不会经过重复的点，称为简单环。

3.子图是一个小图。我们选择一个大图的一些点，然后选择这些点之间连接的一些边。这样一个小的图叫做子图。

4.如果在连通图中有一条从一点到另一点的路径，那么这两点是连通的。如果所有的点都是连通的，这样的图称为连通图。

5.如果没有环，树和森林的连通图称为树。如果图中没有环，我们称之为森林。

有深度优先和拓扑排序方法来确定有向图是否有环。

1.拓扑排序，如果可以用拓扑排序来完成对图中所有节点的排序，则表示图中没有环，如果不能完成，则表示有环。

2、强连通分量。我们可以回忆一下强连通子图的概念，也就是说，对于一个图的子图，子图中的任何U->V必须有V->U，那么它就是一个强连通子图。这个限制正是环的概念。所以我认为，通过寻找图的强连通子图，我们应该能够找出图中是否有环，以及有多少环。

3.改进的DFS不能仅由DFS使用。如果问题是一个无向图，那么DFS可以被解决。但无向图不能得到正确的结果。例如：a->B，a->C->B，我们用DFS来处理这个图，我们会发现它有环，但它没有。我们可以通过稍微改变DFS来解决这个问题。解决方法如下：图中的一个节点，根据其C[n]值，有三种状态：0，该节点未被访问-1，至少被访问过一次，其子节点正在被访问，1，其子节点已被访问。根据这个假设，当根据DFS进行搜索时，有三种可能：1。如果C[v]=0，则它是一个新节点，不会被处理。2如果C[v]=-1，则表示在访问节点的子节点的过程中访问了节点本身，则图中存在一个环。三。如果C[v]=1，类似于2的导数，则不存在环。在程序中加入一些特殊的处理，即在图中找出几个环并记录每个环的路径