图的邻接矩阵实现_MGraph
最后更新于：2022-04-01 20:51:51
邻接矩阵有两种, 不带权图和网的邻接矩阵. 不带权图的邻接矩阵元素为0或1, 网的邻接矩阵中包含0, INF, 和边上的权值, 权值类型T可为整型, 实型. 三元组(u, v, w)代表一条边, u, v是边的两个定点, w表示u v的关系:
a[u][u] = 0, 两种邻接矩阵的主对角元素都是0. a[u][v] = w, 若 在E中, 则w = 1(不带权图)或w = w(i, j)(网). 若不在E中,
则w = noEdge, noEdge = 0(不带权图)或noEdge = INF(网).
保护数据成员T **a指向动态生成的二维数组, 用来存储邻接矩阵.
包含的函数Exist(): 若输入参数u, v无效或a[u][v] == noEdge, 则不存在边, 返回false, 否则返回true.
函数Insert(): 若输入参数u, v无效返回Failure. 若a[u][v] != noEdge, 表示边已经存在, 函数返回Duplicate. 否则添加边, 返回Success, 具体做法: a[u][v] = w, e++.
函数Remove(): 若输入参数u, v无效, 不能执行删除运算, 返回Failure. 若a[u][v] == noEdge, 表示图中不存在边, 函数返回Notpresent. 否则从邻接矩阵中删除边, 返回Success, 具体做法: a[u][v] = noEdge, e--.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure };
template
class Graph
{
public:
virtual ~Graph() {};
virtual ResultCode Insert(int u, int v, T &w) = 0;
virtual ResultCode Remove(int u, int v) = 0;
virtual bool Exist(int u, int v) const = 0;
/* data */
};
template
class MGraph: public Graph
{
public:
MGraph(int mSize, const T& noedg);
~MGraph();
ResultCode Insert(int u, int v, T &w);
ResultCode Remove(int u, int v);
bool Exist(int u, int v) const;
int Vertices() const { return n; }
void Output();
protected:
T **a;
T noEdge;
int n, e;
/* data */
};
template
void MGraph::Output()
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
if(a[i][j] == noEdge) cout << "NE\t";
else cout << a[i][j] << "\t";
cout << endl;
}
cout << endl << endl << endl;
}
template
MGraph::MGraph(int mSize, const T &noedg)
{
n = mSize, e = 0, noEdge = noedg;
a = new T *[n];
for(int i = 0; i < n; ++i) {
a[i] = new T[n];
for(int j = 0; j < n; ++j)
a[i][j] = noEdge;
a[i][i] = 0;
}
}
template
MGraph::~MGraph()
{
for(int i = 0; i < n; ++i)
delete []a[i];
delete []a;
}
template
bool MGraph::Exist(int u, int v) const
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false;
return true;
}
template
ResultCode MGraph::Insert(int u, int v, T &w)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] != noEdge) return Duplicate;
a[u][v] = w;
e++;
return Success;
}
template
ResultCode MGraph::Remove(int u, int v)
{
if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
if(a[u][v] == noEdge) return NotPresent;
a[u][v] = noEdge;
e--;
return Success;
}
int main(int argc, char const *argv[])
{
MGraph mg(4, 99);
int w = 4; mg.Insert(1, 0, w); mg.Output();
w = 5; mg.Insert(1, 2, w); mg.Output();
w = 3; mg.Insert(2, 3, w); mg.Output();
w = 1; mg.Insert(3, 0, w); mg.Output();
w = 1; mg.Insert(3, 1, w); mg.Output();
return 0;
}
~~~
';