实验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,01 2 3,1 ,3 ,0,0,2 ,程序清单,#include #include #define M 100 typedef 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 ,01 2 3,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算法,采用邻接表作为图的存储结构，其宽度优先搜索的程