awgraph.h

贪婪算法合集,包括二分覆盖,单源最短路径,拓扑排序,机器调度问题

// 加权图的耗费邻接矩阵,根据无向图可看成(i,j)和(i,j)都存在的有向图，所以可派生于AdjacencyWDigraph类

#ifndef AdjacencyWGraph_
#define AdjacencyWGraph_

#include "awdgraph.h"

template<class T>
class AdjacencyWGraph : public AdjacencyWDigraph<T>
{
public:
	AdjacencyWGraph(int Vertices = 10, T noEdge = 0): AdjacencyWDigraph<T>(Vertices, noEdge) {}
    AdjacencyWGraph<T>& Add(int i, int j, const T& w)
	{AdjacencyWDigraph<T>::Add(i,j,w);a[j][i] = w;return *this;}//无向图对称的存在，所以a[j][i]也要赋值
    AdjacencyWGraph<T>& Delete(int i, int j)//同样删除，要置两个为0
	{AdjacencyWDigraph<T>::Delete(i,j);a[j][i] = NoEdge;return *this;}
    int Degree(int i) const {return OutDegree(i);}//度数，只要出度即可
};

#endif