回答下列概念完全图

1、6 图6.1 回答下列概念：完全图、子图、连通分量、网络、最小生成树、拓扑序列 完全图：任意两个顶点之间都有边的图。子 图：设有图G=(V,E)，若V'是V的子集(V'V)，E'是E的子集(E'E)，且E'中的边所邻接的点均在V'中出现，则G'=(V',E')也是一个图，并且称之为G的子图。连通分量：无向图G的极大连通子图。网 络：边上带权的图。最小生成树：连通网络的所有生成树中边上权值之和最小的生成树。拓扑序列：有向无环图中所有顶点按照拓扑排序的思想排成的一个线性序列。6.2 n个顶点的无向图，若采用邻接矩阵为存储结构，

2、如何求边的条数？如何求某个顶点的度？如果该图为有向图呢？无向图的邻接矩阵是对称的，“1”的个数则是图中边的条数的2倍，第i行或第i列上“1”的个数都是序号为i的顶点的度。有向图中，“1”的个数则是图中边的条数，第i行“1”的个数是序号为i的顶点的出度，第i列上“1”的个数是序号为i的顶点的入度。6.3 对于一个具有n个顶点和e条边的无向图，若采用邻接表为存储结构，所有边表中的结点总数为多少？如何求某个顶点的度？当该图为有向图时，所有边表中的结点总数为多少？如何求某个顶点的入度和出度？（1）无向图的边表中的结点总数为：2*e；某个顶点的度：该顶点的边表中的结点个数。（2）若该图为有向图，且采用邻

3、接表（通常称为出边表）为存储结构，则所有边表中的结点总数为e；出边表中，顶点vi对应的边表结点的个数即为顶点vi的出度；求顶点vi的入度，需要遍历整个出边表，求边表结点中adjvex域的值为i的结点个数。6.4 设一个有向图为G=(V,E)，其中V= v1,v2,v3,v4，E=< v2,v1>,< v2,v3>,< v4,v1>,< v1,v4>,< v4,v2>,请回答下列各问：（1）画出该有向图，求出每个顶点的入度和出度。（2）画出该图的邻接矩阵存储结构图示并给出C语言描述。（3）画出该图的邻接表和逆邻接表的存储结构图示并给出C

4、语言描述。（4）写出从顶点v2出发的DFS序列和BFS序列。 （1）有向图如下：顶点v1的入度是2，出度是1；顶点v2的入度是1，出度是2；顶点v3的入度是1，出度是0；顶点v4的入度是1，出度是2。（2）C语言描述：#define N 4/* 图的顶点数 */typedef char VexType;/* 顶点类型 */typedef int AdjType;/* 权值类型 */typedef structVexType vertexN+1;/* 顶点数组 */AdjType edgeN+1N+1;/* 邻接矩阵 */AdjMatrix;（3）C语言描述：typedef struct nod

5、e int adjvex;/* 邻接点域 */ struct node *next; /* 指针域 */EdgeNode; /* 定义边表结点 */typedef struct VexType vertex; /* 顶点域 */ EdgeNode *link; /* 指针域 */VexNode; /* 定义顶点表结点 */#define N 10VexNode adjlistN+1;邻接表图示：逆邻接表图示：（4）DFS序列： v2, v1,v4,v3 BFS序列： v2, v1,v3,v46.5 对图6.50所示的无向图，依次输入各边：(v1,v2)、(v1,v4)、(v2,v3)、(v3,

6、v4)、(v3,v5)，请回答下列各问：（1）写出该无向图的二元组表示。（2）画出该图的邻接矩阵和邻接表（头插法建表）存储结构图示。（3）对（2）中的邻接矩阵，给出从顶点v1出发的DFS序列和DFS生成树。（4）对（2）中的邻接表，给出从顶点v1出发的BFS序列和BFS生成树。 （1）无向图G的二元组表示：设G=(V,E)，V为顶点集，E为边集，则V=v1,v2,v3,v4,v5E=(v1,v2)、(v1,v4)、(v2,v3)、(v3,v4)、(v3,v5)（2）邻接矩阵图示：邻接表图示：（3）对（2）中的邻接矩阵，从顶点v1出发的DFS序列是v1,v2,v3,v4,v5DFS生成树是：（4

