图论详细讲解

Dijkstra算法原理详细讲解
Dijkstra算法是图论中的一种贪心算法，用于求解最短路径问题。

该算法的贪心策略是：每次选择当前距离起点最近的节点作为中间节点，并更新起点到其它节点的距离。

通过不断选择距离起点最近的节点，并逐步更新起点到各个节点的距离，最终得到起点到终点的最短路径。

Dijkstra算法的具体实现包括以下几个步骤：
1. 初始化：将起点到各个节点的距离记为无穷大或者一个较大的值，将起点到自己的距离记为0。

2. 选择当前距离起点最近的节点作为中间节点。

这个过程可以通过维护一个距离起点最近的节点集合来实现，初始时集合中只包含起点。

3. 更新起点到与中间节点相邻的节点的距离，即对于每个与中间节点相邻的节点，如果从起点到中间节点的距离加上中间节点到该节点的距离小于起点到该节点的距离，则更新起点到该节点的距离为从起点到中间节点的距离加上中间节点到该节点的距离。

4. 重复步骤2和步骤3，直到起点到终点的距离不再更新。

5. 最终得到起点到终点的最短路径。

Dijkstra算法的时间复杂度为O(N^2)，其中N为节点的数目。

如果使用优先队列来维护距离起点最近的节点集合，则算法的时间复杂度可以降为O(NlogN)，但是实际应用中优先队列的实现可能较为复杂。

Dijkstra算法可以用于有向图和无向图，但是不能处理带有负权边的图。

如果图中存在负权边，则可以使用Bellman-Ford算法来求解最短路径。

高中数学图论的实际应用与教学探讨在高中数学的广袤领域中，图论宛如一颗璀璨的明珠，虽然它并非高中数学课程的核心部分，但其在实际生活中的应用广泛，且对于培养学生的逻辑思维和解决问题的能力具有重要意义。

本文将深入探讨高中数学图论的实际应用，并对其教学方法进行分析。

一、图论的基本概念图论是研究图的性质和应用的数学分支。

所谓“图”，并不是我们日常所理解的图像或图画，而是由一些顶点（节点）和连接这些顶点的边所组成的结构。

例如，一个城市的交通网络可以用图来表示，顶点代表城市中的各个地点，边代表道路。

在图论中，有许多重要的概念，如顶点的度（与该顶点相连的边的数量）、路径（从一个顶点到另一个顶点经过的边的序列）、回路（起点和终点相同的路径）、连通图（任意两个顶点之间都存在路径）等。

二、图论在实际生活中的应用1、交通规划城市的交通规划是图论应用的一个重要领域。

通过将城市道路网络抽象为图，可以分析交通流量，确定关键的道路节点和拥堵路段，从而优化交通信号灯设置、规划新的道路建设等，以提高交通效率，减少拥堵。

2、网络通信在计算机网络中，图论用于描述网络拓扑结构。

通过分析网络中的节点和连接关系，可以优化数据传输路径，提高网络的可靠性和性能。

3、物流配送物流企业在规划货物配送路线时，可以利用图论来找到最短路径，降低运输成本，提高配送效率。

例如，快递员在派送多个地点的包裹时，通过图论算法可以找到最优的派送顺序。

4、任务分配在项目管理中，将各项任务视为顶点，任务之间的依赖关系视为边，可以使用图论来合理安排任务的执行顺序，确保项目按时完成。

5、电路设计电子电路的设计中也会用到图论。

电路中的元件可以看作顶点，元件之间的连接看作边，通过分析电路图的拓扑结构，可以优化电路设计，提高电路的性能和可靠性。

三、高中数学图论教学的重要性1、培养逻辑思维能力图论问题的解决需要学生进行逻辑推理和分析，通过构建图、寻找路径、判断连通性等操作，锻炼学生的思维严谨性和逻辑性。

图论综述一、简介图论是数学的一个分支。

它以图为研究对象。

图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。

集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。

通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。

关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。

目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。

图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。

二、基本内容2.1 图的基本概念本章首先介绍了图的一些基本性质和一些不同模型的图，包括偶图，完全图和补图，引入了定点度的来描述图的性质。

