下载文档原格式
离散数学图的连通性判定算法离散数学中，图是研究事物之间关系的一种可视化表示方式。
而图的连通性判定算法是判断图中各个节点之间是否存在连通路径的一种方法。
本文将介绍常用的离散数学图的连通性判定算法，并对其进行详细说明。
一、深度优先搜索算法深度优先搜索算法（Depth First Search，简称DFS）是一种用于遍历图或树的搜索算法。
在图的连通性判定中，DFS算法可以用于检测一个图是否是连通图。
算法步骤如下：1. 选择一个起始节点作为当前节点，并将其标记为已访问；2. 从当前节点出发，沿着一条未访问的边到达相邻节点；3. 若相邻节点未被访问，则将其标记为已访问，并将其设为当前节点，重复步骤2；4. 若当前节点的所有相邻节点都已被访问，则回溯到上一个节点，重复步骤3，直到回溯到起始节点。
通过DFS算法，我们可以遍历图中的所有节点，并判断图的连通性。
若在遍历过程中，所有节点都被访问到，则图是连通的；否则，图是非连通的。
二、广度优先搜索算法广度优先搜索算法（Breadth First Search，简称BFS）也是一种用于遍历图或树的搜索算法。
在图的连通性判定中，BFS算法同样可以用于判断图是否为连通图。
算法步骤如下：1. 选择一个起始节点作为当前节点，并将其标记为已访问；2. 将当前节点的所有相邻节点加入一个队列；3. 从队列中取出一个节点作为当前节点，并将其标记为已访问；4. 将当前节点的所有未访问的相邻节点加入队列；5. 重复步骤3和步骤4，直到队列为空。
通过BFS算法，我们可以逐层遍历图中的节点，并判断图的连通性。
若在遍历过程中，所有节点都被访问到，则图是连通的；否则，图是非连通的。
三、并查集算法并查集算法（Disjoint Set Union，简称DSU）是一种用于处理一些不相交集合的数据结构。
在图的连通性判定中，并查集算法可以用于判断图的连通性。
算法步骤如下：1. 初始化并查集，将每个节点设为一个单独的集合；2. 对于图中的每一条边(u, v)，判断节点u和节点v是否属于同一个集合；3. 若节点u和节点v属于不同的集合，则将它们合并为一个集合；4. 重复步骤2和步骤3，直到遍历完所有边。
计算机学科专业基础综合数据结构-图(二)(总分100,考试时间90分钟)一、单项选择题(下列每题给出的4个选项中，只有一个最符合试题要求)1. 具有6个顶点的无向图至少应有______条边才能确保是一个连通图。
A.5 B.6 C.7 D.82. 设G是一个非连通无向图，有15条边，则该图至少有______个顶点。
A.5 B.6 C.7 D.83. 下列关于无向连通图特性的叙述中，正确的是______。
①所有顶点的度之和为偶数②边数大于顶点个数减1③至少有一个顶点的度为1A.只有① B.只有② C.①和② D.①和③4. 对于具有n(n＞1)个顶点的强连通图，其有向边的条数至少是______。
A.n+1B.nC.n-1D.n-25. 下列有关图的说法中正确的是______。
A.在图结构中，顶点不可以没有任何前驱和后继 B.具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和6. 对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是______，矩阵中非零元素的个数是2e。
A.n B.(n-1)2 C.n-1 D.n27. 无向图的邻接矩阵是一个______。
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵8. 从邻接矩阵可知，该图共有______个顶点。
如果是有向图，该图共有4条有向边；如果是无向图，则共有2条边。
A.9 B.3 C.6 D.1 E.5 F.4 G.2 H.09. 下列说法中正确的是______。
A.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C.一个图的邻接矩阵表示不唯一，邻接表表示唯一 D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一10. 用邻接表存储图所用的空间大小______。
A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的二次方有关11. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的______，广度优先搜索算法类似于二叉树的层次序遍历。
《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。
A.效率B.复杂度C.数据元素之间的关系D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。
A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。
A.p->next=p->next->nextB.p->next=p->nextC.p=p->next;p->next=p->next->nextD.p=p->next->next6.带头结点的单链表head为空的判定条件是（）。
A.head==NULLB.head->next==NULLC.head->next==headD.head!==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。
A.p->head==NULLB.p==NULLC.p->next==headD.p==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
9.队列操作的原则是（）。
A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。
自测题（6-10章）一、填空题1、二叉树第i(i>=1)层上至多有______个结点，深度为k(k>=1)的二叉树至多有______个结点。
2、对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
3、满二叉树上各层的节点数已达到了二叉树可以容纳的______，满二叉树也是______二叉树，但反之不然。
4、具有n个结点的完全二叉树的深度为______。
5、具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。
6、二叉树有不同的链式存储结构，其中最常用的是________与________。
7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。
8、由________转换成二叉树时，其根结点的右子树总是空的。
9、哈夫曼树是带权路径长度________的树，通常权值较大的结点离根________。
10、有m个叶子结点的哈夫曼树，其结点总数为________。
11、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有________个叶子结点。
12、具有10个顶点的无向图，边的总数最多为________。
13、N个顶点的连通图的生成树含有________条边。
14、无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。
15、一个具有n个顶点的完全无向图的边数为________，一个具有n个顶点的完全有向图的弧数为________。
16、遍历图的基本方法有________优先搜索和________优先搜索两种。
17、在有向图的邻接矩阵上，由第i行可得到第________个结点的________，而由第j列可得到第________个结点的________。
18、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素________比较大小。
题目：如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。
选项A：一棵树选项B：有回路选项C：连通图选项D：完全图答案：连通图题目：下列有关图遍历的说法不正确的是（）。
选项A：非连通图不能用深度优先搜索法选项B：图的遍历要求每一顶点仅被访问一次选项C：连通图的深度优先搜索是一个递归过程选项D：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征答案：非连通图不能用深度优先搜索法题目：无向图的邻接矩阵是一个（）。
选项A：对称矩阵选项B：对角矩阵选项C：上三角矩阵选项D：零矩阵答案：对称矩阵题目：图的深度优先遍历算法类似于二叉树的（）遍历。
选项A：后序选项B：先序选项C：层次选项D：中序答案：先序题目：已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
/pluginfile.php/67710/question/questiontext/2988635/7/108770/01 .png选项A：V1V2V4V8V3V5V6V7选项B：V1V2V4V8V5V3V6V7选项C：V1V2V4V5V8V3V6V7选项D：V1V3V6V7V2V4V5V8答案：V1V2V4V8V5V3V6V7题目：在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。
选项A：1选项B：1/2选项C：4选项D：2答案：2题目：邻接表是图的一种（）。
选项A：顺序存储结构选项B：索引存储结构选项C：散列存储结构选项D：链式存储结构答案：链式存储结构题目：已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
/pluginfile.php/67710/question/questiontext/2988635/8/108771/02 .png选项A：aebcfd选项B：abcefd选项C：acfdeb选项D：abcedf答案：abcefd题目：已知如图3所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
算法设计：深度优先遍历和广度优先遍历实现深度优先遍历过程1、图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
它们对无向图和有向图均适用。
注意：以下假定遍历过程中访问顶点的操作是简单地输出顶点。
2、布尔向量visited[0．．n-1]的设置图中任一顶点都可能和其它顶点相邻接。
在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。
为了避免重复访问同一个顶点，必须记住每个已访问的顶点。
为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。
--------------------------深度优先遍历(Depth-First Traversal)1．图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。
在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。
若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。
采用的搜索方法的特点是尽可能先对纵深方向进行搜索。
这种搜索方法称为深度优先搜索(Depth-First Search)。
相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
2、深度优先搜索的过程设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。
若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。
广度优先搜索算法利用广度优先搜索解决的最短路径问题广度优先搜索算法（BFS）是一种图算法，用于解决最短路径问题。
其主要思想是从起始节点开始，不断扩展和访问其邻居节点，直到找到目标节点或者遍历完所有节点。
BFS算法可以用于解决许多问题，其中包括最短路径问题。
下面将介绍广度优先搜索算法的基本原理及其应用于最短路径问题的具体步骤。
同时，通过示例来进一步说明算法的执行过程和实际应用。
一、广度优先搜索算法原理广度优先搜索算法是一种层次遍历的算法，它从起始节点开始，按照距离递增的顺序，依次遍历节点。
在遍历的过程中，任意两个节点之间的距离不超过2，因此，BFS算法可以用于求解最短路径问题。
二、广度优先搜索算法的具体步骤1. 创建一个队列，用于存储待访问的节点。
2. 将起始节点放入队列中，并将其标记为已访问。
3. 当队列不为空时，执行以下步骤：a. 从队列中取出一个节点。
b. 访问该节点，并根据需求进行相应操作。
c. 将该节点的所有未访问过的邻居节点放入队列中，并将它们标记为已访问。
d. 重复步骤a~c，直到队列为空。
4. 完成以上步骤后，如果找到目标节点，则算法终止；否则，表示目标节点不可达。
三、广度优先搜索算法在最短路径问题中的应用最短路径问题是指从一个节点到另一个节点的最短路径，其长度可以通过广度优先搜索算法得到。
考虑以下示例：假设有一个迷宫，迷宫由多个格子组成，其中一些格子是墙壁，不可通过，而其他格子可以自由通行。
任务是找到从起始格子到达目标格子的最短路径。
利用广度优先搜索算法解决最短路径问题的具体步骤如下：1. 创建一个队列，并将起始格子放入队列中。
2. 将起始格子标记为已访问。
3. 当队列不为空时，执行以下步骤：a. 从队列中取出一个格子。
b. 如果该格子是目标格子，则算法终止。
c. 否则，获取该格子的邻居格子，并将未访问过的邻居格子放入队列中。
d. 将该格子的邻居格子标记为已访问。
e. 重复步骤a~d，直到队列为空。
【算法】⼴度优先算法和深度优先算法⼴度（BFS）和深度（DFS）优先算法这俩个算法是图论⾥⾯⾮常重要的两个遍历的⽅法。
下⾯⼀个例⼦迷宫计算，如下图解释：所谓⼴度，就是⼀层⼀层的，向下遍历，层层堵截，看下⾯这幅图，我们如果要是⼴度优先遍历的话，我们的结果是V1 V2 V3 V4 V5 V6 V7 V8。
⼴度优先搜索的思想： ①访问顶点vi ； ②访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ； ③依次从这些邻接点（在步骤②中访问的顶点）出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 说明： 为实现③，需要保存在步骤②中访问的顶点，⽽且访问这些顶点的邻接点的顺序为：先保存的顶点，其邻接点先被访问。
这⾥我们就想到了⽤标准模板库中的queue队列来实现这种先进现出的服务。
步骤： 1.将V1加⼊队列，取出V1，并标记为true(即已经访问)，将其邻接点加进⼊队列，则 <—[V2 V3] 2.取出V2，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[V3 V4 V5]3.取出V3，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[V4 V5 V6 V7]4.取出V4，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[V5 V6 V7 V8]5.取出V5，并标记为true(即已经访问)，因为其邻接点已经加⼊队列，则 <—[V6 V7 V8]6.取出V6，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[V7 V8]7.取出V7，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[V8]8.取出V8，并标记为true(即已经访问)，将其未访问过的邻接点加进⼊队列，则 <—[]区别：深度优先遍历：对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个结点只能访问⼀次。
广度优先搜索详解及应用场景广度优先搜索（BFS）是一种图遍历算法，用于在图或树中遍历节点。
它从根节点开始，并按照离根节点的距离逐层访问节点，直到找到目标节点或遍历完整个图。
BFS算法采用队列数据结构来实现，它按照先进先出（FIFO）的原则遍历节点。
下面我们将详细介绍BFS的执行步骤，并探讨其应用场景。
1. 步骤：a. 创建一个空队列，并将根节点入队。
b. 从队列中取出第一个节点，并访问该节点。
c. 将该节点的所有未访问过的邻居节点入队。
d. 标记当前节点为已访问。
e. 重复步骤b-d，直到队列为空或者找到目标节点。
2. 应用场景：a. 最短路径：BFS可以用于寻找两个节点之间的最短路径。
在无权图中，BFS会按照距离逐层遍历，当找到目标节点时，路径的层数即为最短路径长度。
b. 连通性检测：BFS可以判断图中两个节点是否连通。
通过遍历所有节点，如果能够访问到目标节点，则说明两个节点是连通的。
c. 图的遍历：BFS可以用于遍历整个图的节点。
通过BFS算法，可以按照节点的层次顺序进行遍历，并获取图的结构信息。
d. 二叉树的层次遍历：BFS可用于二叉树的层次遍历，从上到下逐层访问二叉树的节点。
总结：广度优先搜索是一种有效的图遍历算法，通过队列实现节点的层次遍历。
它可以在图中寻找最短路径，判断节点的连通性，以及进行图的遍历和二叉树的层次遍历。
对于涉及层次关系和连通性的问题，BFS 是一种重要的算法工具。
通过掌握BFS算法的原理和应用场景，我们可以更好地应用它来解决实际问题。
在实际开发中，我们可以将BFS应用于推荐系统、社交网络分析、路径规划等领域，进一步提升算法的效率和准确性。
总之，广度优先搜索作为一种重要的图遍历算法，具有广泛的应用前景。
在日常的学习和实践中，我们应该深入理解BFS的原理，并善于运用它解决各种实际问题。
深度优先遍历算法和广度优先遍历算法实验小结一、引言在计算机科学领域，图的遍历是一种基本的算法操作。
深度优先遍历算法（Depth First Search，DFS）和广度优先遍历算法（Breadth First Search，BFS）是两种常用的图遍历算法。
它们在解决图的连通性和可达性等问题上具有重要的应用价值。
本文将从理论基础、算法原理、实验设计和实验结果等方面对深度优先遍历算法和广度优先遍历算法进行实验小结。
二、深度优先遍历算法深度优先遍历算法是一种用于遍历或搜索树或图的算法。
该算法从图的某个顶点开始遍历，沿着一条路径一直向前直到不能再继续前进为止，然后退回到上一个节点，尝试下一个节点，直到遍历完整个图。
深度优先遍历算法通常使用栈来实现。
以下是深度优先遍历算法的伪代码：1. 创建一个栈并将起始节点压入栈中2. 将起始节点标记为已访问3. 当栈不为空时，执行以下步骤：a. 弹出栈顶节点，并访问该节点b. 将该节点尚未访问的邻居节点压入栈中，并标记为已访问4. 重复步骤3，直到栈为空三、广度优先遍历算法广度优先遍历算法是一种用于遍历或搜索树或图的算法。
该算法从图的某个顶点开始遍历，先访问起始节点的所有相邻节点，然后再依次访问这些相邻节点的相邻节点，依次类推，直到遍历完整个图。
广度优先遍历算法通常使用队列来实现。
以下是广度优先遍历算法的伪代码：1. 创建一个队列并将起始节点入队2. 将起始节点标记为已访问3. 当队列不为空时，执行以下步骤：a. 出队一个节点，并访问该节点b. 将该节点尚未访问的邻居节点入队，并标记为已访问4. 重复步骤3，直到队列为空四、实验设计本次实验旨在通过编程实现深度优先遍历算法和广度优先遍历算法，并通过对比它们在不同图结构下的遍历效果，验证其算法的正确性和有效性。
具体实验设计如下：1. 实验工具：使用Python编程语言实现深度优先遍历算法和广度优先遍历算法2. 实验数据：设计多组图结构数据，包括树、稠密图、稀疏图等3. 实验环境：在相同的硬件环境下运行实验程序，确保实验结果的可比性4. 实验步骤：编写程序实现深度优先遍历算法和广度优先遍历算法，进行多次实验并记录实验结果5. 实验指标：记录每种算法的遍历路径、遍历时间和空间复杂度等指标，进行对比分析五、实验结果在不同图结构下，经过多次实验，分别记录了深度优先遍历算法和广度优先遍历算法的实验结果。
深度优先算法与⼴度优先算法深度优先搜索和⼴度优先搜索，都是图形搜索算法，它两相似，⼜却不同，在应⽤上也被⽤到不同的地⽅。
这⾥拿⼀起讨论，⽅便⽐较。
⼀、深度优先搜索深度优先搜索属于图算法的⼀种，是⼀个针对图和树的遍历算法，英⽂缩写为DFS即Depth First Search。
深度优先搜索是图论中的经典算法，利⽤深度优先搜索算法可以产⽣⽬标图的相应拓扑排序表，利⽤拓扑排序表可以⽅便的解决很多相关的图论问题，如最⼤路径问题等等。
⼀般⽤堆数据结构来辅助实现DFS算法。
其过程简要来说是对每⼀个可能的分⽀路径深⼊到不能再深⼊为⽌，⽽且每个节点只能访问⼀次。
基本步奏（1）对于下⾯的树⽽⾔，DFS⽅法⾸先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
（2）从stack中访问栈顶的点；（3）找出与此点邻接的且尚未遍历的点，进⾏标记，然后放⼊stack中，依次进⾏；（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进⾏；（5）直到遍历完整个树，stack⾥的元素都将弹出，最后栈为空，DFS遍历完成。
⼆、⼴度优先搜索⼴度优先搜索（也称宽度优先搜索，缩写BFS，以下采⽤⼴度来描述）是连通图的⼀种遍历算法这⼀算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最⼩⽣成树算法都采⽤了和宽度优先搜索类似的思想。
其别名⼜叫BFS，属于⼀种盲⽬搜寻法，⽬的是系统地展开并检查图中的所有节点，以找寻结果。
换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为⽌。
基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。
如果所有节点均被访问，则算法中⽌。
⼀般⽤队列数据结构来辅助实现BFS算法。
基本步奏（1）给出⼀连通图，如图，初始化全是⽩⾊（未访问）；（2）搜索起点V1（灰⾊）；（3）已搜索V1（⿊⾊），即将搜索V2，V3，V4（标灰）；（4）对V2，V3，V4重复以上操作；（5）直到终点V7被染灰，终⽌；（6）最短路径为V1，V4，V7.作者：安然若知链接：https:///p/bff70b786bb6来源：简书简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
//算法6.7广度优先搜索遍历连通图#include <iostream>using namespace std;#define MVNum 100 //最大顶点数#define MAXQSIZE 100//最大队列长度typedef char VerTexType; //假设顶点的数据类型为字符型typedef int ArcType; //假设边的权值类型为整型bool visited[MVNum]; //访问标志数组，其初值为"false"//-----图的邻接矩阵存储表示-----typedef struct{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum,arcnum; //图的当前点数和边数}Graph;//----队列的定义及操作--------typedef struct{ArcType *base;//初始化的动态分配存储空间int front;//头指针，若队列不空，指向队头元素int rear;//尾指针，若队列不空，指向队尾元素的下一个位置}sqQueue;void InitQueue(sqQueue &Q){//构造一个空队列QQ.base = new ArcType[MAXQSIZE];if(!Q.base) exit(1);//存储分配失败Q.front = Q.rear = 0;}//InitQueuevoid EnQueue(sqQueue &Q, ArcType e){//插入元素e为Q的新的队尾元素if((Q.rear + 1) % MAXQSIZE == Q.front)return;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;}//EnQueuebool QueueEmpty(sqQueue Q){//判断是否为空队if(Q.rear == Q.front)return true;return false;}//QueueEmptyvoid DeQueue(sqQueue &Q, ArcType &u){//队头元素出队并置为uu = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;}//DeQueue//--------------------------------------------------int LocateVex(Graph G , VerTexType v){//确定点v在G中的位置for(int i = 0; i < G.vexnum; ++i)if(G.vexs[i] == v)return i;return -1;}//LocateVexvoid CreateUDN(Graph &G){//采用邻接矩阵表示法，创建无向网Gint i , j , k;cout <<"请输入总顶点数，总边数，以空格隔开:";cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数cout << endl;cout << "输入点的名称，如a" << endl;for(i = 0; i < G.vexnum; ++i){cout << "请输入第" << (i+1) << "个点的名称:";cin >> G.vexs[i]; //依次输入点的信息}cout << endl;for(i = 0; i < G.vexnum; ++i) //初始化邻接矩阵，边的权值均置为极大值MaxIntfor(j = 0; j < G.vexnum; ++j)G.arcs[i][j] = 0;cout << "输入边依附的顶点，如a b" << endl;for(k = 0; k < G.arcnum;++k){//构造邻接矩阵VerTexType v1 , v2;cout << "请输入第" << (k + 1) << "条边依附的顶点:";cin >> v1 >> v2;//输入一条边依附的顶点i = LocateVex(G, v1); j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标G.arcs[i][j] = 1;//边<v1, v2>的权值置为wG.arcs[j][i] = G.arcs[i][j];//置<v1, v2>的对称边<v2, v1>的权值为w}//for}//CreateUDNint FirstAdjVex(Graph G , int v){//返回v的第一个邻接点int i;for(i = 0 ; i < G.vexnum ; ++i){if(G.arcs[v][i] == 1 && visited[i] == false)return i;}return -1;}//FirstAdjVexint NextAdjVex(Graph G , int u , int w){//返回v相对于w的下一个邻接点int i;for(i = w ; i < G.vexnum ; ++i){if(G.arcs[u][i] == 1 && visited[i] == false)return i;}return -1;}//NextAdjVexvoid DFS(Graph G, int v){//从第v个顶点出发递归地深度优先遍历图Gcout << G.vexs[v] << " "; visited[v] = true; //访问第v个顶点，并置访问标志数组相应分量值为trueint w;for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))//依次检查v的所有邻接点w ，FirstAdjVex(G, v)表示v的第一个邻接点//NextAdjVex(G, v, w)表示v相对于w的下一个邻接点，w≥0表示存在邻接点if(!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w递归调用DFS}//DFSvoid BFS (Graph G, int v){//按广度优先非递归遍历连通图GsqQueue Q;ArcType u;ArcType w;cout << G.vexs[v] << " "; visited[v] = true; //访问第v个顶点，并置访问标志数组相应分量值为trueInitQueue(Q);//辅助队列Q初始化，置空EnQueue(Q, v);//v进队while(!QueueEmpty(Q)){ //队列非空DeQueue(Q, u);//队头元素出队并置为ufor(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){//依次检查u的所有邻接点w ，FirstAdjVex(G, u)表示u的第一个邻接点//NextAdjVex(G, u, w)表示u相对于w的下一个邻接点，w≥0表示存在邻接点if(!visited[w]){//w为u的尚未访问的邻接顶点cout << G.vexs[w] << " "; visited[w] = true;//访问w，并置访问标志数组相应分量值为trueEnQueue(Q, w);//w进队}//if}//for}//while}//BFSint main(){printf("\n-----------------------测试-----------------------\n\n");Graph G;CreateUDN(G);cout << endl;cout << "无向连通图G创建完成！" << endl << endl;cout << "请输入遍历连通图的起始点：";VerTexType c;cin >> c;int i;for(i = 0 ; i < G.vexnum ; ++i){if(c == G.vexs[i])break;}cout << endl;while(i >= G.vexnum){cout << "该点不存在，请重新输入！" << endl;cout << "请输入遍历连通图的起始点：";cin >> c;for(i = 0 ; i < G.vexnum ; ++i){if(c == G.vexs[i])break;}}printf("\n-----------------------测试-----------------------\n\n");cout << "深度优先搜索遍历连通图结果：" << endl;DFS(G , i);for(int j = 0;j < MVNum;j++){visited[j] = false;}printf("\n-----------------------测试-----------------------\n\n");cout << "广度优先搜索遍历连通图结果：" << endl;BFS(G , i);cout <<endl;return 0;}//main效果图：。
