图的应用及其实现

1、.实验六 图的应用及其实现班级：软件091 姓名：郭靖 学号：200900834126 一、实验目的1进一步功固图常用的存储结构。2熟练掌握在图的邻接表实现图的基本操作。3理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。二、实验内容 一.基础题目：题目一：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。测试数据：教材图7.28 题目二：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。 试设计程序实现上述AOE网类型定

2、义和基本操作,完成上述功能。 题目二连通 OR 不连通描述：给定一个无向图，一共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 Topologi

3、calSort(MGraph G)/有向图G采用邻接表存储结构，若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,i

4、nt y)/G为无向图，x、y为图中两节点，删除xy边（3） void DFSearch(MGraph &G, int v, int s,char* PATH)/ G为无向图，查找一条V到S的路径，v为遍历起点，PATH存放路径结点（二）、函数调用及主函数设计主函数只是对函数调用，这里不再列出，详见源码（三）、程序调试及运行结果分析这里只对拓扑排序进行调试运行，其他只贴出结果。1、 运行程序，提示输入定点数和边数：2、 依次按要求输入，得到程序结果：以下是题目三结果： 实验总结四、主要算法流程图及程序清单1、主要算法流程图拓扑排序TopologicalSort算法流程图开始结束T求出各顶点入度

5、将入读为0的顶点入栈Count置0Count+；栈顶元素出栈，存入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 s

6、tatus;typedef int ElemType;typedef struct ArcNode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，ArcNode;typedef struct VNode /表头结点 char vexdata; /存放顶点信息struct ArcNode *firstarc; /指示第一个邻接点VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义AdjList vertices; /顶

7、点向量int vexnum, arcnum; / 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.arcnum ; / 输入顶点数、边数和图类/G.vexnum=5;G.arcnum=7;cout输入顶点:endl;for (int i=0; i

8、 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中的序号ArcNode * pi = new ArcNode; if (!pi)exit(-1);/ 存储分配失败pi - adjvex = j;/ 对弧结点赋邻接点位置pi - nextarc = G.verticesi.fir

9、starc;/头插法，将tv结点插入到第i个单链表中G.verticesi.firstarc = pi;/ 插入链表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

10、&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.vexnum;i+) /初始化每个顶点入度为0indegreei

11、=0;for (i=0;iadjvex+;G.verticesi.firstarc=G.verticesi.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)

12、int k=p-adjvex;indegreek-;if (!indegreek)Push(S,k);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#defi

13、ne INCREMENT 10typedef enum DG, DN, UDG, UDN GraphKind;typedef int status;typedef int ElemType;typedef struct ArcNode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，int info;ArcNode;typedef struct VNode /表头结点 char vexdata; /存放顶点信息struct ArcNode *firstarc; /指

14、示第一个邻接点VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义AdjList vertices; /顶点向量int vexnum, arcnum; / 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

15、 G.arcnum ; / 输入顶点数、边数和图类/G.vexnum=5;G.arcnum=7;cout输入顶点:endl;for (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中的序号ArcNode * pi = new ArcNode

16、; if (!pi)exit(-1);/ 存储分配失败pi - adjvex = j;/ 对弧结点赋邻接点位置pi - nextarc = 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

17、.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.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;

18、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.verticesi.firstarc-nextarc;int ve20;int vl20;status TopologcalOrder(MGraph G,SqStack &T)int indegree20;FindInDegree(G,indegree);SqStack S;InitStack(S);for (i

19、nt i=0;iG.vexnum;i+)if (!indegreei)Push(S,i);InitStack(T);int count=0,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;fo

20、r (int i=0;inextarc)k=p-adjvex;dut=p-info;if (vlk-dutvlj)vlj=vlk-dut;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_

21、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;typedef struct ArcNode / 弧结点 int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置struct ArcNode *nextarc; /链域，指示依附于vi的下一条边或弧的结点，ArcNode;typedef

22、struct VNode /表头结点 char vexdata; /存放顶点信息struct ArcNode *firstarc; /指示第一个邻接点VNode,AdjListMAX_VERTEX_NUM;typedef struct /图的结构定义AdjList vertices; /顶点向量int vexnum, arcnum; / 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

23、 -1;void CreateGraph(MGraph &G)/ 生成图G的存储结构-邻接表 无向图cout输入顶点数、边数: G.vexnum G.arcnum ; / 输入顶点数、边数和图类/G.vexnum=5;G.arcnum=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,

24、 tv);/ 确定sv和tv在G中位置，即顶点在G.vertices中的序号ArcNode * pi = new ArcNode; ArcNode * pj = new ArcNode; 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.f

25、irstarc;G.verticesj.firstarc = pj;cout构造成功!adjvex!=y)q=p;p=p-nextarc;if(!p)return 0;if (p=G.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

26、.verticesy.firstarc=p-nextarc;elseq-nextarc=p-nextarc;delete p;return 1;typedef struct Nodeint data;struct Node *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;bool visited10;ArcNode *nextnode=NULL;/全局变量/得到i号顶点的第一个邻接点int FirstAdjVex(MGraph &g,int i)ArcNode *p;p=g.verticesi.first