7、）对（2）中的邻接表，从顶点v1出发的BFS序列是：v1,v4,v2,v3,v5BFS生成树：6.6 画出图6.51的所有可能的最小生成树。 图6.50 图6.516.7 求出图6.52从顶点v1到其他各顶点之间的最短路径。终点路径长度路径v10v1v1v220v1v2v35v1v3v419v1v3v6v4v525v1v3v6v5v615v1v3v66.8 给出图6.53所有可能的拓扑序列。 图 6.52 图6.53v2,v1,v3,v5,v4,v7,v8,v6或v5,v2,v1,v3, v4,v7,v8,v6或v7, v2,v1,v3, v5, v4,v8,v66.9 设计一个算法将一个无向

8、图的邻接矩阵转换成邻接链表。/邻接矩阵的C语言描述#define N 5/* 图的顶点数 */typedef char VexType;/* 顶点类型 */typedef int AdjType;/* 权值类型 */typedef structVexType vertexN+1;/* 顶点数组 */AdjType edgeN+1N+1;/* 邻接矩阵 */AdjMatrix;/邻接表的C语言描述typedef struct node int adjvex;/* 邻接点域 */ struct node *next; /* 指针域 */EdgeNode; /* 定义边表结点 */typedef s

9、truct VexType vertex; /* 顶点域 */ EdgeNode *link; /* 指针域 */VexNode; /* 定义顶点表结点 */VexNode adjlistN+1;void creatAdjList(AdjMatrix *adj) /* 根据邻接矩阵建立邻接表 */int i,j;EdgeNode *s;for(i=1;i<=N;i+) /* 顶点下标从1开始 */adjlisti.vertex=adj->vertexi;adjlisti.link =NULL; /* 边表指针初始为空 */for(i=1;i<=N;i+) /* 建立边表 */

