南工大第四章-图.doc

数据结构与算法上机作业
第四章 图
一、选择题
1、在一个无向图中,所有顶点得度数之与等于所有边数得 C 倍。
A、 1/2 B、 1 C、 2 D、 4
2、在一个有向图中,所有顶点得入度之与等于所有顶点出度之与得 B 倍。
A、 1/2 B、 1 C、 2 D、 4
3、G就是一个非连通无向图,共有28条边,则该图至少有 D 个顶点。
A、 6 B、 7 C、 8 D、 9
4、有n个顶点得图得邻接矩阵使用 B 数组存储得。
A、 一维 B、 n行n列 C、 任意行n列 D、 n行任意列
5、对于一个具有n个顶点与e条边得无向图,采用邻接表表示,则表头数组大小至少为(假设下标为0得数组参与使用) A 。
A、 n-1 B、 n+1 C、 n D、 n+e
6、下列说法正确得就是 C 。
A、 有向图得邻接矩阵一定就是不对称得
B、 有向图得邻接矩阵一定就是对称得
C、 无向图得邻接矩阵一定就是对称得
D、 无向图得邻接矩阵可以不对称
7、深度优先遍历类似与二叉树得 A :
A、 先根遍历 B、 中根遍历 C、 后根遍历 D、 层次遍历
8、广度优先遍历类似与二叉树得 D :
A、 先根遍历 B、 中根遍历 C、 后根遍历 D、 层次遍历
9、下列关于开放树(Free Tree)得说法错误得就是 C :
A、 具有n个结点得开放树包含n-1条边
B、 开放树没有回路
C、 开放树可以就是非连通图
D、 在开放树中任意加一条边,一定会产生回路
10、在如下图所示得图中,从顶点a出发,按深度优先遍历,则可能得到得一种顶点得序列为 。
A、 a, b, e, c, d, f B、 a, c, f, e, b, d
C、 a, e, b, c, f, d D、 a, e, d, f, c, b

11、在如上图所示得图中,从顶点a出发,按广度优先遍历,则可能得到得一种顶点得序列为 。
A、 a, b, e, c, d, f B、 a, b, e, c, f, d
C、 a, e, b, c, f, d D、 a, e, d, f, c, b
12、设网(带权得图)有n个顶点与e条边,则采用邻接表存储时,求最小生成树得Prim算法得时间复杂度为 C 。
A、 O(n) B、 O(n+e) C、 O(n2) D、 O(n3)
13、设图有n个顶点与e条边,求解最短路径得Floyd算法得时间复杂度为 O 。
A、 O(n) B、 O(n+e) C、 O(n2) D、 O(n3)
14、最小生成树就是指 C 。
A、 由连通网所得到得边数最少得生成树。
B、 由连通网所得到得顶点数相对较少得生成树。
C、 连通网中所有生成树中权值之与为最小得生成树。
D、 连通网得极小连通子图。
15、下面关于工程计划得AOE网得叙述中,不正确得就是 B 。
A、 关键活动不按期完成就会影响整个工程得完成时间。
B、 任何一个关键活动提前完成,那么整个工程将会提前完成。
C、 所有关键活动都提前完成,那么整个工程将会提前完成。
D、 某些关键工程若提前完成,那么整个工程将会提前完成。
16、在AOE网中,始点与汇点得个数为 C 。
A、 1个始点,若干个汇点 B、 若干个始点,若干个汇点
C、 若干个始点,1个汇点 C、 1个始点,1个汇点
17、在下图所示得无向图中,从顶点v1开始采用Prim算法生成最小生成树,算法过程中产生得顶点次序为 B 。
A、 v1, v3, v4, v2, v5, v6 B、 v1, v3, v6, v2, v5, v4
C、 v1, v2, v3, v4, v5, v6 D、 v1, v3, v6, v4, v2, v5