其次介绍了子图的相关概念，介绍了图的一些基本运算规则，对图的路和连通性进行了阐释。

紧接着讲解了最短路算法，定义设G为边赋权图。

u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。

图的代数表示，包括图的邻接矩阵和图的关联矩阵。

最后对极图理论进行了简介，主要介绍了极值图论中的一个经典结论——托兰定理。

2.2 树本章主要介绍了树的概念与性质，阐述了生成树与最小生成树的基本概念与一些常用结论与定理。

树是不含圈的无圈图，也是连通的无圈图。

树是图论中应用最为广泛的一类图。

在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。

离散数学中的图论着色算法-教案一、引言1.1图论的发展历程1.1.118世纪欧拉解决哥尼斯堡七桥问题，奠定图论基础。

1.1.219世纪图论在数学和物理学领域得到发展。

1.1.320世纪图论在计算机科学中扮演重要角色。

1.1.4当前图论研究涉及网络科学、社会网络等多个领域。

1.2图论的基本概念1.2.1图由节点和边组成，用于表示物件与物件之间的关系。

1.2.2节点代表研究对象，边代表节点间的联系。

1.2.3图分为有向图和无向图，反映关系的方向性。

1.2.4图的度、路径、环等是图论中的基本术语。

1.3图论在现实中的应用1.3.1社交网络分析，如Facebook的社交图谱。

1.3.2电信网络设计，如电话网络的布局。

1.3.3交通运输规划，如航班路线的优化。

1.3.4计算机网络设计，如互联网的结构优化。

二、知识点讲解2.1图的着色问题2.1.1图的着色是将图中的节点用颜色进行标记，满足相邻节点颜色不同。

2.1.2着色问题分为正常着色和特定着色，如双色着色、列表着色等。

2.1.3着色问题在图论中具有重要地位，与图的性质紧密相关。

2.1.4着色问题广泛应用于地图着色、排课表、寄存器分配等领域。

2.2图的着色算法2.2.1Welsh-Powell算法，基于节点度进行着色。

2.2.2DSATUR算法，优先着色度数大且邻接节点着色多的节点。

2.2.3RLF算法，考虑节点邻接矩阵的行、列和节点度。

2.2.4图的着色算法不断发展，如启发式算法、遗传算法等。

2.3图的着色算法的应用2.3.1地图着色，确保相邻区域颜色不同。

2.3.2课程表安排，避免时间冲突。

2.3.3计算机寄存器分配，优化资源利用。

2.3.4光纤通信网络设计，减少信号干扰。

三、教学内容3.1图的着色问题的引入3.1.1通过地图着色实例引入图的着色问题。

3.1.2讲解正常着色和特定着色问题的区别。

3.1.3分析着色问题在现实中的应用场景。

3.1.4引导学生思考着色问题的数学模型。

【转】彻底弄懂最短路径问题（图论）P.S.根据个⼈需要，我删改了不少问题引⼊问题：从某顶点出发，沿图的边到达另⼀顶点所经过的路径中，各边上权值之和最⼩的⼀条路径——最短路径。

解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出⼀篇，其中Floyd算法可以求解任意两点间的最短路径的长度。

笔者认为任意⼀个最短路算法都是基于这样⼀个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若⼲个节点到B。

⼀.Dijkstra算法该算法在《数据结构》课本⾥是以贪⼼的形式讲解的，不过在《运筹学》教材⾥被编排在动态规划章节，建议读者两篇都看看。

(1) 迪杰斯特拉(Dijkstra)算法按路径长度递增次序产⽣最短路径。

先把V分成两组：S：已求出最短路径的顶点的集合V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加⼊到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证）。

(2) 求最短路径步骤1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值，若存在<V0,Vi>，为<V0,Vi>弧上的权值（和SPFA初始化⽅式不同），若不存在<V0,Vi>，为Inf。

2. 从T中选取⼀个其距离值为最⼩的顶点W(贪⼼体现在此处)，加⼊S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作⽤⾄关重要)，对T中顶点的距离值进⾏修改：若加进W作中间顶点，从V0到Vi的距离值⽐不加W的路径要短，则修改此距离值（上⾯两个并列for循环，使⽤最⼩点更新）。

