《图的应用与实现.doc》由会员分享，可在线阅读，更多相关《图的应用与实现.doc（15页珍藏版）》请在三一办公上搜索。
1、 实验六 图的应用及其实现一、实验目的1进一步功固图常用的存储结构。2熟练掌握在图的邻接表实现图的基本操作。3理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。二、实验内容 一.基础题目：题目一：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。测试数据：教材图7.28 题目二：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 题目二连通 OR 不连通描述：给
2、定一个无向图，一共n个点，请编写一个程序实现两种操作：D x y 从原图中删除连接x，y节点的边。Q x y 询问x，y节点是否连通输入第一行两个数n,m（5=n=40000,1=m=100000）接下来m行，每行一对整数 x y （x,y=n）,表示x,y之间有边相连。保证没有重复的边。接下来一行一个整数 q（q=100000）以下q行每行一种操作，保证不会有非法删除。输出按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D三、实验步骤(一)、数据结构与核心算法的设计描述1、 题目一（1） status TopologicalSort(MGraph G)/有向图G采用邻接表存储结构，
3、若G无回路，则输出G的定带你的一个拓扑排序序列并返回OK，否则返回ERROR2、 题目二（1） status TopologcalOrder(MGraph G,SqStack &T)/有向网G采取邻接表存储，求个顶点时间最早发生时间ve，T为拓扑排序顶点栈，S为零入度顶点栈，若G无回路，则返回G的一个拓扑排序，函数数值为OK，否则返回ERROR（2） status CriticalPath(MGraph G)/G为有向网，输出G的各项关键活动3、 题目五(1) status Deleteside(MGraph &G,int x,int y)/G为无向图，x、y为图中两节点，删除xy边（3） v
4、oid DFSearch(MGraph &G, int v, int s,char* PATH)/G为无向图，查找一条V到S的路径，v为遍历起点，PATH存放路径结点（二）、函数调用及主函数设计主函数只是对函数调用，这里不再列出，详见源码（三）、程序调试及运行结果分析这里只对拓扑排序进行调试运行，其他只贴出结果。1、 运行程序，提示输入定点数和边数：2、 依次按要求输入，得到程序结果：以下是题目三结果： 实验总结四、主要算法流程图及程序清单1、主要算法流程图拓扑排序TopologicalSort算法流程图开始结束T求出各顶点入度将入读为0的顶点入栈Count置0Count+；栈顶元素出栈，存入
5、iP =G.verticesi.firstarc是否栈空？P！=null对i号顶点每个邻接点减1将入读为0的顶点入栈FFT2、程序清单 题目一源码：#include using namespace std;#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE 50#define INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int status;typedef int ElemType;typede
6、f struct Arode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct Arode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，Arode;typedef struct VNode /表头结点 char vexdata; /存放顶点信息struct Arode *firstarc; /指示第一个邻接点VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义AdjList vertices; /顶点向量int vexnum, arum; / GraphKind kind=0;
7、/ 图的种类标志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return -1;void CreateGraph(MGraph &G)/ 生成图G的存储结构-邻接表cout输入顶点数、边数: G.vexnum G.arum ; / 输入顶点数、边数和图类/G.vexnum=5;G.arum=7;cout输入顶点:endl;for (int i=0; i G.verticesi.vexdata; / 输入顶点G.verticesi.firstar
8、c = NULL; cout输入各边:endl;for (int k=0; ksv tv; / 输入一条边（弧）的始点和终点i = LocateVex(G, sv); int j = LocateVex(G, tv);/ 确定sv和tv在G中位置，即顶点在G.vertices中的序号Arode * pi = new Arode; if (!pi)exit(-1);/ 存储分配失败pi - adjvex = j;/ 对弧结点赋邻接点位置pi - nextarc = G.verticesi.firstarc;/头插法，将tv结点插入到第i个单链表中G.verticesi.firstarc = pi
9、;/ 插入链表G.verticesi cout构造成功!=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType);if (!S.base)return OVERFLOW;S.top=S.base+INCREMENT;S.stacksize+=INCREMENT;*S.top=e;S.top+;return OK;/出栈status Pop(SqStack &S,ElemType &e)/获得S栈顶元素,复制给eif (S.top=S.base) return ERROR;S.to
10、p-;e=*S.top;return OK;/判空status IsEmpty(SqStack &S)/判断栈S是否为空if (S.top=S.base)return ERROR;elsereturn OK;/清空栈status Clearstack(SqStack &S)S.top=S.base;return OK;void FindInDegree(MGraph G,int *indegree)for (int i=0;iG.vexnum;i+) /初始化每个顶点入度为0indegreei=0;for (i=0;iadjvex+;G.verticesi.firstarc=G.vertice
11、si.firstarc-nextarc;/*-AOV拓扑排序序列-*/status TopologicalSort(MGraph G)int indegree20;FindInDegree(G,indegree);SqStack S;InitStack(S);for (int i=0;iG.vexnum;i+)if (!indegreei)Push(S,i);int count=0;while(IsEmpty(S)Pop(S,i);coutG.verticesi.vexdatanextarc)int k=p-adjvex;indegreek-;if (!indegreek)Push(S,k);
12、if (countG.vexnum)return ERROR;else return OK;/*main()*/int main()MGraph G;CreateGraph(G);TopologicalSort(G);return 0;题目二源码：#include using namespace std;#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE 50#define INCREMENT 10typedef enum DG, DN, UDG, UDN GraphK
13、ind;typedef int status;typedef int ElemType;typedef struct Arode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct Arode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，int info;Arode;typedef struct VNode /表头结点 char vexdata; /存放顶点信息struct Arode *firstarc; /指示第一个邻接点VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义Ad
14、jList vertices; /顶点向量int vexnum, arum; / GraphKind kind=0; / 图的种类标志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return -1;void CreateGraph(MGraph &G)/ 生成图G的存储结构-邻接表cout输入顶点数、边数: G.vexnum G.arum ; / 输入顶点数、边数和图类/G.vexnum=5;G.arum=7;cout输入顶点:endl;for
15、 (int i=0; i G.verticesi.vexdata; / 输入顶点G.verticesi.firstarc = NULL; cout输入各边和权值:endl;for (int k=0; ksv tvpower; / 输入一条边（弧）的始点和终点i = LocateVex(G, sv); int j = LocateVex(G, tv);/ 确定sv和tv在G中位置，即顶点在G.vertices中的序号Arode * pi = new Arode; if (!pi)exit(-1);/ 存储分配失败pi - adjvex = j;/ 对弧结点赋邻接点位置pi - nextarc =
16、 G.verticesi.firstarc;/头插法，将tv结点插入到第i个单链表中G.verticesi.firstarc = pi;/ 插入链表G.verticesi pi-info=power;cout构造成功!=S.stacksize)S.base=(ElemType*)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType);if (!S.base)return OVERFLOW;S.top=S.base+INCREMENT;S.stacksize+=INCREMENT;*S.top=e;S.top+;return OK;/出栈s
17、tatus Pop(SqStack &S,ElemType &e)/获得S栈顶元素,复制给eif (S.top=S.base) return ERROR;S.top-;e=*S.top;return OK;/判空status IsEmpty(SqStack &S)/判断栈S是否为空if (S.top=S.base)return ERROR;elsereturn OK;/清空栈status Clearstack(SqStack &S)S.top=S.base;return OK;void FindInDegree(MGraph G,int *indegree)for (int i=0;iG.ve
18、xnum;i+) /初始化每个顶点入度为0indegreei=0;for (i=0;iadjvex+;G.verticesi.firstarc=G.verticesi.firstarc-nextarc;int ve20;int vl20;status TopologcalOrder(MGraph G,SqStack &T)int indegree20;FindInDegree(G,indegree);SqStack S;InitStack(S);for (int i=0;iG.vexnum;i+)if (!indegreei)Push(S,i);InitStack(T);int count=0
19、,j=0,k=0;for (i=0;inextarc)k=p-adjvex;indegreek-;if (indegree=0)Push(S,k);if (vej+p-infovek)vek=vej+p-info;if (countG.vexnum)return ERROR;elsereturn OK;status CriticalPath(MGraph G)SqStack T;if (!TopologcalOrder(G,T)return ERROR;for (int i=0;inextarc)k=p-adjvex;dut=p-info;if (vlk-dutvlj)vlj=vlk-dut;
20、for (j=0;jnextarc)k=p-adjvex;dut=p-info;int ee=vej;int el=vlk-dut;char tag=(ee=el)?*: ;coutjkduteeeltagendl;return OK;int main()MGraph G;CreateGraph(G);CriticalPath(G);return 0;题目三源码：#include using namespace std;#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW -1#define INIT_SIZE
21、 50#define INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int status;typedef int ElemType;typedef struct Arode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct Arode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，Arode;typedef struct VNode /表头结点 char vexdata; /存放顶点信息struct Arode *firstarc; /指示第一个邻接点VN
22、ode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义AdjList vertices; /顶点向量int vexnum, arum; / GraphKind kind=0; / 图的种类标志 MGraph;int LocateVex(MGraph &G,char v)for(int i=0;iG.vexnum;i+)if(G.verticesi.vexdata=v)return i;return -1;void CreateGraph(MGraph &G)/ 生成图G的存储结构-邻接表 无向图cout输入顶点数、边数: G.vexnum G.arum
23、 ; / 输入顶点数、边数和图类/G.vexnum=5;G.arum=7;cout输入顶点:endl;for (int i=0; i G.verticesi.vexdata; / 输入顶点G.verticesi.firstarc = NULL; cout输入各边:endl;for (int k=0; ksv tv; / 输入一条边（弧）的始点和终点i = LocateVex(G, sv); int j = LocateVex(G, tv);/ 确定sv和tv在G中位置，即顶点在G.vertices中的序号Arode * pi = new Arode; Arode * pj = new Arod
24、e; if (!pi)exit(-1);if (!pj)exit(-1);pi - adjvex = j;/ 对弧结点赋邻接点位置pi - nextarc = G.verticesi.firstarc;/头插法，将tv结点插入到第i个单链表中G.verticesi.firstarc = pi;/ 插入链表G.verticesi pj - adjvex = i;pj - nextarc = G.verticesj.firstarc;G.verticesj.firstarc = pj;cout构造成功!adjvex!=y)q=p;p=p-nextarc;if(!p)return 0;if (p=G
25、.verticesx.firstarc)G.verticesx.firstarc=p-nextarc;elseq-nextarc=p-nextarc;delete p;p=G.verticesy.firstarc;q=G.verticesy.firstarc;while(p&p-adjvex!=x)q=p;p=p-nextarc;if(!p)return 0;if (p=G.verticesy.firstarc)G.verticesy.firstarc=p-nextarc;elseq-nextarc=p-nextarc;delete p;return 1;typedef struct Node
26、int data;struct Node *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;bool visited10;Arode *nextnode=NULL;/全局变量/得到i号顶点的第一个邻接点int FirstAdjVex(MGraph &g,int i)Arode *p;p=g.verticesi.firstarc;if(!p) return -1;return(p-adjvex);/得到i号顶点的下一个邻接点int NextAdjVex(MGraph &g,int i,int w)
27、if(!w) return -1;Arode *p;p=g.verticesi.firstarc;while (p&p-adjvex!=w)p=p-nextarc;if (!p|!p-nextarc)return -1;int m=p-nextarc-adjvex;return m;int pathcount=0;void Append(MGraph G,char *PATH,int v)PATHpathcount=G.verticesv.vexdata;pathcount+;void Delete(char *PATH,int v)pathcount-;bool found=false;vo
28、id DFSearch(MGraph &G, int v, int s,char* PATH)if (found)return;visitedv = true;/ 访问第 v 个顶点，并置访问标志Append(G,PATH, v);/把顶点v加入路径for (int w=FirstAdjVex(G, v);w!=-1&!found;w=NextAdjVex(G,v,w) if (w=s)found =true;Append(G,PATH, w);return;/exit(1);/找到退出else if(!visitedw)DFSearch(G,w, s,PATH);/加入w /end forif (!found)Delete(PATH,v);int main()MGraph G; CreateGraph(G);/ Deleteside(G,0,2);Deleteside(G,0,1);char PATH20;DFSearch(G,0,2,PATH);if (found)coutcendl;elsecoutdendl;return 0;15 / 15
