"图遍历的演示程序设计与实现"
一个空图); DestroyGraph(销毁图); LocateVex(获取节点在图中的位置); GetVex(获取节点的值); PutVex(修改节点的值); FirstAdjVex(获取节点的第一个邻接节点); NextAdjVex(获取节点的下一个邻接节点); InsertVex(插入节点); DeleteVex(删除节点); InsertArc(插入边); DeleteArc(删除边); DFSTraverse(深度优先遍历); BFSTraverse(广度优先遍历); Prim(最小生成树Prim算法); Kruskal(最小生成树Kruskal算法); ShortestPath(最短路径Dijkstra算法); BreedthFirstSearch(广度优先搜索); DepthFirstSearch(深度优先搜索); } 2、设计链表结构体表示无向图的邻接表,每个顶点结点都包含一个指向该顶点第一个邻接点的指针域,以及一个指向该顶点边表的指针域,边表包含边表结点,每个边表结点都包含终点在顶点链表中的位置和指向下一个邻接点的指针域; 3、设计栈的结构,包含一个数组用于存放栈中的元素,以及一个指向栈顶元素的指针; 4、设定用户界面,可以让用户输入相应的指令以及图的相关信息,例如起点节点、终点节点等; 5、根据用户输入的指令和图的相关信息,调用相应的函数来完成相应的操作; 6、设计算法,首先设计深度优先和广度优先遍历的算法,然后根据用户输入的起点节点,利用栈分别实现深度优先和广度优先遍历,并输出遍历的结点序列;接着设计Prim和Kruskal算法来生成最小生成树,利用凹入表打印生成树的边集;最后设计Dijkstra算法来计算最短路径,利用广度优先搜索和深度优先搜索来求出从一个结点到另外一个结点,但不经过另外一个指定结点的所有简单路径; 三、详细设计 1、图的抽象数据类型定义 1. typedef enum { DG, DN, UDG, UDN } GraphKind; 2. typedef char VertexType; 3. typedef int ArcType; /* 定义图的邻接表存储结构 */ typedef struct ArcNode { int adjvex; //该弧所指向的顶点在顶点表中的位置 struct ArcNode *nextarc; //指向下一个邻接点的指针 int weight; //弧的权值 } ArcNode; /* 定义顶点表结点 */ typedef struct VexNode { VertexType data; //存储顶点的数据 结构ArcNode *firstarc; //指向第一个邻接点 ArcNode *head; //指向第一条依附该顶点的边 struct VexNode *next; //指向下一个顶点 } VexNode, AdjList[MAXVEX]; typedef struct { AdjList vertices; //顶点表 ArcNode arcs[MAXVEX][MAXVEX]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类 } ALGraph; 2、初始化图的函数定义 void InitGraph(ALGraph *G) { int i, j; for (i = 0; i < G->vexnum; i++) { G->vertices[i].firstarc = NULL; } for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->arcs[i][j].adjvex = 0; G->arcs[i][j].nextarc = NULL; G->arcs[i][j].weight = INT_MAX; } } } 3、创建图的函数定义 void CreateGraph(ALGraph *G) { FILE *fp; int i, j, k; printf("请输入图的种类:0-有向图(DG) 1-有向网(DN) 2-无向图(UDG) 3-无向网(UDN):"); scanf("%d", &(G->kind)); printf("请输入图的顶点数:"); scanf("%d", &(G->vexnum)); ... 详细设计有很多内容,根据要求就做可以了
剩余16页未读,继续阅读
- 粉丝: 92
- 资源: 9356
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx