《最新实验3 图的基本操作PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新实验3 图的基本操作PPT课件.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验实验3 图的基本操作图的基本操作实验目的1 掌握图的结构特征，以及两种存储结构的特点及适用范围2 图的查找，插入和删除算法3 掌握图的深度优先遍历算法4 掌握图的宽度优先遍历算法/函数原型声明BOOL Exist(Graph g,int u,int v)；BOOL Add(Graph*g,int u,int v,T w)；ENode*NewENode(int vex,T weight,ENode*nextarc)；BOOL Delete(Graph*g,int u,int v)；void DFS(Graph g,int v,BOOL*visited)；void BFS(Graph g,T
2、v,BOOL*visited)；/主函数主函数 void main()void main()char ch;char ch;int k;int k;do do printf(nnn);printf(nnn);printf(n=printf(n=主菜单主菜单=);=);printf(nn 1.printf(nn 1.打印图的邻接矩阵打印图的邻接矩阵););printf(“nn 2.printf(“nn 2.打印图的邻接表打印图的邻接表););printf(nn 3.printf(nn 3.插入边插入边););printf(“nn 4.printf(“nn 4.删除表删除表););printf(“
3、nn 5.printf(“nn 5.查找边查找边););printf(“nn 6.printf(“nn 6.深度优先遍历图深度优先遍历图););printf(“nn 7.printf(“nn 7.宽度优先遍历图宽度优先遍历图););printf(nn 0.printf(nn 0.结束程序运行结束程序运行););printf(n=);printf(n=);printf(n printf(n 请输入您的选择请输入您的选择(0,1,2,3,4,5,6,7);(0,1,2,3,4,5,6,7);scanf(%d,&k);scanf(%d,&k);建立邻接表建立邻接表 函数函数CreateGraphCr
4、eateGraph构造一个有构造一个有n n个顶点，但个顶点，但不包含边不包含边的有向图。由于图的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。void CreateGraph(Graph*g,int n)void CreateGraph(Graph*g,int n)int i;int i;g-Vertices=n;g-Vertices=n;g-A=(ENode*)malloc(n*sizeof(ENode*);g-A=(ENode*)malloc(n*sizeof(ENode*);for(i=0;iAi
5、=for(i=0;iAi=NULLNULL;0 01 1.n-1n-1.边的搜索边的搜索0 01 12 23 32 2 1 1 0 0 3 3 1 1 3 3 1 1 3 3 2 2 0 0 1,21,2是否有边？是否有边？/搜索边的函数搜索边的函数BOOL Exist(Graph g,int u,int v)BOOL Exist(Graph g,int u,int v)int n;int n;ENode*p;ENode*p;n=g.Vertices;n=g.Vertices;if(if(u0un-1un-1)return FALSE;)return FALSE;for(p=g.Au;p&p-
6、AdjVex!=v;for(p=g.Au;p&p-AdjVex!=v;p=p-NextArc;p=p-NextArc;if(!p)return FALSE;if(!p)return FALSE;return TRUE;return TRUE;插入边的函数插入边的函数BOOL Add(Graph*g,int u,int v,T w)int n;ENode*p;n=g-Vertices;if(u0|vn-1|vn-1|u=v|Exist(*g,u,v)printf(BadInputn);return FALSE;p=NewENode(v,w,g-Au);g-Au=p;return TRUE;0 0
7、1 12 23 3 1 1 3 3 0 0 0 0 2 2 p p3 30 01 13 32 2插入邻接表中由指针插入邻接表中由指针AuAu所所指示的单链表的最前面指示的单链表的最前面ENode*NewENode(int vex,T weight,ENode*nextarc)ENode*NewENode(int vex,T weight,ENode*nextarc)ENode*p;ENode*p;p=(ENode*)malloc(sizeof(ENode);p=(ENode*)malloc(sizeof(ENode);p-AdjVex=vex;p-AdjVex=vex;p-W=weight;p
8、-W=weight;p-NextArc=nextarc;p-NextArc=nextarc;return p;return p;/删除边的函数删除边的函数BOOL Delete(Graph*g,int u,int v)BOOL Delete(Graph*g,int u,int v)int n=g-Vertices;int n=g-Vertices;ENode*p,*q;ENode*p,*q;if(u-1&u-1&uAu;q=NULL;p=g-Au;q=NULL;while(p&p-AdjVex!=v)while(p&p-AdjVex!=v)q=p;p=p-NextArc;q=p;p=p-Nex
9、tArc;if(p)if(p)if(q)q-NextArc=p-NextArc;if(q)q-NextArc=p-NextArc;else g-Au=p-NextArc;else g-Au=p-NextArc;free(p);free(p);return TRUE;return TRUE;printf(BadInputn);printf(BadInputn);return FALSE;return FALSE;0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 0 01 13 32 23 3P Pq=NULLq=NULL在由指针在由指针AuAu所指示的单所指示的单链表中，搜索链表
10、中，搜索AdjVexAdjVex域的域的值为值为v v的边结点的边结点DFSDFS递归算法（递归算法（【程序程序10105 5】）。void DFS(Graph g,int v,BOOL*visited)ENode*w;visitedv=TRUE;printf(%d ,v);for(w=g.Av;w;w=w-NextArc)if(!visitedw-AdjVex)DFS(g,w-AdjVex,visited);void Traversal_DFS(Graph g)BOOL visitedMaxSize;int i,n=g.Vertices;for(i=0;in;i+)visitedi=FALSE;for(i=0;iNextArc)for(w=g.Au;w;w=w-NextArc)if(!visitedw-AdjVex)if(!visitedw-AdjVex)printf(%d ,w-AdjVex);printf(%d ,w-AdjVex);visitedw-AdjVex=TRUE;visitedw-AdjVex=TRUE;Append(&q,w-AdjVex);Append(&q,w-AdjVex);u u的邻接顶点入队的邻接顶点入队访问队头元素访问队头元素u u的所有未访问过的所有未访问过的邻接点的邻接点