18、在上图所示得途中,采用Cruskal算法生成最小生成树,过程中产生得边得次序就是 C 。
A、 (v1, v2), (v2, v3), (v5, v6), (v1, v5) B、 (v1, v3), (v2, v6), (v2, v5), (v1, v4)
C、 (v1, v3), (v2, v5), (v3, v6), (v4, v5) D、 (v2, v5), (v1, v3), (v5, v6), (v4, v5)
19、如下图所示得图中,其中一个拓扑排序得结果就是 A 。
A、 v1→v2→v3→v6→v4→v5→v7→v8
B、 v1→v2→v3→v4→v5→v6→v7→v8
C、 v1→v6→v4→v5→v2→v3→v7→v8
D、 v1→v6→v2→v3→v7→v8→v4→v5

20、在下图所示得AOE网中,活动a9得最早开始时间为 B 。
A、 13 B、 14 C、 15 D、 16

21、在上图所示得AOE网中,活动a4得最迟开始时间为 D
A、 2 B、 3 C、 4 D、 5
22、设图有n个顶点与e条边,当用邻接表表示该图时,则求解最短路径得Dijkstra算法得时间复杂度为 O 。
A、 O(n) B、 O(n+e) C、 O(e) D、 O(n2)
二、填空题
1、若无向图G中顶点数为n,则图G至多有 n(n-1)/2 条边;若G为有向图,则图G至多有 n(n-1) 条边。
2、图得存储结构主要有两种,分别就是 邻接表 与 邻接矩阵 。
3、若G 就是有向图,则把邻接到顶点v 得顶点数目或边数目称为顶点v 得 入度 ;把邻接于顶点v 得顶点数目或边数目称为顶点v 得 出度 。
4、已知一个图得邻接矩阵表示,计算第j个顶点得入度得方法就是 第j行非0元素得个数 ,计算第j个顶点得出度得方法就是 第j列非0元素得个数 。
5、若将图中得每条边都赋予一个权,则称这种带权得图为 网络 。
6、无论就是有向图还就是无向图,顶点数n 、边数e 与各顶点得度D(vi)之间得关系为: 。
7、若路径上第一个顶点v1 与最后一个顶点vm 重合, 则称这样得简单路径为 回路或环 。
8、如果图中任意一对顶点都就是连通得, 则称此图就是 连通图 ;非连通图得极大连通子图叫做 连通分量 。
9、创建一个邻接矩阵图得复杂度就是 O(n*n) ;创建一个链接表图得复杂度就是 O(n+e) 。
10、图得遍历有 深度优先遍历 与广度优先遍历等方法。
11、在深度优先搜索与广度优先搜索中,都采用visited[i]= 0(false) 得方式设置第i个顶点为new,而采用visited[i]= 1(true) 得方式标识第i个结点为old。
12、由于深度优先算法得特点,深度优先往往采用 递归 得方式实现。
13、由于广度优先算法得特点,在广度优先实现过程中,往往要借助于另一种数据结构
队列 实现。
14、在深度优先搜索与广度优先搜索中,在搜索过程中所经过得边都称为 搜索边 。
15、连通而且无环路得无向图称为 开放数 。
16、对于含有n个顶点e条边得连通图,利用Prim算法求其最小生成树得时间复杂度为 O(n*n) ,利用Kruscal算法求最小生成树得时间复杂度就是 O(e*lg e) 。
3、顶点表示活动得网简称为 AOV ;边表示活动得网简称为 AOE 。
17、一个含有n个顶点得无向连通图,其每条边得权重都就是a(a>0),则其最小生成树得权重等于 (n-1)*a 。
18、具有n个顶点得有向图,如果采用邻接矩阵表示该图,则求某顶点到其她各顶点得最短路径得Dijkstra算法得时间复杂度就是 O(n*n) ;如果采用邻接表表示该图,则时间复杂度为 O(e) 。
19、在用Dijkstra算法求单源最短路径得过程中,将顶点集合V划分为两个集合S与V-S,其中S中得点为 最短路径已确定得顶点集合 ,V-S中得点为 最短路径未确定得顶点集合 。
20、求每一对顶点之间得最短路径,可以用两种方法,一种就是分别对每个顶点采用 算法,另一种方法就是 。
21、假设有向图得邻接矩阵C得传递闭包为A,则A[i][j]=1表示 。
22、有向图得中心点就是指 具有最小偏心度得顶点 。
三、已知一个无向图如下图所示,试给出该图得邻接矩阵与邻接表存储示意图(画图,分别用矩阵与数组链表图表示),并编程分别实现该图得邻接矩阵表示与邻接表表示,要求编写两种表示方法得存储结构、相关基本操作,并在主函数中创建该图。

