下载文档原格式
离散数学图的连通性判定算法离散数学中，图是研究事物之间关系的一种可视化表示方式。
而图的连通性判定算法是判断图中各个节点之间是否存在连通路径的一种方法。
本文将介绍常用的离散数学图的连通性判定算法，并对其进行详细说明。
一、深度优先搜索算法深度优先搜索算法（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出发的未检测过的边。
//算法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效果图：。
