图的基本操作及实现的课程设计报告报告.doc

"软件认知实践"报告目 录第1章 题目概述2第1.1节 题目要求2第1.2节 主要难点3第2章 系统流程图4第3章 数据构造和算法5第4章 核心代码分析6第5章 复杂度分析25参考文献25第1章 题目概述第1.1节 题目要求(1)自选存储构造,输入含n个顶点用字符表示顶点和e条边的图G；(2)求每个顶点的度,输出结果；(3)指定任意顶点*为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS)；(4)指定任意顶点*为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS)；(5)输入顶点*,查找图G:假设存在含*的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信 息“无*；(6)判断图G是否是连通图，输出信息“YES/“NO；(7)如果选用的存储构造是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作(2)；反之亦然。第1.2节 主要难点(1)自选存储构造创立一个图：通过用户从键盘敲入的两个数值分别确定图的顶点数和边数，选择邻接矩阵存储构造将图的结点信息存储在一个顺序表中，图的边信息存储在一个二维数组中。(2)求每个顶点的度：1.邻接矩阵存储构造下求每个顶点的度：利用图的邻接矩阵，每个顶点所在行和所在列的边的权值如果存在则该顶点的度+1，依次算出每个顶点的度，并且记录在一个数组中输出。2.邻接表存储构造下求每个顶点的度：定义一个邻接边指针循环指向顶点的邻接边单链表头结点，当结点不空时，该顶点的出度+1,邻接边弧头结点的入度+1，依次求出每个顶点的出度和入度之和就为该顶点的度。(3)图的深度优先遍历：采取邻接矩阵构造，指定任意顶点*为初始顶点1.访问结点v并标记结点v已访问；2.查找结点v的第一个邻接结点w；3.假设结点v的邻接结点w存在，则继续执行，否则算法完毕；4.假设结点w尚未被访问，则递归访问结点w；5.查找结点v的w邻接结点的下一个邻接结点w,转到步骤3。(4)图的广度优先遍历：采取邻接矩阵构造，指定任意顶点*为初始顶点，利用顺序循环队列以保持访问过的结点的顺序1.首先访问初始结点v并标记结点v为已访问；2.结点v入队列；3.当队列非空时则继续执行，否则算法完毕；4.出队列取得队头结点u；5.查找u的第一个邻接结点w；6.假设u的邻接结点w不存在则转到步骤3，否则循环执行以下步骤：6.1假设结点w尚未被访问，则访问结点w并标记结点w为已访问；6.2结点w入队列；6.3查找结点u的w邻接结点的下一个邻接结点w，转到步骤6 。(5)判断有向图的强连通性：采取邻接表构造，在图中寻找一个包含所有顶点且首尾相连的环，假设这样的环存在，则该图为强连通图，否则不为强连通图。(6)用邻接矩阵的信息生成邻接表：定义一个邻接表的边信息构造体，将邻接矩阵的边信息转换成邻接表的边信息存储到邻接边的单链表中。第二章 系统流程图mainPrintCreatGraphMVerticesDepthFirstSearchCreatLGraphMDeleteBroadFirstSearchChaZhaoLianTongLVerticesInsertVerte*InsertEdgeLInsertVerte*LAdjInitiateDeleteVertenDeleteEdgeLInsertEdgeInitiate第3章 数据构造和算法(1)有向图顶点的数据类型DataType 定义如下：typedef int DataType ；(2)邻接矩阵存储构造以下图的构造体定义如下：typedef structSeqList Vertices； int edgeMa*VerticesMa*Vertices；int numOfEdges； AdjMGraph； (3)邻接矩阵存储构造以下图的边信息构造体定义如下：typedef structint row； int col； int weight； RowColWeight；(4)邻接表存储构造以下图的构造体定义如下：typedef struct Node int dest； struct Node *ne*t；Edge； typedef structDataType data； int sorce； Edge *adj； AdjLHeight； typedef structAdjLHeight aMa*Vertices； int numOfVerts； int numOfEdges； AdjLGraph；(5)邻接表存储构造以下图的边信息构造体定义如下：typedef structint row； int col； RowCol；(6)顺序循环队列的构造体定义如下：typedef struct DataType queueMa*QueueSize；int rear；int front；int count；SeqCQueue；(7)顺序表的构造体定义如下：typedef structDataType listMa*Size；int size；SeqList；第四章 核心代码分析源程序存放在八个文件夹中，文件SeqList.h是顺序表的构造体定义和操作函数，文件SeqCQueue.h是顺序循环队列的构造体定义和操作函数，文件AdjMGraph.h是邻接矩阵存储构造以下图的构造体定义和操作函数，文件AdjMGraphCreate.h是邻接矩阵存储构造以下图的创立函数，文件AdjLGraph.h是邻接表存储构造以下图的构造体定义和操作函数，文件AdjLGraphCreate.h是邻接表存储构造以下图的创立函数，文件AdjMGraphTraverse.h是邻接矩阵存储构造以下图的深度优先遍历和广度优先遍历操作函数，文件图的根本操作与实现.c是主函数。(1)/* 文件SeqList.h */typedef structDataType listMa*Size;int size;SeqList;void ListInitiate(SeqList *L)L->size=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,int i,DataType *)int j;if(L->size>=Ma*Size)printf("数组已满无法插入！n");return 0;else if(i<0|i>L->size)printf("参数不合法！n");return 0;elsefor(j=L->size;j>i;i-)L->listj=L->listj-1;L->listi=*;L->size+;return 1;int ListDelete(SeqList *L,int i,DataType *)int j;if(L->size<=0)printf("顺序表已空无数据元素可删！n");return 0;else if(i<0|i>L->size-1)printf("参数i不合法！n");return 0;else*=L->listi;for(j=i+1;j<=L->size-1;j+)L->listj-1=L->listj;L->size-;return 1;int ListGet(SeqList L,int i,DataType *)if(i<0|i>L.size-1)printf("参数i不合法！n");return 0;else*=L.listi;return 1;(2)/* 文件SeqCQueue.h*/typedef struct DataType queueMa*QueueSize;int rear;int front;int count;SeqCQueue;void QueueInitiate(SeqCQueue *Q)Q->rear=0;Q->front =0;Q->count =0;int QueueNotEmpty(SeqCQueue Q)if(Q.count !=0) return 1;else return 0;int QueueAppend(SeqCQueue *Q,DataType *)if(Q->count>0&&Q->rear=Q->front)printf("队列已满无法插入!");return 0;else Q->queue Q->rear=*;Q->rear =(Q->rear +1)%Ma*QueueSize;Q->count +;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q->count =0)printf("队列已空无数据出队列!n");return 0;else*d=Q->queueQ->front; Q->front=(Q->front+1)%Ma*QueueSize;Q->count -;return 1;int QueueGet(SeqCQueue Q,DataType*d)if(Q.count =0)printf("队列已空无数据出队列!n");return 0;else*d=Q.queue Q.front ;return 1;(3)/* 文件AdjMGraph.h*/#include"SeqList.h"typedef structSeqList Vertices; /存放结点的顺序表int edgeMa*VerticesMa*Vertices; /存放边的邻接矩阵int numOfEdges; /边的条数AdjMGraph; /边的构造体定义void Initiate(AdjMGraph *G,int n) /初始化int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)if(i=j)G->edgeij=0;elseG->edgeij=Ma*Weight;G->numOfEdges=0; /边的条数置为0ListInitiate(&G->Vertices); /顺序表初始化void InsertVerte*(AdjMGraph *G,DataType verte*) /在图G中插入结点verte*ListInsert(&G->Vertices,G->Vertices.size,verte*); /顺序表尾插入void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/在图G中插入边<v1,v2>,边<v1,v2>的权为weightif(v1<0|v1>G->Vertices.size|v2<0|v2>G->Vertices.size)printf("参数v1或v2越界出错!n");e*it(1);G->edgev1v2=weight;G->numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2) /在图中删除边<v1,v2>if(v1<0|v1>G->Vertices.size|v2<0|v2>G->Vertices.size|v1=v2)printf("参数v1或v2越界出错!n");e*it(1);if(G->edgev1v2=Ma*Weight|v1=v2)printf("该边不存在!n");e*it(0);G->edgev1v2=Ma*Weight;G->numOfEdges-;void DeleteVerten(AdjMGraph *G,int v) /删除结点vint n=ListLength(G->Vertices),i,j; DataType *;for(i=0;i<n;i+) /计算删除后的边数for(j=0;j<n;j+)if(i=v|j=v)&&G->edgeij>0&&G->edgeij<Ma*Weight)G->numOfEdges-; /计算被删除边for(i=v;i<n;i+) /删除第v行for(j=0;j<n;j+)G->edgeij=G->edgei+1j;for(i=0;i<n;i+) /删除第v列for(j=v;j<n;j+)G->edgeij=G->edgeij+1;ListDelete(&G->Vertices,v,&*); /删除结点vint GetFistVe*(AdjMGraph *G,int v) /在图G中寻找序号为v的结点的第一个邻接结点/如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1int col;if(v<0|v>G->Vertices.size)printf("参数v1越界出错!n");e*it(1);for(col=0;col<G->Vertices.size;col+)if(G->edgevcol>0&&G->edgevcol<Ma*Weight)return col;return -1;int GetNe*tVe*(AdjMGraph*G,int v1,int v2)/在图中寻找v1结点的邻接结点v2的下一个邻接结点/如果这样的结点存在，返回该邻接结点的序号；否则，返回-1/v1和v2都是相应结点的序号int col;if(v1<0|v1>G->Vertices.size|v2<0|v2>G->Vertices.size)printf("参数v1或v2越界出错!n");e*it(1); for(col=v2+1;col<G->Vertices.size;col+)if(G->edgev1col>0&&G->edgev1col<Ma*Weight)return col;return -1;/输出图G的邻接矩阵void Print(AdjMGraph *G) int i,j;for(i=0;i<G->Vertices.size;i+)for(j=0;j<G->Vertices.size;j+)printf("%6d ",G->edgeij);printf("n");/邻接矩阵存储构造下求出每个顶点的度并输出void MVertices(AdjMGraph *G,DataType a) int i,j,m;DataType bMa*Vertices;/用数组b记录相应结点的度for(i=0;i<G->Vertices.size;i+)bi=0; /置0printf("邻接矩阵存储构造以下图的顶点的度为:n");for(m=0;m<G->Vertices.size;m+) /求出每个结点的度for(i=0;i<G->Vertices.size;i+)for(j=0;j<G->Vertices.size;j+)if(i=m&&G->edgeij>0&&G->edgeij<Ma*Weight)/求出邻接矩阵第i行权值存在的边的个数,当边<m,j>存在时,bm加1bm+;if(j=m&&i!=m&&G->edgeij>0&&G->edgeij<Ma*Weight)/求出邻接矩阵第j列权值存在的边的个数,当边<i,m>存在时，bm加1bm+;printf("顶点%d的度为:%dn",am,bm);/查找图G中是否存在点vint ChaZhao(AdjMGraph *G,int v) if(0<=v&&v<G->Vertices.size)printf("存在顶点%dn",v);return 1;elseprintf("不存在顶点%dn",v);return 0;/删除查找到的结点v并删除该结点及与之相关的边void MDelete(AdjMGraph *G,int v)int i;for(i=0;i<G->Vertices.size;i+)if(G->edgevi>0&&G->edgevi<Ma*Weight)/当邻接矩阵的第v行有边<v,i>存在时,删除边<v,i>DeleteEdge(G,v,i);if(G->edgeiv>0&&G->edgeiv<Ma*Weight)/当邻接矩阵的第j行有边<i,v>存在时,删除边<i,v>DeleteEdge(G,i,v);DeleteVerten(G,v);/删除结点v(4)/* 文件AdjMGraphCreate.h*/typedef structint row; /行下标int col; /列下标int weight; /权值RowColWeight; /边信息构造体定义void CreatGraph(AdjMGraph *G,DataType v,int n,RowColWeight E,int e)/在图G中插入n个结点信息v和e条边信息Eint i,k;Initiate(G,n); /结点顺序表初始化for(i=0;i<n;i+)InsertVerte*(G,vi); /结点插入for(k=0;k<e;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight); /边插入(5)/* 文件AdjLGraph.h */邻接表的存储构造typedef struct Node int dest; /邻接边的弧头结点序号struct Node *ne*t;Edge; /邻接边单链表的结点构造体typedef structDataType data; /结点数据元素 int sorce;/邻接边的弧尾结点序号Edge *adj; /邻接边的头指针AdjLHeight; /数组的数据元素类型构造体typedef structAdjLHeight aMa*Vertices; /邻接表数组int numOfVerts; /结点个数int numOfEdges; /边个数AdjLGraph; /邻接表构造体/初始化操作函数void LAdjInitiate(AdjLGraph *G)int i;G->numOfVerts=0;G->numOfEdges=0;for(i=0;i<Ma*Vertices;i+)G->ai.sorce=i;G->ai.adj=NULL;/撤销操作函数void LAdjDestroy(AdjLGraph *G)/撤销图G中的所有邻接边单链表int i;Edge *p,*q;for(i=0;i<G->numOfVerts;i+)p=G->ai.adj;while(p!=NULL)q=p->ne*t;free(p);p=q;/插入结点操作函数void LInsertVerte*(AdjLGraph *G,int i,DataType verte*)/在图G中的第i(0<=i<Ma*Vertices)个位置插入结点数据元素verte*if(i>=0&&i<Ma*Vertices)G->ai.data=verte*; /存储结点数据元素verte*G->numOfVerts+; /个数加1elseprintf("结点越界");/插入边操作函数void LInsertEdge(AdjLGraph *G,int v1,int v2)/在图G中参加边<v1,v2>的信息Edge *p; /定义一个邻接边指针if(v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts)printf("参数v1或v2越界出错");e*it(0);p=(Edge *)malloc(sizeof(Edge); /申请邻接边单链表结点空间p->dest=v2; /置邻接边弧头序号p->ne*t=G->av1.adj; /新结点插入单链表的表头G->av1.adj=p; /头指针指向新的单链表表头G->numOfEdges+; /边数个数加1/删除边操作函数void LDeleteEdge(AdjLGraph *G,int v1,int v2)/删除图G中的边<v1,v2>信息Edge *curr,*pre;if(v1<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts)printf("参数v1或v2越界出错!");e*it(0);pre=NULL;curr=G->av1.adj;while(curr!=NULL&&curr->dest!=v2)/在v1结点的邻接边单链表中查找v2结点pre=curr;curr=curr->ne*t;/删除表示邻接边<v1,v2>的结点if(curr!=NULL&&curr->dest=v2&&pre=NULL) /当邻接边<v1,v2>的结点是单链表的第一个结点时G->av1.adj=curr->ne*t;free(curr);G->numOfEdges-;else if(curr!=NULL&&curr->dest=v2&&pre!=NULL)/当邻接边<v1,v2>的结点不是单链表的第一个结点时pre->ne*t=curr->ne*t;free(curr);G->numOfEdges-;else/当邻接边<v1,v2>结点不存在时printf("边<v1,v2>不存在时");/取第一个邻接结点int LGetFirstVe*(AdjLGraph *G,int v)/取图G中结点v的第一个邻接结点/取到时返回该邻接结点的对应序号，否则返回-1Edge *p;if(v<0|v>G->numOfVerts)printf("参数v1或v2越界出错!");e*it(0);p=G->av.adj;if(p!=NULL)return p->dest; /返回该邻接结点的对应序号elsereturn -1; /返回-1/取下一个邻接结点int LGetNe*tVe*(AdjLGraph *G,int v1,int v2)/取图G中结点v1的邻接结点v2的下一个邻接结点/取到时返回该邻接结点的对应序号，否则返回-1Edge *p;if(v1<0|v1>G->numOfVerts|v2<0|v2>G->numOfVerts)printf("参数v1或v2越界出错!");e*it(0);p=G->av1.adj;while(p!=NULL) /寻找结点v1的邻接结点v2if(p->dest!=v2)p=p->ne*t;continue;elsebreak;p=p->ne*t; /p指向邻接结点v2的下一个邻接结点if(p!=NULL)return p->dest; /返回该邻接结点的对应序号elsereturn -1; /返回-1/邻接表存储下求每个顶点的度并输出结果void LVertices(AdjLGraph *G,DataType a)printf("邻接表存储构造下的图的顶点的度为:n");int OutDegreeMa*Vertices,InDegreeMa*Vertices;/定义一个出度和入度的数组int i;for(i=0;i<G->numOfVerts;i+) /首先将出度和入度数组的每个成员都置0OutDegreei=0;InDegreei=0;Edge *p; /定义一个邻接边指针for(i=0;i<G->numOfVerts;i+)p=G->ai.adj; /指针指向ai的邻接边单链表头结点while(p!=NULL)/当p所指向的邻接边结点不空时OutDegreei+; /出度加1InDegreep->dest+; /邻接边弧头结点的入度加1p=p->ne*t; /p指向下一个邻接边结点for(i=0;i<G->numOfVerts;i+) /输出每个结点的度printf("顶点%d的度为:",ai);printf("%d",OutDegreei+InDegreei); /每个结点的度即出度与入度相加的和printf("n");/判断有向图G是否为强连通图int LianTong(AdjLGraph *G,DataType a) int i,bMa*Vertices,k=0;for(i=0;i<G->numOfVerts;i+)bi=0;Edge *q,*p; /定义一个邻接边指针for(i=0;i<G->numOfVerts;i+)q=G->ai.adj;while(q!=NULL)bi+;q=q->ne*t;for(i=0;i<G->numOfVerts;i+)if(bi=1)k+;p=G->aG->numOfVerts-1.adj;if(k=G->numOfVerts&&p->dest=a0)return 1;elsereturn 0;(6)/* 文件AdjLGraphCreate.h */typedef structint row; /行下标int col; /列下标RowCol; /边信息构造体定义void CreatLGraph(AdjLGraph *G,DataType v,int n,RowCol d,int e)int i,k;LAdjInitiate(G);for(i=0;i<n;i+)LInsertVerte*(G,i,vi);for(k=0;k<e;k+)LInsertEdge(G,dk.row,dk.col);(7)/* 文件AdjMGraphTraverse.h */void Visit(DataType item)printf("%d ",item);void DepthFSearch(AdjMGraph G,int v,int visited,void Visit(DataType item)/连通图G以v为初始结点的访问操作为Visit()的深度优先遍历/数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问int w;Visit(G.Vertices.listv); /访问结点vvisitedv=1; /置已访问标记w=GetFistVe*(&G,v); /取第一个邻接结点while(w!=-1)if(!visitedw)/非0 还未访问DepthFSearch(G,w,visited,Visit);w=GetNe*tVe*(&G,v,w);void DepthFirstSearch(AdjMGraph G,void Visit(DataType item)/非连通图G的访问操作为Visit()的深度优先遍历int i;int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);for(i=0;i<G.Vertices.size;i+)visitedi=0;for(i=0;i<G.Vertices.size;i+)if(!visitedi)DepthFSearch(G,i,visited,Visit);free(visited);#include"SeqCQueue.h" /包括顺序循环队列void BroadFSearch(AdjMGraph G,int v,int visited,void Visit(DataType item)/连通图G以v为初始结点的访问操作为Visit()的广度优先遍历/数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问DataType u,w;SeqCQueue queue;Visit(G.Vertices.listv); /访问结点vvisitedv=1; /置已访问标记QueueInitiate(&queue); /队列初始化QueueAppend(&queue,v); /初始结点v入队列while(QueueNotEmpty(queue) /队列非空时QueueDelete(&queue,&u); /出队列w=GetFistVe*(&G,u); /取结点u的第一个邻接结点while(w!=-1) /邻接结点w存在时if(!visitedw) /假设没有访问过Visit(G.Vertices.listw); /访问结点wvisitedw=1; /置已访问标记QueueAppend(&queue,w); /结点w入队列w=GetNe*tVe*(&G,u,w); /取下一个邻接结点void BroadFirstSearch(AdjMGraph G,void Visit(DataType item)/非连通图G访问操作为Visit()的广度优先遍历int i;int *visited=(int *)malloc(sizeof(int)*G.Vertices.size);for(i=0;i<G.Vertices.size;i+)visitedi=0;for(i=0;i<G.Vertices.size;i+)if(!visitedi)BroadFSearch(G,i,visited,Visit);free(visited);(8)/* 文件图的根本操作与实现.c */#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef int DataType;/定义DataType为整形#define Ma*Size 100#define Ma*Vertices 10#define Ma*Edges 100#define Ma*Wei