相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： 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
====================================================================焦急等待算法结果的分割线====================================================================
举例下图：
|-------> b ------
--- |
a ----------> d
--- |
|-------> c ------
有向无环图顶点 a b c d 的赋值应该为 12 3 4
====================================================================焦急等待算法结果的分割线====================================================================
点击(此处)折叠或打开
-
#include <string>
-
#include <vector>
-
#include <iostream>
-
-
class vertex {
-
public:
-
int head;
-
int next;
-
int in_degree;
-
int val;
-
-
vertex();
-
vertex(int, int);
-
};
-
-
vertex::vertex()
-
{
-
head = next = val = in_degree = 0;
-
}
-
-
vertex::vertex(int head, int next)
-
{
-
this->head = head;
-
this->next = next;
-
in_degree = 0;
-
val = 0;
-
}
-
-
std::vector<vertex> digraph;
-
-
void gen_digraph(std::vector<vertex>& dg) {
-
dg.push_back(vertex(0, 0));
-
dg.push_back(vertex(0, 5));
-
dg.push_back(vertex(0, 7));
-
dg.push_back(vertex(0, 0));
-
dg.push_back(vertex(0, 8));
-
dg.push_back(vertex(2, 6));
-
dg.push_back(vertex(4, 0));
-
dg.push_back(vertex(3, 0));
-
dg.push_back(vertex(2, 9));
-
dg.push_back(vertex(3, 0));
-
-
std::vector<vertex>::iterator i;
-
for (i = dg.begin(); i != dg.end(); i) {
-
if (i->head != 0) {
-
int index = i->head;
-
dg[index].in_degree;
-
}
-
}
-
}
-
-
void topo_sort(std::vector<vertex>& dg, int vertex, int topo_val)
-
{
-
int index = vertex;
-
dg[index].val = topo_val;
-
while (dg[index].next != 0) {
-
int next = dg[index].next;
-
int head = dg[next].head;
-
dg[index].next = dg[next].next;
-
if (--dg[head].in_degree == 0)
-
topo_sort(dg, head, topo_val);
-
}
-
}
-
-
int main(int argc, char** argv)
-
{
-
int index = 1;
-
std::vector<vertex>::iterator p;
-
-
gen_digraph(digraph);
-
-
for ( p = digraph.begin()1; p->in_degree != 0 && p != digraph.end(); p, index);
-
if (p == digraph.end())
-
return -1;
-
topo_sort(digraph, index, 1);
-
-
index = 1;
-
for ( p = digraph.begin()1; p->head == 0 && p != digraph.end(); p, index)
-
std::cout << index << "\t" << p->val << std::endl;
-
-
return 0;
- }
给主人留下些什么吧！~~