【数据结构】关键路径

前端之家收集整理的这篇文章主要介绍了【数据结构】关键路径前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

关键路径

数据结构中 求关键路径,以前写的代码,传给大家看看!


  1. /*
  2. 名称:关键路径
  3. 语言:数据结构C语言版
  4. 编译环境:VC++ 6.0
  5. 日期:2014-3-25
  6. */
  7. #include <stdio.h>
  8. #include <limits.h>
  9. #include <malloc.h>
  10. #include<cstdlib>
  11. #include <string.h>
  12.  
  13. // 求关键路径。实现算法7.13、7.14的程序
  14.  
  15. // 图的邻接表存储表示
  16. #define MAX_NAME 3 // 顶点字符串的最大长度+1
  17. #define MAX_VERTEX_NUM 20
  18. typedef int InfoType; // 存放网的权值
  19. typedef char VertexType[MAX_NAME]; // 字符串类型
  20. typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网}
  21.  
  22. typedef struct ArcNode
  23. {
  24. int adjvex; // 该弧所指向的顶点的位置
  25. struct ArcNode *nextarc; // 指向下一条弧的指针
  26. InfoType *info; // 网的权值指针)
  27. }ArcNode; // 表结点
  28.  
  29. typedef struct VNode
  30. {
  31. VertexType data; // 顶点信息
  32. ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
  33. }VNode,AdjList[MAX_VERTEX_NUM];// 头结点
  34.  
  35. typedef struct
  36. {
  37. AdjList vertices;
  38. int vexnum,arcnum; // 图的当前顶点数和弧数
  39. int kind; // 图的种类标志
  40. }ALGraph;
  41.  
  42. int ve[MAX_VERTEX_NUM]; // 全局变量(用于算法7.13和算法7.14)
  43.  
  44.  
  45. // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
  46. int LocateVex(ALGraph G,VertexType u)
  47. {
  48. int i;
  49. for(i=0;i<G.vexnum;++i)
  50. if(strcmp(u,G.vertices[i].data)==0)
  51. return i;
  52. return -1;
  53. }
  54.  
  55. // 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。
  56. int CreateGraph(ALGraph *G)
  57. {
  58. int i,j,k;
  59. int w; // 权值
  60. VertexType va,vb;
  61. ArcNode *p;
  62. printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
  63. scanf("%d",&(*G).kind);
  64. printf("请输入图的顶点数和边数:(空格)\n");
  65. scanf("%d%d",&(*G).vexnum,&(*G).arcnum);
  66. printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
  67. for(i = 0; i < (*G).vexnum; ++i) // 构造顶点向量
  68. {
  69. scanf("%s",(*G).vertices[i].data);
  70. (*G).vertices[i].firstarc = NULL;
  71. }
  72. if((*G).kind == 1 || (*G).kind == 3) // 网
  73. printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
  74. else // 图
  75. printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
  76. for(k = 0;k < (*G).arcnum; ++k) // 构造表结点链表
  77. {
  78. if((*G).kind==1||(*G).kind==3) // 网
  79. scanf("%d%s%s",&w,va,vb);
  80. else // 图
  81. scanf("%s%s",vb);
  82. i = LocateVex(*G,va); // 弧尾
  83. j = LocateVex(*G,vb); // 弧头
  84. p = (ArcNode*)malloc(sizeof(ArcNode));
  85. p->adjvex = j;
  86. if((*G).kind == 1 || (*G).kind == 3) // 网
  87. {
  88. p->info = (int *)malloc(sizeof(int));
  89. *(p->info) = w;
  90. }
  91. else
  92. p->info = NULL; // 图
  93. p->nextarc = (*G).vertices[i].firstarc; // 插在表头
  94. (*G).vertices[i].firstarc = p;
  95. if((*G).kind >= 2) // 无向图或网,产生第二个表结点
  96. {
  97. p = (ArcNode*)malloc(sizeof(ArcNode));
  98. p->adjvex = i;
  99. if((*G).kind == 3) // 无向网
  100. {
  101. p->info = (int*)malloc(sizeof(int));
  102. *(p->info) = w;
  103. }
  104. else
  105. p->info = NULL; // 无向图
  106. p->nextarc = (*G).vertices[j].firstarc; // 插在表头
  107. (*G).vertices[j].firstarc = p;
  108. }
  109. }
  110. return 1;
  111. }
  112.  
  113. // 输出图的邻接表G。
  114. void Display(ALGraph G)
  115. {
  116. int i;
  117. ArcNode *p;
  118.  
  119. switch(G.kind)
  120. {
  121. case DG: printf("有向图\n");
  122. break;
  123. case DN: printf("有向网\n");
  124. break;
  125. case AG: printf("无向图\n");
  126. break;
  127. case AN: printf("无向网\n");
  128. }
  129. printf("%d个顶点:\n",G.vexnum);
  130. for(i = 0; i < G.vexnum; ++i)
  131. printf("%s ",G.vertices[i].data);
  132. printf("\n%d条弧(边):\n",G.arcnum);
  133. for(i = 0; i < G.vexnum; i++)
  134. {
  135. p = G.vertices[i].firstarc;
  136. while(p)
  137. {
  138. if(G.kind <= 1) // 有向
  139. {
  140. printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
  141. if(G.kind == DN) // 网
  142. printf(":%d ",*(p->info));
  143. }
  144. else // 无向(避免输出两次)
  145. {
  146. if(i < p->adjvex)
  147. {
  148. printf("%s-%s ",G.vertices[p->adjvex].data);
  149. if(G.kind == AN) // 网
  150. printf(":%d ",*(p->info));
  151. }
  152. }
  153. p=p->nextarc;
  154. }
  155. printf("\n");
  156. }
  157. }
  158.  
  159.  
  160. // 求顶点的入度,算法7.12、7.13调用
  161. void FindInDegree(ALGraph G,int indegree[])
  162. {
  163. int i;
  164. ArcNode *p;
  165. for(i=0;i<G.vexnum;i++)
  166. indegree[i]=0; // 赋初值
  167. for(i=0;i<G.vexnum;i++)
  168. {
  169. p=G.vertices[i].firstarc;
  170. while(p)
  171. {
  172. indegree[p->adjvex]++;
  173. p=p->nextarc;
  174. }
  175. }
  176. }
  177.  
  178. typedef int SElemType; // 栈类型
  179.  
  180. #define STACK_INIT_SIZE 10 // 存储空间初始分配量
  181. #define STACKINCREMENT 2 // 存储空间分配增量
  182. // 栈的顺序存储表示 P46
  183. typedef struct SqStack
  184. {
  185. SElemType *base; // 在栈构造之前和销毁之后,base的值为NULL
  186. SElemType *top; // 栈顶指针
  187. int stacksize; // 当前已分配的存储空间,以元素为单位
  188. }SqStack; // 顺序栈
  189.  
  190.  
  191.  
  192. // 构造一个空栈S。
  193. int InitStack(SqStack *S)
  194. {
  195. // 为栈底分配一个指定大小的存储空间
  196. (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  197. if( !(*S).base )
  198. exit(0); // 存储分配失败
  199. (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈
  200. (*S).stacksize = STACK_INIT_SIZE;
  201. return 1;
  202. }
  203.  
  204. // 若栈S为空栈(栈顶与栈底相同的),则返回1,否则返回0。
  205. int StackEmpty(SqStack S)
  206. {
  207. if(S.top == S.base)
  208. return 1;
  209. else
  210. return 0;
  211. }
  212.  
  213. // 插入元素e为新的栈顶元素。
  214. int Push(SqStack *S,SElemType e)
  215. {
  216. if((*S).top - (*S).base >= (*S).stacksize) // 栈满,追加存储空间
  217. {
  218. (*S).base = (SElemType *)realloc((*S).base,((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
  219. if( !(*S).base )
  220. exit(0); // 存储分配失败
  221. (*S).top = (*S).base+(*S).stacksize;
  222. (*S).stacksize += STACKINCREMENT;
  223. }
  224. *((*S).top)++=e;
  225. // 这个等式的++ * 优先级相同,但是它们的运算方式,是自右向左
  226. return 1;
  227. }
  228.  
  229. // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回1;否则返回0。
  230. int Pop(SqStack *S,SElemType *e)
  231. {
  232. if((*S).top == (*S).base)
  233. return 0;
  234. *e = *--(*S).top;
  235. // 这个等式的++ * 优先级相同,但是它们的运算方式,是自右向左
  236. return 1;
  237. }
  238.  
  239. // 算法7.13 P185
  240. // 有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve (全局变量)。
  241. // T为拓扑序列顶点栈,S为零入度顶点栈。若G无回路,则用栈T返回G的一个拓
  242. // 扑序列,且函数值为1,否则为0
  243. int TopologicalOrder(ALGraph G,SqStack *T)
  244. {
  245. int j,k,count,indegree[MAX_VERTEX_NUM];
  246. SqStack S;
  247. ArcNode *p;
  248. FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]
  249. InitStack(&S); // 初始化栈
  250. for(j=0;j<G.vexnum;++j) // 建零入度顶点栈S
  251. if(!indegree[j])
  252. Push(&S,j); // 入度为0者进栈
  253. InitStack(T); // 初始化拓扑序列顶点栈
  254. count=0; // 对输出顶点计数
  255. for(j=0;j<G.vexnum;++j) // 初始化ve[]=0 (最小值)
  256. ve[j]=0;
  257. while(!StackEmpty(S))
  258. {
  259. // 栈不空
  260. Pop(&S,&j);
  261. Push(T,j); // j号顶点入T栈并计数
  262. ++count;
  263. for(p=G.vertices[j].firstarc;p;p=p->nextarc)
  264. {
  265. // 对j号顶点的每个邻接点的入度减1
  266. k=p->adjvex;
  267. if(--indegree[k]==0) // 若入度减为0,则入栈
  268. Push(&S,k);
  269. if(ve[j]+*(p->info)>ve[k])
  270. ve[k]=ve[j]+*(p->info);
  271. }
  272. }
  273. if(count<G.vexnum)
  274. {
  275. printf("此有向网有回路\n");
  276. return 0;
  277. }
  278. else
  279. return 1;
  280. }
  281.  
  282. // 算法7.14 P185
  283. // G为有向网,输出G的各项关键活动
  284. int CriticalPath(ALGraph G)
  285. {
  286. int vl[MAX_VERTEX_NUM];
  287. SqStack T;
  288. int i,ee,el;
  289. ArcNode *p;
  290. char dut,tag;
  291. if(!TopologicalOrder(G,&T)) // 产生有向环
  292. return 0;
  293. j=ve[0];
  294. for(i=1;i<G.vexnum;i++) // j=Max(ve[]) 完成点的值
  295. if(ve[i]>j)
  296. j=ve[i];
  297. for(i=0;i<G.vexnum;i++) // 初始化顶点事件的最迟发生时间(最大值)
  298. vl[i]=j; // 完成点的最早发生时间
  299. while(!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值
  300. for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextarc)
  301. {
  302. k=p->adjvex;
  303. dut=*(p->info); // dut<j,k>
  304. if(vl[k]-dut<vl[j])
  305. vl[j]=vl[k]-dut;
  306. }
  307. printf(" j k dut ee el tag\n");
  308. for(j=0;j<G.vexnum;++j) // 求ee,el和关键活动
  309. for(p=G.vertices[j].firstarc;p;p=p->nextarc)
  310. {
  311. k=p->adjvex;
  312. dut=*(p->info);
  313. ee=ve[j];
  314. el=vl[k]-dut;
  315. tag=(ee==el)?'*':' ';
  316. // 输出关键活动
  317. printf("%2d %2d %3d %3d %3d %c\n",dut,el,tag);
  318. }
  319. printf("关键活动为:\n");
  320. for(j=0;j<G.vexnum;++j) // 同上
  321. for(p=G.vertices[j].firstarc;p;p=p->nextarc)
  322. {
  323. k=p->adjvex;
  324. dut=*(p->info);
  325. if(ve[j]==vl[k]-dut)
  326. // 输出关键活动
  327. printf("%s→%s\n",G.vertices[j].data,G.vertices[k].data);
  328. }
  329. return 1;
  330. }
  331.  
  332. int main()
  333. {
  334. ALGraph h;
  335. printf("请选择有向网\n");
  336. CreateGraph(&h);
  337. Display(h);
  338. CriticalPath(h);
  339. system("pause");
  340. return 0;
  341. }
  342.  
  343. /*
  344. 输出效果
  345.  
  346. 请选择有向网
  347. 请输入图的类型(有向图:0,无向网:3): 1
  348. 请输入图的顶点数和边数:(空格)
  349. 6 8
  350. 请输入6个顶点的值(<3个字符):
  351. v1
  352. v2
  353. v3
  354. v4
  355. v5
  356. v6
  357. 请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):
  358. 3 v1 v2
  359. 2 v1 v3
  360. 2 v2 v4
  361. 3 v2 v5
  362. 4 v3 v4
  363. 3 v3 v6
  364. 2 v4 v6
  365. 1 v5 v6
  366. 有向网
  367. 6个顶点:
  368. v1 v2 v3 v4 v5 v6
  369. 8条弧(边):
  370. v1→v3 :2 v1→v2 :3
  371. v2→v5 :3 v2→v4 :2
  372. v3→v6 :3 v3→v4 :4
  373. v4→v6 :2
  374. v5→v6 :1
  375.  
  376. j k dut ee el tag
  377. 0 2 2 0 0 *
  378. 0 1 3 0 1
  379. 1 4 3 3 4
  380. 1 3 2 3 4
  381. 2 5 3 2 5
  382. 2 3 4 2 2 *
  383. 3 5 2 6 6 *
  384. 4 5 1 6 7
  385. 关键活动为:
  386. v1→v3
  387. v3→v4
  388. v4→v6
  389. 请按任意键继续. . .
  390.  
  391. */

猜你在找的数据结构相关文章