3. 重复上述步骤，直到S中包含所有顶点，即S=V为⽌（说明最外层是除起点外的遍历）。

离散数学中的图论基础知识讲解图论是离散数学中的一个重要分支，研究的是图的性质和图中的关系。

图论在计算机科学、网络科学、运筹学等领域有着广泛的应用。

本文将从图的基本概念、图的表示方法、图的遍历算法以及一些常见的图论问题等方面进行讲解。

一、图的基本概念图是由顶点和边组成的一种数学结构。

顶点表示图中的元素，边表示元素之间的关系。

图可以分为有向图和无向图两种类型。

1. 无向图：无向图中的边没有方向，表示的是两个顶点之间的无序关系。

如果两个顶点之间存在一条边，那么它们之间是相邻的。

无向图可以用一个集合V表示顶点的集合，用一个集合E表示边的集合。

2. 有向图：有向图中的边有方向，表示的是两个顶点之间的有序关系。

如果从顶点A到顶点B存在一条有向边，那么A指向B。

有向图可以用一个集合V表示顶点的集合，用一个集合E表示有向边的集合。

二、图的表示方法图可以用多种方式进行表示，常见的有邻接矩阵和邻接表两种方法。

1. 邻接矩阵：邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否存在边。

如果顶点i和顶点j之间存在边，那么矩阵的第i行第j列的元素为1；否则为0。

邻接矩阵适用于表示稠密图，但对于稀疏图来说，会造成空间浪费。

2. 邻接表：邻接表是一种链表的数据结构，用来表示图中的顶点和边。

每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。

邻接表适用于表示稀疏图，节省了存储空间。

三、图的遍历算法图的遍历是指按照某一规则访问图中的所有顶点。

常见的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

1. 深度优先搜索：深度优先搜索是一种递归的搜索算法。

从某个顶点出发，首先访问该顶点，然后递归地访问与它相邻的未访问过的顶点，直到所有的顶点都被访问过。

2. 广度优先搜索：广度优先搜索是一种迭代的搜索算法。

从某个顶点出发，首先访问该顶点，然后依次访问与它相邻的所有未访问过的顶点，再依次访问与这些顶点相邻的未访问过的顶点，直到所有的顶点都被访问过。

