《实验3图的基本操作.ppt》由会员分享，可在线阅读，更多相关《实验3图的基本操作.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图图 的基本算法实现实验目的1 掌握图的结构特征，以及两种存储结构的特点及适用范围2 图的查找，插入和删除算法3 掌握图的深度优先遍历算法4 掌握图的宽度优先遍历算法实验要求认真阅读和掌握本实验的程序上机运行程序。保存和打印出程序的运行结果，并结合程序进行分析。按照图的操作需要，重新组合程序并运行，打印出文件清单和运行结果。实验内容1 1 输入图的顶点集合和边集合，输入图的顶点集合和边集合，建立图的邻接矩阵，建立图的邻接矩阵，并打印并打印。2 2输入图的顶点集合和边集合，输入图的顶点集合和边集合，建立图的邻接表，并建立图的邻接表，并打印打印。3 3查找查找指定边指定边4 4删除删除指定边指定边
2、5 5插入插入指定边指定边6 6图的深度优先遍历算法图的深度优先遍历算法BFS BFS（递归算法）（递归算法）。7 7图的深度优先遍历算法图的深度优先遍历算法DFSDFS（递归算法）（递归算法）。运行结果：运行结果：=主菜单主菜单=1.1.打印图的邻接矩阵打印图的邻接矩阵 2.2.打印图的邻接表打印图的邻接表 3.3.插入边插入边 4.4.删除边删除边 5.5.查找边查找边 6.6.深度优先遍历图深度优先遍历图 7.7.宽度优先遍历图宽度优先遍历图 0.0.结束程序运行结束程序运行=请输入您的选择请输入您的选择(0,1,2,3,4,5,6,7)1(0,1,2,3,4,5,6,7)1 请输入图的
3、节点编号（如请输入图的节点编号（如1 1）：）：0 0，1 1，2 2，3 3 请继续输入图的边（如请继续输入图的边（如1 1，2 2）：0 0，1 1 请继续输入图的边（如请继续输入图的边（如1 1，2 2）：0 0，3 3 请继续输入图的边（如请继续输入图的边（如1 1，2 2）：1 1，3 3 请继续输入图的边（如请继续输入图的边（如1 1，2 2）：1 1，2 2 请继续输入图的边（如请继续输入图的边（如1 1，2 2）：2 2，3 3 请继续输入二叉树各结点的编号和对应的值：请继续输入二叉树各结点的编号和对应的值：0 0，#=主菜单主菜单=1.1.打印图的邻接矩阵打印图的邻接矩阵 2
4、.2.打印图的邻接表打印图的邻接表 3.3.插入边插入边 4.4.删除边删除边 5.5.查找边查找边 6.6.深度优先遍历图深度优先遍历图 7.7.宽度优先遍历图宽度优先遍历图 0.0.结束程序运行结束程序运行=请输入您的选择请输入您的选择(0,1,2,3,4,5,6,7)0(0,1,2,3,4,5,6,7)00 01 13 32 2(a)(a)无向图无向图G G1 1(d)(d)图图G G1 1的邻接矩阵的邻接矩阵 0 1 2 30 1 2 30 0 1 0 10 0 1 0 11 1 0 1 11 1 0 1 12 0 1 0 12 0 1 0 13 1 1 1 03 1 1 1 0=主菜
5、单主菜单=1.1.打印图的邻接矩阵打印图的邻接矩阵 2.2.打印图的邻接表打印图的邻接表 3.3.插入边插入边 4.4.删除边删除边 5.5.查找边查找边 6.6.深度优先遍历图深度优先遍历图 7.7.宽度优先遍历图宽度优先遍历图 0.0.结束程序运行结束程序运行=请输入您的选择请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)2(0,1,2,3,4,5,6,7,8,9,10)20 01 13 32 20 01 12 23 3 1 1 3 3 0 0 0 0 2 2 程序清单#include#include#include#include#define M 100#define M
6、 100typedef struct enodetypedef struct enode int AdjVex;int AdjVex;T W;T W;struct enode*NextArc;struct enode*NextArc;ENode;ENode;/边节点边节点边节点边节点 typedef struct graph typedef struct graph int Vertices;int Vertices;ENode*A;ENode*A;Graph;Graph;/图图图图/函数原型声明BOOL Exist(Graph g,int u,int v)；BOOL Add(Graph*g,
7、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 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.p
8、rintf(nn 1.打印图的邻接矩阵打印图的邻接矩阵););printf(“nn 2.printf(“nn 2.打印图的邻接表打印图的邻接表););printf(nn 3.printf(nn 3.插入边插入边););printf(“nn 4.printf(“nn 4.删除表删除表););printf(“nn 5.printf(“nn 5.查找边查找边););printf(“nn 6.printf(“nn 6.深度优先遍历图深度优先遍历图););printf(“nn 7.printf(“nn 7.宽度优先遍历图宽度优先遍历图););printf(nn 0.printf(nn 0.结束程序运行结
9、束程序运行););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);建立邻接表建立邻接表 函数函数CreateGraphCreateGraph构造一个有构造一个有n n个顶点，但个顶点，但不包含边不包含边的有向图。由于图的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。void CreateGraph(Graph*g,int n
10、)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=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
11、 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-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
12、*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 01 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*New
13、ENode(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-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=
14、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-NextArc;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;pr
15、intf(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所指示的单所指示的单链表中，搜索链表中，搜索AdjVexAdjVex域的域的值为值为v v的边结点的边结点DFSDFS递归算法（递归算法（【程序程序10105 5】）。void DFS(Graph g,int v,BOOL*visited)ENode*w;visitedv=TRUE;printf(%d ,v);for(w=g.A
16、v;w;w=w-NextArc)if(!visitedw-AdjVex)DFS(g,w-AdjVex,visited);void Traversal_DFS(Graph g)BOOL visitedMaxSize;int i,n=;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的所有未访问过的所有未访问过的邻接点的邻接点