采用邻接表存储结构-编写一个求无向图的连通分量个数的算法

323.⽆向图中连通分量的数⽬题⽬：给定编号从 0 到 n-1 的 n 个节点和⼀个⽆向边列表（每条边都是⼀对节点），请编写⼀个函数来计算⽆向图中连通分量的数⽬。

⽰例 1:输⼊: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]0 3| |1 ---2 4输出: 2⽰例 2:输⼊: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]0 4| |1 ---2 --- 3输出: 1注意:你可以假设在 edges 中不会出现重复的边。

⽽且由于所以的边都是⽆向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

解答：DFS：维持⼀个未遍历过的节点，每次取⼀个为遍历过的节点，然后从它开始dfs，遍历所有可达的节点，也就是找到了⼀个连通分量。

class Solution {public:int countComponents(int n, vector<vector<int>>& edges) {if(n<=0){return0;}unordered_map<int,unordered_set<int> > edge_map;for(auto& edge:edges){edge_map[edge[0]].insert(edge[1]);edge_map[edge[1]].insert(edge[0]);}unordered_set<int> unvisited;for(int i=0;i<n;++i){unvisited.insert(i);}int res=0;while(unvisited.size()>0){// for(int x:unvisited){// cout<<x<<" ";// }cout<<endl;auto cur=unvisited.begin();dfs(*cur,unvisited,edge_map);++res;}return res;}void dfs(int cur,unordered_set<int>& unvisited,unordered_map<int,unordered_set<int> >& edge_map){unvisited.erase(cur);for(const int& neighbour:edge_map[cur]){if(unvisited.count(neighbour)){dfs(neighbour,unvisited,edge_map);}}}};并差集：（开始没想到，确实是个好⽅法）class Solution {public:vector<int> father;int Father(int i){if(father[i]!=i){return father[i]=Father(father[i]);}return i;}void merge(int x,int y){int px=Father(x),py=Father(y);father[px]=py;}int countComponents(int n, vector<vector<int>>& edges) {father.resize(n);for(int i=0;i<n;++i){father[i]=i;}for(auto& edge:edges){merge(edge[0],edge[1]);}unordered_set<int> tmp;for(int i=0;i<n;++i){if(tmp.count(Father(i))==0){//注意这⾥要调⽤Father(i)函数，因为可能i的⽗亲还没有更新为最靠上的祖先。

计算机学科专业基础综合数据结构-图(二)(总分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. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的______，广度优先搜索算法类似于二叉树的层次序遍历。

第7章 图 自测卷解答 姓名 班级一、单选题（每题1分，共16分） 前两大题全部来自于全国自考参考书！（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。

A ．栈 B. 队列C. 树D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 （ ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 （建议：0 1 2 3 4 5 6） （ C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A ． 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D. 0 3 6 1 5 4 2建议：先画出图，再深度遍历⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110（ A ）12. 已知图的邻接表如下所示，根据算法，则从顶点0出发不是深度优先遍历的结点序列是A．0 1 3 2 B. 0 2 3 1C. 0 3 2 1D. 0 1 2 3（A）14. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）15. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）16. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

第7章图自测卷解答姓名班级题号一二三四五总分题分1620241030100得分一、单选题（每题1分，共16分）（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。

A．1/2B.1C.2D.4（B）2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1/2B.1C.2D.4（B）3.有8个结点的无向图最多有条边。

A．14B.28C.56D.112（C）4.有8个结点的无向连通图最少有条边。

A．5B.6C.7D.8（C）5.有8个结点的有向完全图有条边。

A．14B.28C.56D.112（B）6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图（C）8.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是01111011001001A．02431561000100B.0136542C.042316511001101011010D.03615420001101建议：01342561100010（D）9.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A．0243156B.0135642C.0423165D.0134256（B）10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243651B.0136425C.0423156D.0134256（建议：0123456）（C）11.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.01234561（D）12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是A．0132B.0231C.0321D.0123（A）13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312（A）14.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（D）15.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（A）16.任何一个无向连通图的最小生成树A．只有一棵B.一棵或多棵C.一定有多棵D.可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1.图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

一、应用题1．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。

1题图答．深度优先遍历序列：125967384宽度优先遍历序列：123456789注：（1）邻接表不唯一，这里顶点的邻接点按升序排列（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一（3）这里的遍历，均从顶点1开始2．给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。

（3）宽度优先生成树3.在什么情况下，Prim算法与Kruskual算法生成不同的MST？答．在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST4．已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，试画出构造过程）。

答．Prim 算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal 算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）5．G=(V,E)是一个带有权的连通图,则：（1）．请回答什么是G 的最小生成树； （2）．G 为下图所示,请找出G 的所有最小生成树。

28题图答．（1）最小生成树的定义见上面26题 （2）最小生成树有两棵。

（限于篇幅，下面的生成树只给出顶点集合和边集合，边以三元组（Vi,Vj,W ）形式），其中W 代表权值。

V （G ）={1，2，3，4，5} E1(G)={(4，5，2)，（2，5，4），（2，3，5），（1，2，7）}；E2(G)={(4，5，2），（2，4，4），（2，3，5），（1，2，7）}6．请看下边的无向加权图。

（1）．写出它的邻接矩阵。

（2）．按Prim 算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。

辅助数组各分量值：7．已知世界六大城市为:(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）．画出这六大城市的交通网络图;（2）．画出该图的邻接表表示法;（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树.8．已知顶点1-6和输入边与权值的序列（如右图所示）：每行三个数表示一条边的两个端点和其权值，共11行。

第一章绪论一、问答题1.什么是数据结构？2.叙述四类基本数据结构的名称与含义。

3.叙述算法的定义与特性。

4.叙述算法的时间复杂度。

5.叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。

7.叙述面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.叙述参数传递的主要方式及特点。

10.叙述抽象数据类型的概念。

二、判断题（在各题后填写“√”或“×”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

（）2.算法就是程序。

（）3. 在高级语言（如C或PASCAL）中，指针类型是原子类型。

（）三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。

注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。

通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。

（2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

第二章线性表2.1描述以下三个概念的区别：头指针，头结点，首元素结点。

2.2填空：（1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。

在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。

java邻接矩阵计算连通分量以Java邻接矩阵计算连通分量为主题，我们将介绍如何使用Java 编程语言来实现连通分量的计算，并且通过邻接矩阵来表示图的结构。

在此之前，我们先来了解一下什么是连通分量。

连通分量是图论中的一个概念，用来描述图中的若干个顶点组成的子集，其中任意两个顶点之间都存在路径。

换句话说，连通分量是指图中可以互相到达的顶点的集合。

在计算连通分量之前，我们需要先了解一下邻接矩阵的概念。

邻接矩阵是一种常用的图的表示方法，它是一个二维矩阵，其中矩阵的行和列分别表示图中的顶点，矩阵的元素表示顶点之间的边的关系。

如果两个顶点之间存在边，则对应的邻接矩阵元素为1；如果两个顶点之间不存在边，则对应的邻接矩阵元素为0。

接下来我们将介绍如何使用Java编程语言来实现邻接矩阵的计算连通分量。

我们需要定义一个Graph类来表示图的结构。

这个类需要包含一个邻接矩阵作为成员变量，并且提供一些方法来操作邻接矩阵。

```javapublic class Graph {private int[][] adjacencyMatrix;public Graph(int numVertices) {adjacencyMatrix = new int[numVertices][numVertices]; }public void addEdge(int source, int destination) {adjacencyMatrix[source][destination] = 1;adjacencyMatrix[destination][source] = 1;}public void removeEdge(int source, int destination) {adjacencyMatrix[source][destination] = 0;adjacencyMatrix[destination][source] = 0;}public boolean isConnected(int source, int destination) {return adjacencyMatrix[source][destination] == 1;}// 其他操作方法...}```在Graph类中，我们使用一个二维数组adjacencyMatrix来表示邻接矩阵。

习题7 图单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。

A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e② A. e/2 B. e D. n+e10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。

① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b图一个无向图11．已知一有向图的邻接表存储结构如图所示。

⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D. v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

实验五？无向图邻接表存储结构的创建、遍历及求连通分量实验五无向图邻接表存储结构的创建、遍历及求连通分量#include<iostream.h>typedef char vextype;const MAXVER=21;typedef struct listnode{int adjvex;struct listnode* next;}listnode;//表结点typedef struct{vextype data;listnode *first;}headnode;//头结点typedef struct{headnode vexs[MAXVER];int vexnum,arcnum;} ALgraph;//图void createALgraph(ALgraph &G){int i, s, d;listnode *p,*q;cout<<"输入图的顶点数和边数：";cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++){cout<<"\n输入第"<<i<<"个顶点信息：";cin>>G.vexs[i].data;G.vexs[i].first=NULL;} //输入第i个结点值并初始化第i个单链表为空for(i=1; i<=G.arcnum; i++){cout<<"\n输入第"<<i<<"条边的始点和终点：";cin>>s>>d;//s为始点，d为终点p=new listnode; p->adjvex=d;p->next=G.vexs[s].first;G.vexs[s].first=p;//将新建的以d为信息的表结点p插入s单链表的头结点后q=new listnode;q->adjvex=s;q->next=G.vexs[d].first;G.vexs[d].first=q;//将新建的以s为信息的表结点q插入d单链表的头结点后}}int visited[MAXVER];//定义全局数组遍历visitedvoid dfs(ALgraph G, int v)//被遍历的图G采用邻接表作为存储结构，v为出发顶点编号{listnode *p;cout<<G.vexs[v].data;visited[v]=1;p=G.vexs[v].first;while(p!=NULL){if(visited[p->adjvex]==0) dfs(G,p->adjvex);//若p所指表结点对应的邻接顶点未访问则递归地从该顶点出发调用dfsp=p->next;}}void dfsTraverse(ALgraph G){int v;//遍历图之前初始化各未访问的顶点for(v=1; v<=G.vexnum; v++)visited[v]=0;//从各个未被访问过的顶点开始进行深度遍历for(v=1;v<=G.vexnum;v++)if(visited[v]==0) dfs(G,v);}void dsfComp(ALgraph G){ int v;//遍历G以前，初始化visited数组为0for(v=1;v<=G.vexnum;v++)visited[v]=0;for(v=1;v<=G.vexnum;v++)if(visited[v]==0){cout<<endl<<"\n一个深度遍历连通分量为：";dfs(G,v);}}void BFS(ALgraph G, int v)//从顶点编号v出发，广度遍历邻接表存储的图G{int queue[MAXVER], front ,rear; listnode* p;front=rear=0;cout<<G.vexs[v].data;visited[v]=1;queue[++rear]=v;while(front!=rear){v=queue[++front];p=G.vexs[v].first;while(p!=NULL){if(visited[p->adjvex]==0){v=p->adjvex;cout<<G.vexs[v].data;visited[v]=1;queue[++rear]=v;}p=p->next;}}}void BFSTraverse(ALgraph G){int v;//遍历G以前，初始化visited数组为0 for(v=1;v<=G.vexnum;v++)visited[v]=0;for(v=1;v<=G.vexnum;v++)if(visited[v]==0)BFS(G,v);}void BFSComp(ALgraph G){int v;//遍历G以前，初始化visited数组为0for(v=1;v<=G.vexnum;v++)visited[v]=0;for(v=1;v<=G.vexnum;v++)if(visited[v]==0){cout<<endl<<"\n一个广度遍历连通分量为："; BFS(G,v);}}void main(){ALgraph g;createALgraph(g);cout<<endl<<"深度遍历结果为："; dfsTraverse(g);dsfComp(g);cout<<endl<<"广度遍历结果为："; BFSTraverse(g);BFSComp(g);cout<<endl;}。

#include<iostream>#include<vector>using namespace std;#define INFINITY 0 //最大值为无限大#define MAX_VERTEX_NUM 20 //最大顶点个数bool visited[MAX_VERTEX_NUM]={false}; //数组的遍历标志//typedef enum{DG,DN,UDG,UDN} GraphKind; //{有向图，有向网，无向图，无向网} typedef struct ArcCell{int adj; //对无权图，用1或0表示是否相邻;对带权图，则为权值int* info; //边的信息} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{int vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的类型}MGraph;int CreateUDN(MGraph &G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;G.arcs[v2-1][v1-1].adj=w;}return 1;int CreateUDG(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for(i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;G.arcs[v2-1][v1-1].adj=w;}return 1;}int CreateDN(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;}return 1;}int CreateDG(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;}return 1;}int CreateGraph(MGraph& G){cout<<"请输入你想要的图的类型：";cin>>G.kind;switch(G.kind){case 0:return CreateDG(G); //构造有向图case 1:return CreateDN(G); //构造有向网case 2:return CreateUDG(G); //构造无向图case 3:return CreateUDN(G); //构造无向网default:return 0;}}int FirstAdjVex(MGraph& G,int i){for(int j=0; j<G.vexnum; j++){if(G.arcs[i][j].adj!=0)return j;}return -1;}int NextAdjVex(MGraph& G,int i,int w){for(int j=w+1; j<G.vexnum; ++j){if(G.arcs[i][j].adj!=0)return j;}return -1;}void DFS(MGraph& G,int i){visited[i]=true;cout<<G.vexs[i]<<" "<<endl;for(int w=FirstAdjVex(G,i); w>=0; w=NextAdjVex(G,i,w)){ if(!visited[w])DFS(G,w);}}void DFSTraverse(MGraph& G){int number=0;for(int i=0; i<G.vexnum; i++){if(!visited[i]){number++;DFS(G,i);}}cout<<"图的连通分量有"<<number<<"个"<<endl;}int main(){MGraph G;CreateGraph(G);for(int i=0; i<G.vexnum;i++){for(int j=0; j<G.vexnum; j++)cout<<G.arcs[i][j].adj<<" ";cout<<endl;}cout<<endl;DFSTraverse(G);return 0;}。

中国人民理工大学指挥自动化学院试卷解放军考试科目：第4 章图结构队别专业：学号：姓名：考试日期：年月日1.单项选择题（每题2分，共36分）【1】在一个无向图中，所有顶点的度数之和等于所有边数的倍。

A．1／2 B．1 C．2 D．4【2】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1／2 B．1 C．2 D．4【3】一个有n个顶点的无向图最多有条边。

A．n B．n(n-1) C．n(n-1)/2 D．2n【4】具有4个顶点的无向完全图有条边。

A．6 B．12 C．16 D．20【5】具有6个顶点的无向图至少应有条边才能确保是一个连通图。

A．5 B．6 C．7 D．8【6】在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。

A．n B．n+1 C．n-1 D．n/2【7】对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。

A．n B．(n-1)2 C．n-1 D．n2【8】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为①：所有邻接表中的结点总数是②。

①A．n B．n+1 C．n-1 D．n+e②A．e/2 B．e C．2e D．n+e【9】对某个无向图的邻接矩阵来说，。

A．第i行上的非零元素个数和第i列的非零元素个数一定相等B．矩阵中的非零元素个数等于图中的边数C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数【10】已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为①；按广度搜索法进行遍历，则可能得到的一种顶点序列为②。

①A．a，b，e，c，d，f B．a，c，f，e，b，dC．a，e，b，c，f，d D．a，e，d，f，c，b②A．a，b，c，e，d，f B．a，b，c，e，f，dC．a，e，b，c，f，d D．a，c，f，d，e，b【11】已知一有向图的邻接表存储结构如图所示。

计算机专业基础综合数据结构（图）历年真题试卷汇编7(总分62, 做题时间90分钟)7. 设计题1.已知连通图如下：(1)若从顶点B出发对该图进行遍历，在(1)的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；(2)写出按深度优先搜索的递归程序。

【厦门大学200l三(12％分)】SSS_TEXT_QUSTI2.设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形，式输出。

例如，下图的输出结果为：(1，3)(2，6，7，4，5，8)(9，10)。

注：本算法中可以调用以下几个函数：firstadj(g，1，)——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0。

nextadj(g，v，w)——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。

nodes(g)——返回图g中的顶点数。

【合肥工业大学2000五、4(8分)】SSS_TEXT_QUSTI3.请设计一个图的抽象数据类型(只需要用类Pascal或类C／C++语言给出其主要功能函数或过程的接口说明，不需要指定存储结构，也不需要写出函数或过程的实现方法)，利用抽象数据类型所提供的函数或过程编写图的广度优先周游算法。

算法不应该涉及具体的存储结构，也不允许不通过函数或过程而直接引用图结构的数据成员，抽象数据类型和算法都应该加足够的注释。

【北京大学1999二、1(10分)】SSS_TEXT_QUSTI4.设计算法以判断给定的无向图G中是否存在一条以网为起点的包含所有顶点的简单路径，若存在，返回TRUE，否则，返回FALSE(注：本算法中可以调用以下几个函数：FIRSTADJ(G，V)——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ(G，W)——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES(G)——返回图G中的顶点数)。

【合肥工业大学1999五、5(8分)】SSS_TEXT_QUSTI5.已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有，则印出该路径上的顶点。

习题7 图7.1 单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。

A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。

A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。

A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。

A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

①A. n B. n+1 C. n-1 D. n+e②A. e/2 B. e C.2e D. n+e10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。

①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b②A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b图 7.1 一个无向图11．已知一有向图的邻接表存储结构如图7.2所示。

图7.2 一个有向图的邻接表存储结构⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

《数据结构》实验报告实验内容：（一）判断一个图有无回路（二）求一个无向图G的连通分量的个数一、目的和要求（需求分析）：1、了解图的定义和图的存储结构。

2、熟悉掌握图的邻接矩阵和邻接表。

3、理解图的遍历算法---深度优先搜索和广度优先搜索。

4、学会编程处理图的连通性问题。

二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）判断一个图有无回路：在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。

在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。

如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。

无向图则可以转化为：如果存在回路，则必然存在一个子图，是一个回路。

因此回路中所有定点的度>=2。

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

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

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

求一个无向图G的连通分量的个数：用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。

三、调试和运行程序过程中产生的问题及采取的措施：在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)，而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。

一、选择题1．数据结构被形式地定义为（K ，R ），其中K 是 数据元素 的有限集合，R 是K 上的 关系 有限集合。

2．链表不具备的特点是 可随机访问任一结点 。

3．若某表最常用的操作是在最后一个结点之间插入一个结点或删除最后一个结点，则采用 带头结点的双循环链表 存储方式最节省运算时间。

4．栈的特点是 先进先出 ，队列的特点是 先进后出 。

5．一个栈的进栈序列是A ，B ，C ，D ，E ，则栈的不可能的输出序列是 DCEAB 。

A ．EDCBAB 。

DECBAC 。

DCEABD 。

ABCDE6．串是一种特殊的线性表，其特殊性体现在 数据元素是一个字符 。

7．一维数组和线性表的区别是 前者长度固定，后者长度可变 。

8.稀疏矩阵一般的压缩存储方法有两种，即 三元组和十字链表 。

9．在线索化二叉树中，t 所指结点没有左子树的充要条件是 B 。

A ．t->left==NULLB. t->ltag==1（P189）C. t->ltag==1且t->left==NULLD ．以上都不对10．设高度为h 的二叉树上只有度为0和度为2 的结点，则此类二叉树中所包含的结点数至少为 B 。

（P158的例题）A ．2h B. 2h-1 C. 2h+1 D.h+111．如图所示二叉树的中序遍历序列是 B 。

（P173）A ．abcdger B. dfebagc C.dbaefcg D. defbagc中序遍历：先左子树，再根，再右子树先序遍历：先根，再左，后右 后序遍历：先左，后右，最后根则该二叉树一定是 高度等于其结点数 。

此种情况只有单只子树才会出现13．在一个图中，所有顶点的度数之和等于所有边数的2倍。

P205(每条边分别作为两个邻接点的度各计了一次)14．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B 倍。

A 1/2B 1C 2D 417、一个有n 个顶点的无向图最多有n(n-1)/2条边。

第7章图一、选择题1．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n22．一个具有n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn；3．要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n4．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）5．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n6．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A．1/2 B．2 C．1 D．47．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图 B．无向图 C．AOV网 D．AOE网8. 下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．图的深度遍历不适用于有向图C．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程9．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V711．一个有向无环图的拓扑排序序列（）是唯一的。