第21讲根树1. 根树2. 根树的周游3. 最优树, Huffman算法4. 最佳前缀码通讯编码Shannon, Hamming, Sudan有噪声信道的可靠通信: 编码信息就是不确定性的消除: 熵(entropy) 比特(bit): b inary i nformation uni t例: {0,1,2,…,7}, log28=3, 编码为000,001,010,…,111000111010101译为0725不等长编码若{0,1,2,…,7}出现频率不一样,则出现频率高的用短码字例: 频率递减: 0,1,2,3,4,5,6,7, 编码为0,1,00,01,10,11,000,001.若收到000111, 不能唯一解码:651, 235, 075,…等.原因: 码字互为前缀,如00是001的前缀最佳前缀码最佳前缀码: 给定信号出现频率, 平均码字长度最短的前缀码平均码字长度: 码字长度乘以频率,求和 例: {0,1,2,3}, 40%, 30%, 20%,10%,编码1: {00,010,011,1},2×40%+3×30%+3×20%+1×10%=2.4编码2: {1,00,010,011},1×40%+2×30%+3×20%+3×10%=1.9最优二叉树带权二叉树: 每个树叶v i 都指定实数权w i带权二叉树的权: W(T)=Σt i=1w i L(v i ), 树叶是v 1,v 2,…,v t , 对应的层数是L(v 1),L(v 2),…, L(v t )最优二叉树: 树叶权为w 1,w 2,…,w t 的所有二叉树中权最小的一个(不唯一) 求最优二叉树的算法: Huffman 算法Huffman 算法输入: 实数w 1,w 2,…,w t , 输出: 树叶权为w 1,w 2,…,w t 的最优二叉树 算法: 1. 选择最小的2个权w 1,w 2, 连接对应的树叶得到权为w 1+w 2的分支点2. 选择w 1+w 2 ,w 3,w 4, …,w t 中最小的2个权, 连接对应顶点得到新的分支点和权3. 同上重复进行, 直到只剩1个权为止Huffman 算法(正确性) 定理14.12(Huffman): 设T’是带权为w 1+w 2,w 3,…,w t 的最优二叉树, 其中w 1≤w 2≤…≤w t , 若把带权为w 1+w 2的树叶作为分支点, 让2个儿子带权分别为w 1,w 2,记所得树为T*, 则T*是带权为w 1,w 2, w 3,…,w t 的最优二叉树.#推广的Huffman 算法: 最优r 叉树. 例14.11总结根树根树的周游最优树, Huffman算法最佳前缀码作业(#17)p256, 习题九, 18, 21 p370, 习题十四, 12今天交作业#14,#15,#16习题讲解(#12)p214, 习题七, 17, 18, 22, 2317. 证法一: 定理13(前提条件是连通) 证明: (1) G是完全图: κ(G)=δ(G)=n-1 (2) G非完全图: δ(G)=n-2, 易证G连通, 由定理13得n-2 = δ(G) ≥κ(G)≥2δ(G)-n+2= 2(n-2)-n+2 = n-2,∴κ(G)=δ(G)=n-2. #证法二: 直接证习题讲解(#12)18. (1) 证法三: 反证法证明: 假设G 不连通, 有s ≥2个连通分支, 则至少有1个连通分支G 1的顶点数n 1≤n/s, G 是简单图, 所以δ(G)≤n 1-1≤n/s-1<n/s ≤n/2,矛盾! #习题讲解(#12)18. (2) 证法一: 利用(1)证明: ∀V’⊆V(G),|V’|<k,令G’=G-V’,δ(G’) ≥δ(G)-(k-1) ≥(n+k-1)/2-(k-1)= (n-(k-1))/2 = n’/2 ⇒G’连通⇒V’非割集⇒κ(G)≥k ⇒G是k-连通图. #习题讲解(#13)p234, 习题八, 2,3,4(更正: G-v 0) 3. (证法1: 删边) 任选2个奇数度顶点, 删除它们之间的简单通路P 1(G 连通, 这样的通路存在), 奇数度顶点减少2个. 在剩下的含奇数度顶点的连通分支中重复上述步骤, 分别得到P 1,P 2,…,P k . 如果还有剩余连通分支,则都是欧拉图, 把相应的欧拉回路合并到上述的简单通路中得到P’1,P’2,…,P’k . 则E(G)=∪k i=1P’i . #习题讲解(#13)p234, 习题八, 2,3,4(更正: G-v0)3. (证法2: 加边) 在k对奇数度顶点之间加k条边, 就没有奇数度顶点了, 得到欧拉图, 在欧拉回路中删除所加的k条边, 最多得到k条的边不重简单通路. 如果得到少于k条的边不重简单通路, 则随意拆断其中一些, 以达到k条. #。

一、无向图:方法1:如果存在回路，则必存在一个子图，是一个环路。

环路中所有顶点的度〉=2。

n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点，则存在环，否则没有环。

n算法分析：由于有m条边，n个顶点。

i)如果m〉=n，则根据图论知识可直接判断存在环路。

（证明:如果没有环路,则该图必然是k棵树 k>=1.根据树的性质,边的数目m = n-k.k〉=1，所以：m<n）ii)如果m〈n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边)操作一次（最多m次）.这两种操作的总数不会超过m+n。

由于m〈n，所以算法复杂度为O（n).注：该方法，算法复杂度不止O（V），首先初始时刻统计所有顶点的度的时候，复杂度为（V + E），即使在后来的循环中E>=V，这样算法的复杂度也只能为O（V + E)。

其次,在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行delete node from list[list［node］]，这里查找的复杂度为list[list［node]]的长度,只有这样才能保证当degree[i]=1时，list［i]里面只有一个点。

这样最差的复杂度就为O（EV)了.方法2:DFS搜索图,图中的边只可能是树边或反向边，一旦发现反向边,则表明存在环。

该算法的复杂度为O(V).方法3：摘自：http：///lzrzhao/archive/2008/03/13/2175787。

aspxPS：此方法于2011—6-12补充假定:图顶点个数为M,边条数为E遍历一遍，判断图分为几部分(假定为P部分，即图有 P 个连通分量）对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1只要有一个满足边数 > 结点数－1原图就有环将P个连通分量的不等式相加，就得到：P1:E1=M1-1P2:E2=M2—1.。

浅谈分层图
浅谈分层图
本篇随笔简单讲解⼀下图论中的分层图问题。

⼀、分层图的概念
分层图，顾名思义就是分很多层的图。

也就是类似⼆维数组，抽象地理解：不再是⼀个单⼀的平⾯图⽽是⼀个⽴体化的东西，不只有长宽，也有了⾃⼰的厚度——即为层数。

⼆、分层图的应⽤
建⽴多层相同或相似的图, 并在图与图之间进⾏连边，可以实现两种性质的图之间的转移。

或是图与图之间有限制的转移。

⽤⼀道例题来理解⼀下：
约翰⼀共有 N N个牧场.由 M M条布满尘埃的⼩径连接。

⼩径可以双向通⾏。

每天早上约翰从牧场 11 出发到牧场 N N去给奶⽜检查⾝体。

通过每条⼩径都需要消耗⼀定的时间。

约翰打算升级其中 K K条⼩径，使之成为⾼速公路。

在⾼速公路上的通⾏⼏乎是瞬间完成的，所以⾼速公路的通⾏时间为 00。

请帮助约翰决定对哪些⼩径进⾏升级，使他每天从 11 号牧场到第 N N号牧场所花的时间最短。

在这道题中，会有⼀些边可以免费，我们考虑DP，但是发现并没有⼀个⽆后效性的转移⽅式。

所以我们只能想其他的⽅式：建分层图。

三、分层图的实现原理
建分层图感性来讲，就是：这种DP不是有后效性么？怎么变成⽆后效性的呢？直接每个状态我都来⼀张图！
假设免费建⽴k条边，所以就可以有k层图表⽰已经免费建⽴了1条边到免费建⽴了k条边。

注意，0层图也就是原图也是要建⽴的。

在连接每两个点的同时，将复制出来的另外k个图上对应的两个点连接起来。

也将i图和j图上的对应的点连接起来。

也就是让这条边权值为零的情况。

所以就可以直接在上⾯跑最短路解决了。

一、无向图：方法1：∙如果存在回路，则必存在一个子图，是一个环路。

环路中所有顶点的度>=2。

∙ n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点，则存在环，否则没有环。

∙ n算法分析：由于有m条边，n个顶点。

i)如果m>=n，则根据图论知识可直接判断存在环路。

（证明：如果没有环路，则该图必然是k棵树k>=1。

根据树的性质，边的数目m = n-k。

k>=1，所以：m<n）ii)如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。

这两种操作的总数不会超过m+n。

由于m<n，所以算法复杂度为O(n)。

∙注：该方法，算法复杂度不止O(V)，首先初始时刻统计所有顶点的度的时候，复杂度为(V + E)，即使在后来的循环中E>=V，这样算法的复杂度也只能为O(V + E)。

其次，在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行delete node from list[list[node]]，这里查找的复杂度为list[list[node]]的长度，只有这样才能保证当degree[i]=1时，list[i]里面只有一个点。

这样最差的复杂度就为O(EV)了。

方法2：DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。

该算法的复杂度为O(V)。