10、 for(j=N;j>=1;j-)if(adj->edgeij=1)s=(EdgeNode*)malloc(sizeof(EdgeNode);/* 生成边表结点*/s->adjvex=j;s->next=adjlisti.link; /* 插入到顶点vi的边表头部 */adjlisti.link=s; /* creatAdjList */6.10 以邻接矩阵作为图的存储结构，试写出图的非递归的深度优先搜索算法。/邻接矩阵的C语言描述#define N 5/* 图的顶点数 */#define MAXSIZE 10typedef char VexType;/* 顶点类型 *

11、/typedef int AdjType;/* 权值类型 */typedef structVexType vertexN+1;/* 顶点数组 */AdjType edgeN+1N+1;/* 邻接矩阵 */AdjMatrix;int visitedN+1; /* 全局标志数组，标注顶点是否被访问 */typedef int SElemType ;/* 栈中数据元素类型，栈中保存顶点序号 */typedef struct SElemType dataMAXSIZE; int top;SeqStack;/* 栈的类型定义，顺序栈 */void DFS(AdjMatrix *adj,int i) /*

12、 从顶点i出发进行深度优先搜索，用邻接矩阵adj存储图 */SeqStack *s;int v=i; s=initSeqStack();push(s,v);while(!empty(s)v= top(s);if(!visitedv) visitedv=1; /* 标记v已经访问过 */printf ("输出序号为%d的顶点: %cn",v,adj->vertexv); /* 访问顶点v*/for (j=1;j<=N;j+) /* 依次搜索v的邻接点 */if(adj->edgevj)&&(!visitedj) push(s,j);break

13、;if(j>N) pop(s);6.11 修改Prim算法，使之能在邻接表存储结构上实现求图的最小生成树，并分析其时间复杂度。由于图上的边都带有权值，因此邻接表结构中的边表结点除了保存邻接点的序号外，还要保存边的权值。最小生成树的存储结构采用边集数组。/邻接表存储结构C语言描述如下：#define N 5/* 图的顶点数 */#define MAX 10000/* 设置一个极大数无穷大 */typedef int AdjType;/* 权值类型 */typedef struct node int adjvex;/* 邻接点域 */AdjType weight;/* 权值域 */ stru

14、ct node *next; /* 指针域 */EdgeNode; /* 定义边表结点 */typedef struct VexType vertex; /* 顶点域 */ EdgeNode *link; /* 指针域 */VexNode; /* 定义顶点表结点 */VexNode adjlistN+1;/最小生成树的存储结构typedef struct edge int fromvex; /* 边的始点域 */int endvex; /* 边的终点域 */int weight; /* 边的权值域 */EdgeSetArray; /* 定义边集数组类型 */EdgeSetArray TN;/*

15、 边集数组全局量 */邻接表存储结构上的Prim算法void prim() int i,j,w,min,minest;EdgeNode *p=null;/* 边表结点指针 */EdgeSetArray edtemp;for (i=1;i<=N-1;i+) /* 构造初始边集数组 */ Ti.formvex=1; /* 始点 */Ti.endvex= i+1; /* 终点 */Ti.weight=MAX; /* 权值先赋初值为无穷大 */p=adjlist1.link; /* 访问顶点1的边表，修改权值 */while (p) /* 依次搜索顶点1的邻接点 */j=p-> adjve

16、x;/* 邻接点的序号 */Tj.weight=p-> weight;p=p->next; for (i=1;i<=N-1;i+) /* 求生成树中的第i条边 */ min=MAX;for(j=i;j<=N-1;j+) /* 求当前最短边，下标为minest */if (Tj.weight<min) min=Tj.weight;minest=j; /* Tminest是当前最短的边 */if (i!=minest)/* 将当前最短的边保存到Ti，如果不是则交换 */ edtemp=Tminest; Tminest=Ti; Ti=edtemp; /* 调整边集数组

17、*/k= Ti.endvex;/* k为新加入集合U的顶点 */for(j=i+1;j<=N-1;j+) /* 调整边集数组中的Ti后面的边 */ p=adjlistk.link; /* 访问顶点k的边表，检查权值 */while (p) /* 依次搜索顶点k的邻接点 */if(p-> adjvex= Tj.endvex &&p->weight< Tj.weight) ;Tj.weight= p->weight; Tj.formvex=k;break;/*for-j*/*for-i*/* prim */6.12 以邻接表作为图的存储结构，试写出从源

18、点到其他各顶点的最短路径的Dijkstra算法。/邻接表存储结构C语言描述如下：#define N 5/* 图的顶点数 */#define MAX 10000/* 设置一个极大数无穷大 */typedef int AdjType;/* 权值类型 */typedef struct node int adjvex;/* 邻接点域 */AdjType weight;/* 权值域 */ struct node *next; /* 指针域 */EdgeNode; /* 定义边表结点 */typedef struct VexType vertex; /* 顶点域 */ EdgeNode *link; /*

19、 指针域 */VexNode; /* 定义顶点表结点 */VexNode adjlistN+1;/采用“存路径上前点序号”的方式来存储最短路径，存储结构C语言描述如下：typedef structint prenode; int pathlength;ShortestPath;int flagN+1;ShortestPath spN+1;void dijkstra (int v) /* 求源点v到其余顶点的最短路径及其长度，邻接表存储有向网络 */ int i,j,m,k,min=MAX; EdgeNode *p=null;/* 边表结点指针 */int flagN+1=0; /* 初始化标志数组 */for (i=1;i<=N;i+)/* 初始化路径数组 */ spi.pathlength = MAX;spi.prenode = 0;/* 先假设源点到其余点无路径，即spi.pathlength=MAX，前点序号为0 */flagv=1;/* 源点v的特殊处理： 标志顶点v在集合S中 */spv.pathleng