代码:
#include<iostream>
using namespace std;
#define max_vexNum 26 // 最大顶点个数
typedef struct{
int vex_num, arc_num; // 顶点数 ,边数
int count; //记录当前顶点数
char vexs[max_vexNum]; // 顶点向量
double arcs[max_vexNum][max_vexNum]; // 邻接矩阵
} Graph;
//添加一个新得顶点
char NewNode(Graph *G,char v){
G->vexs[G->count]=v;
G->count++;
return v;
}
//寻找某个顶点得位置
int FindPosition(Graph *G,char v){
for( int i=0;i<G->count;i++){
if(v==G->vexs[i])
return i;
}
}
void Delete(Graph *G,char v){
//先删除点
int i,j;
int temp_count= G->count;
i=FindPosition(G,v);
for(j=i;j<temp_count;j++)
G->vexs[j]=G->vexs[j+1];
G->count--;
// 删除边
//先删除行
int p=i;//记住位置
for(i=p;i<temp_count-1;i++)
for(j=0;j<temp_count;j++)
G->arcs[i][j]=G->arcs[i+1][j];
//再删除列
for(i=p;i<temp_count-1;i++)
for(j=0;j<temp_count;j++)
G->arcs[j][i]=G->arcs[j][i+1];
}
//建立v1与v2得一条边
void SetSoucc(Graph * G,char v1,char v2){
//先找到对应得定得位置
int i,j;
int temp_count= G->count;
i=FindPosition(G,v1);
j=FindPosition(G,v2);
if(i==temp_count||j==temp_count) //没有找到
return ;
//找到后 ,A[i][j]=0;vexs[j][i]=0;
G-> arcs[i][j]=1;
G-> arcs[j][i]=1;
}
void DelSucc(Graph * G,char v1,char v2){
int i,j;
int temp_count= G->count;
i=FindPosition(G,v1);
j=FindPosition(G,v2);
if(i==temp_count||j==temp_count) //没有找到
return ;
//找到后 ,A[i][j]=0;vexs[j][i]=0;
G-> arcs[i][j]=0;
G-> arcs[j][i]=0;
}
//判断v1y与v2就是否连接
bool isEdge(Graph * G,char v1,char v2){
int i,j;
int temp_count= G->count;
i=FindPosition(G,v1);
j=FindPosition(G,v2);
if(i==temp_count||j==temp_count) //没有找到
return -1;
if(G->arcs[i][j]==1)
return true;
return false;
}
void Print(Graph * G){
int i,j;
for( i=0;i<G->count;i++){
for(j=0;j<G->count;j++)
cout<<G->arcs[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
Graph *G=new Graph;//初始化
int main(){
G->count=0;
NewNode(G,'A');
NewNode(G,'B');
NewNode(G,'C');
NewNode(G,'D');
//插入边
SetSoucc(G,'A','B');
SetSoucc(G,'A','D');
SetSoucc(G,'C','B');
Print(G);
//删除一个顶点
Delete(G,'C');
Print(G);
//删除边
DelSucc(G,'A','D');
Print(G);
if(isEdge(G,'A','B'))
cout<<"A与B右边"<<endl;
return 0;
}
四、已知一个有向图如下图所示,试给出图得邻接矩阵与邻接表存储示意图(画图,分别用矩阵与数组链表图表示),并编程分别实现该图得邻接矩阵表示与邻接表表示,要求编写两种表示方法得存储结构、相关基本操作,并在主函数中创建该图。

代码:
#include<iostream>
#include <stdio、h>
#include<stdlib、h>
using namespace std;
#define max_n 20
struct ArcNode {
char adjvex='#';
ArcNode * next=NULL;
} ;
typedef struct VNode{
char data;
ArcNode * first_head;
} VNode ,AdjList[max_n];
typedef struct {
AdjList vertices;
int vexnum,arcnum;
int count=0;
} Graph;
//新增一个顶点
char NewNode(Graph * G,char v) {
G->vertices[G->count]、data=v;
G->vertices[G->count]、first_head=new ArcNode;
G->count++;
return v;
}
//寻找某个顶点得位置
int FindPosition(Graph *G,char v){
for( int i=0;i<G->count;i++){
if(v==G->vertices[i]、data)
return i;
}
}
//删除一个顶点
void DelNode(Graph * G,char v){
int i=FindPosition(G,v);
//去头
ArcNode *p=G-> vertices[i]、first_head;
//现在 vertices中删除
int j;
for(j=i;j<G->count-1;j++)
G->vertices[j]=G->vertices[j+1];
G->vertices[j]、data='#';
G->vertices[j]、first_head=NULL;
G->count--;
//删除边
ArcNode *q;
while(p!=NULL){
q=p;
p=p->next;
q=NULL;
}
}
//设置v1到v2直接得一条边
void SetSucc(Graph * G,char v1,char v2){
int i=FindPosition(G,v1);
ArcNode *p;
p=G->vertices[i]、first_head;
while(p->next!=NULL){
p=p->next;
}
ArcNode *q=new ArcNode;
q->adjvex=v2;
p->next=q;
}
ArcNode * FindNode(ArcNode * p,char v2){
for(;p;p=p->next){
if(p->next->adjvex==v2)
break;
}
return p;
}
void Detele(Graph * G,char v1,char v2){
int i=FindPosition(G,v1);
ArcNode *p;
//没有找到
if(i==-1)
return ;
p=FindNode(G->vertices[i]、first_head,v2);
//因为p就是上一个节点得位置,用q来保存
//要删除得节点得地址
ArcNode *q = p->next;
//通过将上一个节点得next指针指向要删除节点得next指
//针志向得节点实现断开要删除节点得目得
// p->adjvex=p->next->adjvex;
p->next = p->next->next;
//删除要删除得节点q
delete q;
}
//输出领接表
void Print(Graph * G){
ArcNode *p;
for(int i=0;i<G->count;i++){
//先将 data
cout<< G->vertices[i]、data<<"->";
//从每个顶点得头结点开始遍历
if(G->vertices[i]、first_head->next!=NULL){
p=G->vertices[i]、first_head->next;
while(p!=NULL){
cout<<p->adjvex<<"->";
p=p->next;
}
}
cout<<endl;
}
cout<<endl;
}
Graph * G=new Graph;
int main() {
NewNode(G,'A');
NewNode(G,'B');
NewNode(G,'C');
NewNode(G,'D');
Print(G);
SetSucc(G,'A','D');
SetSucc(G,'A','B');
SetSucc(G,'A','C');
SetSucc(G,'B','C');
SetSucc(G,'C','D');
SetSucc(G,'D','B');
Print(G);
Detele(G,'A','C');
Detele(G,'D','B');
Print(G);
SetSucc(G,'D','C');
Print(G);
return 0;
}
五、已知一个图得顶点集为{a, b, c, d, e},其邻接矩阵如下图,考虑图为无向图与有向图两种情况,分别画出该图。

六、已知一个连通图如下图所示,分别给出一个按深度优先遍历与广度优先遍历得顶点序列(假设从顶点v1出发)。并编程分别实现该图得邻接矩阵表示与邻接表表示,要求编写相关基本操作,并在主函数中求出深度优先序列与广度优先序列。

代码:
#include<iostream>
#include <stdio、h>
#include<stdlib、h>
#include<queue>
using namespace std;
#define max_n 20
struct ArcNode {
char adjvex='#';
ArcNode * next=NULL;
} ;
typedef struct VNode {
char data;
ArcNode * first_head;
} VNode ,AdjList[max_n];
typedef struct {
AdjList vertices;
int visit[max_n] = {0}; //记录就是否被访问过
int vexnum,arcnum;
int count=0;
} Graph;
//新增一个顶点
char NewNode(Graph * G,char v) {
G->vertices[G->count]、data=v;
G->vertices[G->count]、first_head=new ArcNode;
G->count++;
return v;
}
//寻找某个顶点得位置
int FindPosition(Graph *G,char v) {
for( int i=0; i<G->count; i++) {
if(v==G->vertices[i]、data)
return i;
}
}
//删除一个顶点
void DelNode(Graph * G,char v) {
int i=FindPosition(G,v);
//去头
ArcNode *p=G-> vertices[i]、first_head;
//现在 vertices中删除
int j;
for(j=i; j<G->count-1; j++)
G->vertices[j]=G->vertices[j+1];
G->vertices[j]、data='#';
G->vertices[j]、first_head=NULL;
G->count--;
//删除边
ArcNode *q;
while(p!=NULL) {
q=p;
p=p->next;
q=NULL;
}
}
//设置v1到v2直接得一条边
void SetSucc(Graph * G,char v1,char v2) {
int i=FindPosition(G,v1);
ArcNode *p;
p=G->vertices[i]、first_head;
while(p->next!=NULL) {
p=p->next;
}
ArcNode *q=new ArcNode;
q->adjvex=v2;
p->next=q;
}
//对于无向图
void SetSucc1(Graph * G,char v1,char v2) {
SetSucc(G,v1,v2);
SetSucc(G,v2,v1);
}
ArcNode * FindNode(ArcNode * p,char v2) {
for(; p; p=p->next) {
if(p->next->adjvex==v2)
break;
}
return p;
}
void Detele(Graph * G,char v1,char v2) {
int i=FindPosition(G,v1);
ArcNode *p;
//没有找到
if(i==-1)
return ;
p=FindNode(G->vertices[i]、first_head,v2);
//因为p就是上一个节点得位置,用q来保存
//要删除得节点得地址
ArcNode *q = p->next;
//通过将上一个节点得next指针指向要删除节点得next指
//针志向得节点实现断开要删除节点得目得
// p->adjvex=p->next->adjvex;
p->next = p->next->next;
//删除要删除得节点q
delete q;
}
//输出领接表
void Print(Graph * G) {
ArcNode *p;
for(int i=0; i<G->count; i++) {
//先将 data
cout<< G->vertices[i]、data<<"->";
//从每个顶点得头结点开始遍历
if(G->vertices[i]、first_head->next!=NULL) {
p=G->vertices[i]、first_head->next;
while(p!=NULL) {
cout<<p->adjvex<<"->";
p=p->next;
}
}
cout<<endl;
}
cout<<endl;
}
void makeVisitNull(Graph * G){
for(int i=0;i<max_n;i++)
G->visit[i]=0;
}
void Dfs_part(Graph * G,int i) {
ArcNode *p=G->vertices[i]、first_head->next;
for(; p; p=p->next) {
int i=FindPosition(G,p->adjvex);
if(!G->visit[i]) {
G->visit[i]=1;
cout<<p->adjvex<<"->";
Dfs_part(G,i);
}
}
}
//深度优先遍历
void DFS(Graph * G,int i) {
cout<<G->vertices[i]、data<<"->";
G->visit[i]=1;
Dfs_part(G,i);
//恢复
makeVisitNull(G);
cout<<endl;
}
queue<int> qList;
void Bfs_part(Graph * G) {
int t= qList、front();
cout<<G->vertices[t]、data<<"->";
qList、pop();
ArcNode *p=G->vertices[t]、first_head->next;
for(; p; p=p->next) {
int i=FindPosition(G,p->adjvex);
if(!G->visit[i]) {
G->visit[i]=1;
qList、push(i);
}
}
if(!qList、empty())
Bfs_part(G);
}
//
void BFS(Graph * G,int i) {
G->visit[i]=1;
qList、push(i);
Bfs_part(G);
//恢复
makeVisitNull(G);
cout<<endl;
}
Graph * G=new Graph;
int main() {
NewNode(G,'1');
NewNode(G,'2');
NewNode(G,'3');
NewNode(G,'4');
NewNode(G,'5');
NewNode(G,'6');
Print(G);
SetSucc1(G,'1','2');
SetSucc1(G,'1','4');
SetSucc1(G,'1','6');
SetSucc1(G,'2','3');
SetSucc1(G,'2','4');
SetSucc1(G,'2','5');
SetSucc1(G,'3','5');
SetSucc1(G,'4','6');
SetSucc1(G,'4','5');
Print(G);
cout<<"DFS:"<<endl;
DFS(G,0);
cout<<"BFS:"<<endl;
BFS(G,0);
return 0;
}
七、基于深度优先搜索算法,写出求无向图所有连通子图得算法,并求连通分量。
提示:对于无向图,从任一个顶点出发进行DFS遍历,当本次遍历完成后,其所访问得结点构成一个连通子图;如果还存在没有访问过得结点,则从中任一个结点出发进行DFS遍历,……,直到所有结点都被访问。每一次调用DFS后都得到此非连通图得一个连通子图,调用DFS得次数就就是连通子图得个数。
八、网络G得邻接矩阵如下,试画出该图,并画出它得一棵最小生成树。

解:
九、 下图就是一个无向带权图,请给出该图得邻接矩阵,并分别按Prim算法与Kruskal算法求最小生成树(包括算法代码与画图)。

代码:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INFINITE 0xFFFFFFFF
#define VertexData unsigned int //顶点数据
#define UINT unsigned int
#define vexCounts 6 //顶点数量
char vextex[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
struct node {
VertexData data;
unsigned int lowestcost;
} closedge[vexCounts]; //Prim算法中得辅助信息
typedef struct {
VertexData u;
VertexData v;
unsigned int cost; //边得代价
} Arc; //原始图得边信息
void AdjMatrix(unsigned int adjMat[][vexCounts]) { //邻接矩阵表示法
for (int i = 0; i < vexCounts; i++) //初始化邻接矩阵
for (int j = 0; j < vexCounts; j++) {
adjMat[i][j] = INFINITE;
}
}
int Minmum(struct node * closedge) { //返回最小代价边
unsigned int min = INFINITE;
int index = -1;
for (int i = 0; i < vexCounts; i++) {
if (closedge[i]、lowestcost < min && closedge[i]、lowestcost !=0) {
min = closedge[i]、lowestcost;
index = i;
}
}
return index;
}
void MiniSpanTree_Prim(unsigned int adjMat[][vexCounts], VertexData s) {
for (int i = 0; i < vexCounts; i++) {
closedge[i]、lowestcost = INFINITE;
}
closedge[s]、data = s; //从顶点s开始
closedge[s]、lowestcost = 0;
for (int i = 0; i < vexCounts; i++) { //初始化辅助数组
if (i != s) {
closedge[i]、data = s;
closedge[i]、lowestcost = adjMat[s][i];
}
}
for (int e = 1; e <= vexCounts -1;