图的顶点赋值问题-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 13617
  • 博文数量: 3
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 41
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-12 11:12
个人简介

立志称为优秀的产品设计者

文章分类

全部博文(3)

文章存档

2013年(3)

我的朋友
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: c/c

2013-04-23 14:45:02

设g=(v,e)是有向无环图。写一个为g的顶点赋值的算法,如果存在一条从顶点i到顶点j的有向边,则i比j小

举例下图:

       |-------> b ------
    ---                        |
a                               ----------> d
    ---                        |
       |-------> c ------

有向无环图顶点 a b c d 的赋值应该为 12 3 4
====================================================================焦急等待算法结果的分割线====================================================================

点击(此处)折叠或打开

  1. #include <string>
  2. #include <vector>
  3. #include <iostream>

  4. class vertex {
  5. public:
  6.     int head;
  7.     int next;
  8.     int in_degree;
  9.     int val;

  10.     vertex();
  11.     vertex(int, int);
  12. };

  13. vertex::vertex()
  14. {
  15.     head = next = val = in_degree = 0;
  16. }

  17. vertex::vertex(int head, int next)
  18. {
  19.     this->head = head;
  20.     this->next = next;
  21.     in_degree = 0;
  22.     val = 0;
  23. }

  24. std::vector<vertex> digraph;

  25. void gen_digraph(std::vector<vertex>& dg) {
  26.     dg.push_back(vertex(0, 0));
  27.     dg.push_back(vertex(0, 5));
  28.     dg.push_back(vertex(0, 7));
  29.     dg.push_back(vertex(0, 0));
  30.     dg.push_back(vertex(0, 8));
  31.     dg.push_back(vertex(2, 6));
  32.     dg.push_back(vertex(4, 0));
  33.     dg.push_back(vertex(3, 0));
  34.     dg.push_back(vertex(2, 9));
  35.     dg.push_back(vertex(3, 0));

  36.     std::vector<vertex>::iterator i;
  37.     for (i = dg.begin(); i != dg.end(); i) {
  38.         if (i->head != 0) {
  39.             int index = i->head;
  40.             dg[index].in_degree;
  41.         }
  42.     }
  43. }

  44. void topo_sort(std::vector<vertex>& dg, int vertex, int topo_val)
  45. {
  46.     int index = vertex;
  47.     dg[index].val = topo_val;
  48.     while (dg[index].next != 0) {
  49.         int next = dg[index].next;
  50.         int head = dg[next].head;
  51.         dg[index].next = dg[next].next;
  52.         if (--dg[head].in_degree == 0)
  53.             topo_sort(dg, head, topo_val);
  54.     }
  55. }

  56. int main(int argc, char** argv)
  57. {
  58.     int index = 1;
  59.     std::vector<vertex>::iterator p;

  60.     gen_digraph(digraph);

  61.     for ( p = digraph.begin()1; p->in_degree != 0 && p != digraph.end(); p, index);
  62.     if (p == digraph.end())
  63.         return -1;
  64.     topo_sort(digraph, index, 1);

  65.     index = 1;
  66.     for ( p = digraph.begin()1; p->head == 0 && p != digraph.end(); p, index)
  67.         std::cout << index << "\t" << p->val << std::endl;

  68.     return 0;
  69. }


阅读(1305) | 评论(0) | 转发(0) |
0

上一篇:杯子测楼问题

下一篇:没有了

给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图