方法3：摘自：/lzrzhao/archive/2008/03/13/2175787.aspx PS：此方法于2011-6-12补充假定：图顶点个数为M，边条数为E遍历一遍，判断图分为几部分（假定为P部分，即图有P 个连通分量）对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1只要有一个满足边数> 结点数－1原图就有环将P个连通分量的不等式相加，就得到：P1:E1=M1-1P2:E2=M2-1...PN:EN>MN-1所有边数(E) > 所有结点数(M) - 连通分量个数(P)即： E + P > M 所以只要判断结果 E + P > M 就表示原图有环，否则无环.实例代码如下：1.#include<iostream>2.#include<malloc.h>ing namespace std;4.#define maxNum 100 //定义邻接举证的最大定点数5.int visited[maxNum];//通过visited数组来标记这个顶点是否被访问过，0表示未被访问，1表示被访问6.int DFS_Count;//连通部件个数，用于测试无向图是否连通，DFS_Count=1表示只有一个连通部件，所以整个无向图是连通的7.int pre[maxNum];8.int post[maxNum];9.int point;//pre和post的值10.11.//图的邻接矩阵表示结构12.typedef struct13.{14.char v[maxNum];//图的顶点信息15.int e[maxNum][maxNum];//图的顶点信息16.int vNum;//顶点个数17.int eNum;//边的个数18.}graph;19.void createGraph(graph *g);//创建图g20.void DFS(graph *g);//深度优先遍历图g21.void dfs(graph *g,int i);//从顶点i开始深度优先遍历与其相邻的点22.void dfs(graph *g,int i)23.{24.//cout<<"顶点"<<g->v[i]<<"已经被访问"<<endl;25. cout<<"顶点"<<i<<"已经被访问"<<endl;26. visited[i]=1;//标记顶点i被访问27. pre[i]=++point;28.for(int j=1;j<=g->vNum;j++)29. {30.if(g->e[i][j]!=0&&visited[j]==0)31. dfs(g,j);32. }33. post[i]=++point;34.}35.36.void DFS(graph *g)37.{38.int i;39.//初始化visited数组，表示一开始所有顶点都未被访问过40.for(i=1;i<=g->vNum;i++)41. {42. visited[i]=0;43. pre[i]=0;44. post[i]=0;45. }46.//初始化pre和post47. point=0;48.//初始化连通部件数为049. DFS_Count=0;50.//深度优先搜索51.for(i=1;i<=g->vNum;i++)52. {53.if(visited[i]==0)//如果这个顶点为被访问过，则从i顶点出发进行深度优先遍历54. {55. DFS_Count++;//统计调用void dfs(graph *g,int i);的次数56. dfs(g,i);57. }58. }59.}60.void createGraph(graph *g)//创建图g61.{62. cout<<"正在创建无向图..."<<endl;63. cout<<"请输入顶点个数vNum:";64. cin>>g->vNum;65. cout<<"请输入边的个数eNum:";66. cin>>g->eNum;67.int i,j;68.//输入顶点信息69.//cout<<"请输入顶点信息："<<endl;70.//for(i=0;i<g->vNum;i++)71.// cin>>g->v[i];72.//初始画图g73.for(i=1;i<=g->vNum;i++)74.for(j=1;j<=g->vNum;j++)75. g->e[i][j]=0;76.//输入边的情况77. cout<<"请输入边的头和尾"<<endl;78.for(int k=0;k<g->eNum;k++)79. {80. cin>>i>>j;81. g->e[i][j]=1;82. g->e[j][i]=1;//无向图对称83. }84.}85.int main()86.{87. graph *g;88. g=(graph*)malloc(sizeof(graph));89. createGraph(g);//创建图g90. DFS(g);//深度优先遍历91.//连通部件数，用于判断是否连通图92. cout<<"连通部件数量：";93. cout<<DFS_Count<<endl;94.if(DFS_Count==1)95. cout<<"图g是连通图"<<endl;96.else if(DFS_Count>1)97. cout<<"图g不是连通图"<<endl;98.//各顶点的pre和post值99.for(int i=1;i<=g->vNum;i++)100. cout<<"顶点"<<i<<"的pre和post分别为："<<pre[i]<<" "<<post[i]<<endl;101.//cout<<endl;102.//判断无向图中是否有环103.if(g->eNum+DFS_Count>g->vNum)104. cout<<"图g中存在环"<<endl;105.else106. cout<<"图g中不存在环"<<endl;107.int k;108. cin>>k;109.return 0;110.}111./*112.输入：113.正在创建无向图...114.请输入顶点个数vNum:10115.请输入边的个数eNum:9116.请输入边的头和尾117.1 2118.1 4119.2 5120.2 6121.4 7122.5 9123.6 3124.7 8125.9 10126.*/注意：有向图不能使用此方法。