实验3图的基本操作课件

1、图 的基本算法实现实验目的1 掌握图的结构特征，以及两种存储结构的特点及适用范围2 图的查找，插入和删除算法3 掌握图的深度优先遍历算法4 掌握图的宽度优先遍历算法实验要求认真阅读和掌握本实验的程序上机运行程序。保存和打印出程序的运行结果，并结合程序进行分析。按照图的操作需要，重新组合程序并运行，打印出文件清单和运行结果。实验内容1 输入图的顶点集合和边集合，建立图的邻接矩阵，并打印。2输入图的顶点集合和边集合，建立图的邻接表，并打印。3查找指定边4删除指定边5插入指定边6图的深度优先遍历算法BFS （递归算法） 。7图的深度优先遍历算法DFS（递归算法） 。运行结果：=主菜单= 1.打印图的

2、邻接矩阵 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.结束程序运

3、行=请输入您的选择(0,1,2,3,4,5,6,7) 00132(a) 无向图G1(d) 图G1的邻接矩阵 0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0=主菜单= 1.打印图的邻接矩阵 2.打印图的邻接表 3.插入边 4.删除边 5.查找边 6.深度优先遍历图 7.宽度优先遍历图 0.结束程序运行=请输入您的选择(0,1,2,3,4,5,6,7,8,9,10) 201320123 1 3 0 0 2 程序清单 #include#include#define M 100typedef struct enode int AdjVex; T W; struc

4、t 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 BF

5、S(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

6、,4,5,6,7); scanf(%d,&k);建立邻接表 函数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; 01.n-1.边的搜索01232 1 0 3 1 3 1 3 2 0 1,2是否有边？/搜索边的函数BOOL Exist(Graph g, int u, int v) int n; E

7、Node* p; n=g.Vertices; if(un-1) return FALSE; for(p=g.Au; p&p-AdjVex!=v; p=p-NextArc; if (!p) return FALSE; 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-

8、Au=p; return TRUE; 0123 1 3 0 0 2 p30132插入邻接表中由指针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 & uAu; q

9、=NULL; while (p& p-AdjVex!=v) q=p; p=p-NextArc; if (p) if (q) q-NextArc=p-NextArc; else g-Au=p-NextArc; free(p); return TRUE; printf(BadInputn); return FALSE; 0123 1 3 0 0 2 01323Pq=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+)