数据结构及算法讲解.ppt

1.5.2算法逐步求精 确定算法： (1)穷举法;(2)试探法(3)贪心法 贪心算法的思想是首先用第一种颜色对 图中尽可能多的顶点着色(尽可能多表现 出贪心)然后用第二种颜色对余下的顶点中 尽可能多的顶点着色如此等等，直至所有 的顶点都着完色。 当用一种新颜色对余下的顶点着色时我们采取下列步骤: （1）选取某个未着色的顶点，并且用新颜色对它着色。 （2）扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。 1.5.2算法逐步求精 用C++语言描述的贫心算法如下: void greedy(GRAPH G, SET newclr) /*类型GRAPH和SET有待具体说明*/ /*本程序把G中可以着同一色的顶点放入newclr*/ { (1) newclr=F (2) while (G中有未着色的顶点v) (3) if(v不与newclr中的任何顶点相邻){ (4) 对v着色； (5) 将v放入newclr；} }; 其中，G是被着色的图，newclr的初值为空，算法执行的结果形成可以着相同颜色的顶点的集合newclr。只要重复调用greedy算法，直到图中的所有顶点都被着色为止，即可求出问题的解。 1.5.2算法逐步求精 逐步求精：第一步求精： void greedy(GRAPH G, SET newclr) /*类型GRAPH和SET有待具体说明*/ { int found; (1) newclr=F ; (2) while(G中有未着色的顶点v){ (3.1) found=0;/*found的初值为false*/ (3.2) for (newclr中的每一个顶点w） (3.3) if(v与w相邻) (3.4) found=1; (3.5) if(found==0){ /*v与newclr中的任何顶点都不相邻*/ (4) 对v着色； (5) 将v放入newclr； } } }; 1.5.2算法逐步求精 逐步求精：第二步求精： void greedy(GRAPH G, SET newclr) { int found; newclr=%; v=G中第一个未着色的顶点； while (v!=0){ /*G中还有未着色的顶点v*/ found=0; w=newclr中的第一个顶点； while(w!=0){ /*newclr中的顶点还没取尽*/ if(v与w相邻) found=1; w=newclr中的下个顶点； }; if(found==0){ 对v着色；将v放入newclr；} v=G中下一个未着色的顶点； } ; } 1.5.2算法逐步求精 逐步求精：第三步求精： 由上一步求精的结果可见，算法中大部分操作都归结为对图和集合的操作。设G和S分别是抽象数据型GRAPH和SET的实例，我们在G上规定如下操作： (1)FIRSTG(G)返回G中的第一个未加标记的（未着色的）元素；若G中没有这样的元素存在，则返回NULL。 (2)EDGE(v,w,G)若v和w在G中相邻，则返回true，否则返回false。 (3)MARK(v,G)标记G中的元素v。 (4)ADDG(v,G)将元素v放入G中。 (5)NEXTG(G)返回G中下一个未标记得元素，若G中没有这样的元素存在，则返回NUL。 在S上规定如下操作： (1)MAKENULL(S)将集合S置空。 (2)FIRSTS(S)返回S中的第一个元素；若S为空集，则返回NULL。 (3)NEXTS(S)返回S中的下一个元素；若S中没有下一个元素，则返回NULL。 (4)ADDS(v,S)将v放入S中。 1.5.2算法逐步求精 逐步求精：第三步求精： void greedy(GRAPH G, SET newclr) /*类型GRAPH和SET有待说明*/ { int found; elementtype v,w;/*elementtype可以自定义*/ MAKENULL(newclr); v=FIRSTG(G); while(v!=NULL){ found=0; w=FIRSTS(newclr); while(w!=NULL){ if(EDGE(v,w,G)) found=1; w=NEXTS(newclr); }; v=NEXTG(G); } }; 1.5.2算法逐步求精 ADT的实现： 按上述函数，最后一步工作就是给出类型el