无环最长简单路径

标题有点累赘，好像无环就可以保证绝对简单了，下面给出代码的实现

LongestPath.h

 1 #pragma once
 2 
 3 #include <stack>
 4 #include <list>
 5 #include <cstring>
 6 #include <iostream>
 7 
 8 class adjNode
 9 {
10     int v, weight;
11 
12 public:
13     adjNode(int v, int weight) :v(v), weight(weight){}
14     adjNode() = default;
15     //adjNode(adjNode&&) = default;
16     int getV() { return v; }
17     int getWeight(){ return weight; }
18 };
19 
20 class graph
21 {
22     int node_sum;
23     //记得加std
24     std::list<adjNode> **adj;
25 
26     void topoSort(int s, bool visited[], std::stack<int> &Stack);
27 
28 public:
29     graph(int v);
30     ~graph() { 
31         for (int i = 0;i < node_sum;i++)
32             delete adj[i];
33         delete adj; 
34     }
35     void addEdge(int u, int v, int w);
36     void longestPath(int s);//源节点到各点距离以打印方式呈现，或者可以返回一个vector
37 
38 };
39 void graph::topoSort(int s, bool visited[], std::stack<int> &Stack)
40 {
41     visited[s] = 0;
42 
43     for (auto it = adj[s]->begin();it != adj[s]->end();++it)
44     {
45         if (!visited[it->getV()])
46             topoSort(it->getV(), visited, Stack);
47     }
48     Stack.push(s);
49 }
50 
51 void graph::addEdge(int u, int v, int weight)
52 {
53     adj[u]->push_back(adjNode(v, weight));
54 }
55 
56 graph::graph(int v) :node_sum(v)
57 {
58     adj = new std::list<adjNode>* [node_sum];
59     for (int i = 0;i < node_sum;i++)
60         adj[i] = new std::list <adjNode>();
61 }
62 
63 void graph::longestPath(int s)
64 {
65     std::stack<int> sta;
66     int *dist = new int[node_sum];
67     bool *visited = new bool[node_sum];
68 
69     memset(visited, 0, sizeof(visited));
70     for (int i = 0;i < node_sum;i++)
71         dist[i] = INT_MIN;
72     //memset(dist, -1, sizeof(dist));
73     dist[s] = 0;
74 
75     for (int i = 0;i < node_sum;i++)
76         if (!visited[i])
77             topoSort(i, visited, sta);
78 
79     while (!sta.empty()) {
80         int u = sta.top();
81         sta.pop();
82 
83         if (dist[u] != INT_MIN)
84             for (auto it = adj[u]->begin();it != adj[u]->end();++it)
85                 if (dist[it->getV()] < dist[u] + it->getWeight())
86                     dist[it->getV()] = dist[u] + it->getWeight();
87     }
88     for (int i = 0;i < node_sum;i++)std::cout << dist[i] << " ";
89     std::cout << std::endl;
90 
91     delete visited;
92     delete dist;
93 }

这是借鉴某博客的，后面追根溯源找到了https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

一开始的想法是好好学习（照着打）一波，发现代码跑不了，问题应该是出在这一句：

1 list<AdjListNode> *adj;
2 Graph::Graph(int V) // Constructor
3 {
4     this->V = V;
5     adj = new list<AdjListNode>[V];
6 }

跑的时候好像是出现的堆错误，不知道是不是IDE的问题，我的是vs15，这个我想单独立个博客等以后来解决。这告诉我的道理是，看得懂别人的代码最好也还是跑一下，在实现的时候你才会真正地实现一些细节。还是感谢一波分享，除了上面说的还有几处new的地方都没有delete之外，算法什么应该都没问题。当然我贴的代码跑过了，下面是测试的代码：

test.cpp

 1 #include "LongestPath.h"
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 int main(void)
 7 {
 8     graph g(6);
 9     g.addEdge(0, 1, 5);
10     g.addEdge(0, 2, 3);
11     g.addEdge(1, 3, 6);
12     g.addEdge(1, 2, 2);
13     g.addEdge(2, 4, 4);
14     g.addEdge(2, 5, 2);
15     g.addEdge(2, 3, 7);
16     g.addEdge(3, 5, 1);
17     g.addEdge(3, 4, -1);
18     g.addEdge(4, 5, -2);
19 
20     int s = 1;
21     cout << "Following are longest distances from "
22         "source vertex " << s << " 
";
23     g.longestPath(s);
24 
25     return 0;
26 }