邻接图 所谓的拓扑排序 以及 所谓的关键路径

#include
#include

using namespace std;

const int max_num = 20;
template class graph;

template
class node {
        private:
                T id;
                int weight;
                node * next;
        public: 
                friend class graph;
                node() {}       
                node(T v, int w, node * next_node = NULL):
                        id(v), weight(w), next(next_node){}
}; 

template
class graph {
        private:
                node * table;
                bool visited[max_num];
                stack sorted_sta;
                int node_num;
                int getPos(const T &);
        public:
                ~graph();       
                graph(){table = new node[max_num]; node_num = 0;}
                graph(const T * [], int);
                bool addNode(const T &);
                bool addArc(const T &, const T &, const int);
                void clear_vis();
                void top_sort();
                void print_ts();
                void dfs(const T &);
                void print();
                void criticalPath();
};

template
int graph::getPos(const T &v) {
        for (int i = 0; i < node_num; i++) {
                if (table[i].id == v) return i;
        }
        return -1;
}

template
graph::graph(const T * v[], int num) {
        if (num > max_num) {
                cout << "too many!" << endl;    
                return;
        }
        table = new node[max_num];
        node_num = 0;
        for (int i = 0; i < num; i++) {
                addNode(v[i]);
        }
}

template
graph::~graph() {
        node * p;
        for (int i = 0; i < node_num; i++) {
                p = table[i].next;      
                while(p != NULL) {
                        table[i].next = p->next;                
                        delete p;
                        p = table[i].next;
                }
        } 
        delete [] table ;
}
                
template
bool graph::addNode(const T &v) {
        if (node_num >= max_num) {
                cout << "full!" << endl;
                return false;
        } else {
                table[node_num].id = v;
                table[node_num].weight = 0;
                table[node_num].next = NULL;
                node_num++;
                return true;
        }
}

template
bool graph::addArc(const T &v1, const T &v2, const int w) {
        int m;  
        if ((m = getPos(v1)) < 0 || getPos(v2) < 0) {
                cout << "v1 or v2 not exist!" << endl;
                return false;
        } else {
                node *tmp = table[m].next;
                table[m].next = new node(table[getPos(v2)].id,w,tmp);
                return true;
        }
}

template
void graph::print() {
        node * p;    
        for (int i = 0; i < node_num; i++) {
                cout << table[i].id << ":";
                p = table[i].next;
                while(p != NULL) {
                        cout << "->" << p->id << "(" << p->weight << ")";
                        p = p->next;
                }
                cout << endl;
        }
}

template  
void graph::clear_vis() {
        memset(visited,0,max_num);
        while(!sorted_sta.empty()) sorted_sta.pop();
}

template
void graph::top_sort() {
        clear_vis();
        for(int i = 0; i < node_num; i++) {
                if (!visited[i]) {
                        dfs(table[i].id);
                }
        }
}

template
void graph::print_ts() {
        while(!sorted_sta.empty()) {
                cout << sorted_sta.top() << " ";
                sorted_sta.pop();
        }
        cout << endl;
}

template
void graph::dfs(const T &v) {
        int m = getPos(v);
        visited[m] = true;
        node * p = table[m].next;
        while(p != NULL) {
                if (!visited[getPos(p->id)]) {
                        dfs(p->id);
                }
                p = p->next;
        } 
        sorted_sta.push(v);
}

template
void graph::criticalPath() {
        int *pi = new int[node_num];
        int *v = new int[node_num];
        memset (v, 0, sizeof(int) * node_num);
        memset (pi, -1, sizeof(int) * node_num);
        int m;
        node * p;
        top_sort();
        while(!sorted_sta.empty()) {
                m = getPos(sorted_sta.top());
                p = table[m].next;
                while (p != NULL) {
                        if (v[getPos(p->id)] < v[m] + p->weight) {
                                v[getPos(p->id)] = v[m] + p->weight;
                                pi[getPos(p->id)] = m; 
                        }
                        p = p -> next;
                }
                sorted_sta.pop();
        }
        cout << v[m] << endl;
                
        cout << table[m].id;    
        while (pi[m] != -1) {
                cout <<"<-"<< table[pi[m]].id ;
                m = pi[m];
        }
}

int main()
{
        graph a;
        a.addNode('a');
        a.addNode('b');
        a.addNode('c');
        a.addNode('d');
        a.addArc('a','c', 4);
        a.addArc('a','b', 10);
        a.addArc('c','b', 10);
        a.addArc('b','d', 7);
        a.top_sort();
        a.print_ts();
        a.criticalPath();
}

 

 

拓扑排序的道理

 

    保证深度优先，同时越深越先入栈。 最深绝对是出度为0，并且较深一层不会有向上的弧。就好像把整张图的一个入度为零的点拎起来，抖了抖, 然后再一根根理顺。

  上图是拓扑排序后的一张图（和程序中的图无关）。 首先我們考虑C点，从A点到C点有两条路，一条A－>C 一条A－>B->C 现在根据我們的假设，由于拓扑排序的特殊性以及我們程序的写法 C之前的弧都已经操作过了，也就是弧AB AC BC 每个点里面都存有（我們用的是pi这个数组）A点到该点的最远的距离。那我如果现在知道了A点到A点的距离，和A点到B点 的最远距离，我现在只要把A点到A点的距离加上A到C的距离就知道C点经过A点到A点的最远距离，只要把A点到B点的最远 距离加上B点到C的距离就知道C点经过B点到A的最远距离。然后我們比较一下两者取一个最大的，然后C点到A点的最远距离 不就知道了么。 一开始，A点到A点的最远距离是知道的，经过B点时，A点到B点的弧操作过了。这时B点到A点的最远距离就知道了。 接着经过C点，一样的，A B的最远距离都知道了，能到达C的弧又都操作过了，C点到A点的最远距离就知道了。 D点也一样，A B C 都好了， 到D的弧也操作过了，D点到A点最远就知道了。

  还有一定要注意的，一定要有一个入度为0的点，和一个出度为0的点。另外，这个程序不是很健壮，而且不是题目要求的用遍历来写。