实验3 图的基本操作.ppt
图 的基本算法实现,实验目的,1 掌握图的结构特征，以及两种存储结构的特点及适用范围2 图的查找，插入和删除算法3 掌握图的深度优先遍历算法4 掌握图的宽度优先遍历算法,实验要求,认真阅读和掌握本实验的程序上机运行程序。保存和打印出程序的运行结果，并结合程序进行分析。按照图的操作需要，重新组合程序并运行，打印出文件清单和运行结果。,实验内容,1 输入图的顶点集合和边集合，建立图的邻接矩阵，并打印。2输入图的顶点集合和边集合，建立图的邻接表，并打印。3查找指定边4删除指定边5插入指定边6图的深度优先遍历算法BFS（递归算法）。7图的深度优先遍历算法DFS（递归算法）。,运行结果：=主菜单=1.打印图的邻接矩阵 2.打印图的邻接表 3.插入边 4.删除边 5.查找边 6.深度优先遍历图 7.宽度优先遍历图 0.结束程序运行=请输入您的选择(0,1,2,3,4,5,6,7)1请输入图的节点编号（如1）：0，1，2，3请继续输入图的边（如1，2）：0，1请继续输入图的边（如1，2）：0，3请继续输入图的边（如1，2）：1，3请继续输入图的边（如1，2）：1，2请继续输入图的边（如1，2）：2，3请继续输入二叉树各结点的编号和对应的值：0，#,=主菜单=1.打印图的邻接矩阵 2.打印图的邻接表 3.插入边 4.删除边 5.查找边 6.深度优先遍历图 7.宽度优先遍历图 0.结束程序运行=请输入您的选择(0,1,2,3,4,5,6,7)0,=主菜单=1.打印图的邻接矩阵 2.打印图的邻接表 3.插入边 4.删除边 5.查找边 6.深度优先遍历图 7.宽度优先遍历图 0.结束程序运行=请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)2,0123,1,3,0,0,2,程序清单,#include#include#define M 100typedef struct enode int AdjVex;T W;struct enode*NextArc;ENode;/边节点 typedef struct graph int Vertices;ENode*A;Graph;/图,/函数原型声明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 v,BOOL*visited)；,/主函数void main()char ch;int k;do printf(nnn);printf(n=主菜单=);printf(nn 1.打印图的邻接矩阵);printf(“nn 2.打印图的邻接表);printf(nn 3.插入边);printf(“nn 4.删除表);printf(“nn 5.查找边);printf(“nn 6.深度优先遍历图);printf(“nn 7.宽度优先遍历图);printf(nn 0.结束程序运行);printf(n=);printf(n 请输入您的选择(0,1,2,3,4,5,6,7);scanf(%d,建立邻接表 函数CreateGraph构造一个有n个顶点，但不包含边的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。,void CreateGraph(Graph*g,int n)int i;g-Vertices=n;g-A=(ENode*)malloc(n*sizeof(ENode*);for(i=0;iAi=NULL;,边的搜索,3,2,0,1,2是否有边？,/搜索边的函数BOOL Exist(Graph g,int u,int v)int n;ENode*p;n=g.Vertices;if(un-1)return FALSE;for(p=g.Au;p,插入边的函数BOOL Add(Graph*g,int u,int v,T w)int n;ENode*p;n=g-Vertices;if(un-1|vn-1|u=v|Exist(*g,u,v)printf(BadInputn);return FALSE;p=NewENode(v,w,g-Au);g-Au=p;return TRUE;,1,3,0,p,3,插入邻接表中由指针Au所指示的单链表的最前面,ENode*NewENode(int vex,T weight,ENode*nextarc)ENode*p;p=(ENode*)malloc(sizeof(ENode);p-AdjVex=vex;p-W=weight;p-NextArc=nextarc;return p;,/删除边的函数BOOL Delete(Graph*g,int u,int v)int n=g-Vertices;ENode*p,*q;if(u-1,0123,1,3,0,P,q=NULL,在由指针Au所指示的单链表中，搜索AdjVex域的值为v的边结点,DFS递归算法（【程序105】）。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;in;i+)if(!visitedi)DFS(g,i,visited);,对V未标记的邻接点嵌套调用DFS函数,对尚未标记的顶点调用DFS函数,2、BFS算法,采用邻接表作为图的存储结构，其宽度优先搜索的程序如下：,#includequeue.hvoid BFS(Graph g,T v,BOOL*visited)ENode*w;T u;Queue q;CreateQueue(,入队,while(!IsEmpty(q)QueueFront(q,u的邻接顶点入队,
