c语言，无向图如何检测是否有环？

一、c语言，无向图如何检测是否有环？

有向图是否有环的判定算法，主要有深度优先和拓扑排序2中方法。

1、拓扑排序，如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。

2、Strongly Connected Components。我们可以回忆一下强连通子图的概念，就是说对于一个图的某个子图，该子图中的任意u->v,必有v->u，则这是一个强连通子图。这个限定正好是环的概念。所以我想，通过寻找图的强连通子图的方法应该可以找出一个图中到底有没有环、有几个环。

3、改进的DFS单纯用DFS是不能够的。如果题目给出的是一个无向图，DFS是可以解决的。但无向图得不出正确结果的。比如：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但其实没有。 我们可以对DFS稍加变化，来解决这个问题。解决的方法如下： 图中的一个节点，根据其C[N]的值，有三种状态： 0，此节点没有被访问过 -1，被访问过至少1次，其后代节点正在被访问中 1，其后代节点都被访问过。 按照这样的假设，当按照DFS进行搜索时，碰到一个节点时有三种可能： 1、如果C[V]=0，这是一个新的节点，不做处理 2、如果C[V]=-1，说明是在访问该节点的后代的过程中访问到该节点本身，则图中有环。 3、如果C[V]=1，类似于2的推导，没有环。 在程序中加上一些特殊的处理，即可以找出图中有几个环，并记录每个环的路径.

二、有向图和无向图的区别？

有向图和无向图是图论中两个基本的概念，它们的区别在于图中的边是否有方向。

无向图中的边没有方向，可以双向通行，也就是说，如果存在一条从节点A到节点B的边，那么也一定存在一条从节点B到节点A的边。无向图中的边可以用一个简单的线段表示。

而有向图中的边有方向，只能单向通行，也就是说，如果存在一条从节点A到节点B的边，那么并不一定存在一条从节点B到节点A的边。有向图中的边可以用一个箭头表示，箭头指向的是边的终点。

除了边的方向不同，有向图和无向图在其他方面都是相似的，都由节点和边组成。在有向图中，节点的入度是指指向该节点的边的数量，出度是指从该节点出发的边的数量。而在无向图中，节点的度数是指与该节点相连的边的数量。

总之，有向图和无向图是两种不同的图形结构，它们在边的方向、节点的入度和出度等方面都有所不同。在实际应用中，需要根据具体情况选择使用哪种类型的图。

三、有向图和无向图的度数一样吗？

总度数(D)等于边数(e)的两倍。

D=2e

图G的顶点数n和边数e的关系

1、若G是无向图，则0≤e≤n(n-1)/2。

恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)。

2、若G是有向图，则0≤e≤n(n-1)。

恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。

四、有向图和无向图的深度优先一样吗？

看下算法导论，那里面用的顶点染色，对有向图、无向图处理是一样的。

五、【讨论】“拓扑排序算法仅适用于有向无环图”，对吗？

我觉得是错的，拓扑排序也经常用来判定一个有向图是否有环，所以做为判定方法的话，肯定无论有环无环都能用的

六、什么是非连通无向图？

定义连通：对图中任意顶点u,v,都存在路径使u、v连通。 定义无向图：任意一条边都代表u连v以及v连u.所以非连通无向图定义可推。

七、6阶无向完全图有几条边？

一、有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。

首先，有向连通的一个必要条件是图的无向底图连通，这意味着E >= n-1。

其次，证明E > n-1。因当E=n-1时，无向底图为树，任取两顶点s，t，从s到t有且只有一条无向路径，若有向路径s->t连通，则有向路径t->s必不存在。得证： 再次，证明E可以=n。设n个顶点v1，v2，...vn,顺次连接有向边v1v2，v2v3...vn-1vn，vnv1,这个环是有向连通的。 因此最少有n条边。 二、最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。

八、4阶无向完全图有几条边？

无向图的最多边是无向完全图：包含 n(n-1)/2条边。因为一条边关联两个结点，有向完全图的才有n(n-1)条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。

九、与无向图相关的术语有哪些？

与无向图相关的术语包括以下内容：顶点（Vertex）：无向图中的节点，通常用圆或点表示。边（Edge）：无向图中连接两个顶点的线段，通常用直线或曲线表示。度（Degree）：一个顶点的度是指与该顶点相连的边的数量。连通分量（Connected Component）：无向图中的一个子图，其中任意两个顶点之间都存在一条路径。图的遍历（Graph Traversal）：一种访问图中所有顶点的方法，常见的遍历方法包括深度优先搜索和广度优先搜索。邻接表（Adjacency List）：一种用于表示无向图的邻接关系的数组结构，每个顶点对应一个链表，链表中的节点表示与该顶点相连的边。邻接矩阵（Adjacency Matrix）：一种用于表示无向图的邻接关系的二维数组结构，数组中的元素表示顶点之间是否存在边。路径（Path）：无向图中由一系列边依次连接的顶点序列。循环（Cycle）：无向图中一条起点和终点相同的路径。树（Tree）：一种无向图，其中任意两个顶点之间只有一条路径，且不存在循环。森林（Forest）：由多个树组成的无向图。图的直径（Graph Diameter）：无向图中任意两个顶点之间的最长路径的长度。图的半径（Graph Radius）：无向图中距离中心顶点最远的顶点与中心顶点之间的距离。图的中心（Graph Center）：无向图中距离其他顶点最近的顶点。图的密度（Graph Density）：无向图中边的数量与可能的最大边数量的比值。完全图（Complete Graph）：一种无向图，其中任意两个顶点之间都存在一条边。二分图（Bipartite Graph）：一种无向图，其中顶点可以分为两个不相交的子集，使得子集内的顶点之间没有边，而子集之间的顶点之间有边。匹配（Matching）：无向图中一系列互不相交的边，使得每个顶点恰好属于一条边。最大匹配（Maximum Matching）：无向图中边数最多的匹配。完美匹配（Perfect Matching）：无向图中所有顶点都被匹配的匹配。匈牙利算法（Hungarian Algorithm）：一种用于寻找最大匹配或完美匹配的算法。图的着色（Graph Coloring）：将无向图中的顶点分配给不同的颜色，使得相邻的顶点具有不同的颜色。色数（Chromatic Number）：无向图中最少需要的颜色数量，使得相邻的顶点具有不同的颜色。平面图（Planar Graph）：一种可以在平面上绘制而不产生交叉边的无向图。欧拉路径（Eulerian Path）：一种遍历无向图中所有边恰好一次的路径。欧拉回路（Eulerian Circuit）：一种遍历无向图中所有边恰好一次的回路。强连通分量（Strongly Connected Component）：无向图中的一个子图，其中任意两个顶点之间都存在一条往返路径。拓扑排序（Topological Sort）：一种将无向图中的顶点按照拓扑顺序排序的方法。关键路径（Critical Path）：项目管理中用于确定项目最短完成时间的路径。最短路径（Shortest Path）：无向图中两个顶点之间的最短距离。Dijkstra 算法：一种用于寻找最短路径的算法。Floyd-Warshall 算法：一种用于寻找所有顶点之间最短路径的算法。这些术语是无向图的基本概念，了解它们对于理解和分析无向图的性质和算法非常重要。

十、写出4阶有向完全图和4阶无向完全图的邻接矩阵？

4阶有向完全图的邻接矩阵 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 4阶无向完全图的邻接矩阵 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 两者一样