首页 > 代码库 > 图的算法框架

图的算法框架

-------------------siwuxie095

   

   

   

   

   

   

   

   

图的算法框架

   

   

图的算法可以写在函数中,也可以封装在类中,为了严谨起见

和后续复用,这里统一将图的算法都封装在类中

   

   

其实对于图的算法而言,通常会比较复杂,需要很多辅助数据

结构,而且这些数据结构可能会成为类中的成员变量,这也是

要将图的算法封装在类中的原因之一

   

   

同时,这里也会将封装成的类都设置为类模板,这样,不管是

稀疏图,还是稠密图,都可以传入算法中,从而形成模板类

   

   

   

   

   

如:从文件中读取图的测试用例的算法

   

文件 testG1.txt 的内容,如下:

   

技术分享

   

   

该文件可以分成两部分:

   

1)第一行:(13,13),表示图中有 13 个顶点,13 条边

   

2)其它行:每一行有两个数字,表示一条边。共 13 行,即有 13 条边

   

   

   

   

   

程序:

   

SparseGraph.h:

   

#ifndef SPARSEGRAPH_H

#define SPARSEGRAPH_H

   

#include <iostream>

#include <vector>

#include <cassert>

using namespace std;

   

   

   

// 稀疏图 - 邻接表

class SparseGraph

{

   

private:

   

int n, m; //n m 分别表示顶点数和边数

bool directed; //directed表示是有向图还是无向图

vector<vector<int>> g; //g[i]里存储的就是和顶点i相邻的所有顶点

   

public:

   

SparseGraph(int n, bool directed)

{

//初始化时,有n个顶点,0条边

this->n = n;

this->m = 0;

this->directed = directed;

//g[i]初始化为空的vector

for (int i = 0; i < n; i++)

{

g.push_back(vector<int>());

}

}

   

   

~SparseGraph()

{

   

}

   

   

int V(){ return n; }

int E(){ return m; }

   

   

//在顶点v和顶点w之间建立一条边

void addEdge(int v, int w)

{

   

assert(v >= 0 && v < n);

assert(w >= 0 && w < n);

   

g[v].push_back(w);

//1)顶点v不等于顶点w,即 不是自环边

//2)且不是有向图,即 是无向图

if (v != w && !directed)

{

g[w].push_back(v);

}

   

m++;

}

   

   

//hasEdge()判断顶点v和顶点w之间是否有边

//hasEdge()的时间复杂度:O(n)

bool hasEdge(int v, int w)

{

   

assert(v >= 0 && v < n);

assert(w >= 0 && w < n);

   

for (int i = 0; i < g[v].size(); i++)

{

if (g[v][i] == w)

{

return true;

}

}

   

return false;

}

   

   

void show()

{

   

for (int i = 0; i < n; i++)

{

cout << "vertex " << i << ":\t";

for (int j = 0; j < g[i].size(); j++)

{

cout << g[i][j] << "\t";

}

cout << endl;

}

}

   

   

   

//相邻点迭代器(相邻,即 adjacent

//

//使用迭代器可以隐藏迭代的过程,按照一定的

//顺序访问一个容器中的所有元素

class adjIterator

{

private:

   

SparseGraph &G; //图的引用,即 要迭代的图

int v; //顶点v

int index; //相邻顶点的索引

   

public:

   

adjIterator(SparseGraph &graph, int v) : G(graph)

{

this->v = v;

this->index = 0;

}

   

   

//要迭代的第一个元素

int begin()

{

//因为有可能多次调用begin()

//所以显式的将index设置为0

index = 0;

//如果g[v]size()不为0

if (G.g[v].size())

{

return G.g[v][index];

}

   

return -1;

}

   

   

//要迭代的下一个元素

int next()

{

index++;

if (index < G.g[v].size())

{

return G.g[v][index];

}

   

return -1;

}

   

   

//判断迭代是否终止

bool end()

{

return index >= G.g[v].size();

}

};

};

   

   

//事实上,平行边的问题,就是邻接表的一个缺点

//

//如果要在addEdge()中判断hasEdge(),因为hasEdge()O(n)的复

//杂度,那么addEdge()也就变成O(n)的复杂度了

//

//由于在使用邻接表表示稀疏图时,取消平行边(即 addEdge()

//中加上hasEdge()),相应的成本比较高

//

//所以,通常情况下,在addEdge()函数中就先不管平行边的问题,

//也就是允许有平行边。如果真的要让图中没有平行边,就在所有

//边都添加进来之后,再进行一次综合的处理,将平行边删除掉

   

#endif

   

   

   

DenseGraph.h:

   

#ifndef DENSEGRAPH_H

#define DENSEGRAPH_H

   

#include <iostream>

#include <vector>

#include <cassert>

using namespace std;

   

   

   

// 稠密图 - 邻接矩阵

class DenseGraph

{

   

private:

   

int n, m; //n m 分别表示顶点数和边数

bool directed; //directed表示是有向图还是无向图

vector<vector<bool>> g; //二维矩阵,存放布尔值,表示是否有边

   

public:

   

DenseGraph(int n, bool directed)

{

//初始化时,有n个顶点,0条边

this->n = n;

this->m = 0;

this->directed = directed;

//二维矩阵:nn列,全部初始化为false

for (int i = 0; i < n; i++)

{

g.push_back(vector<bool>(n, false));

}

}

   

   

~DenseGraph()

{

   

}

   

   

int V(){ return n; }

int E(){ return m; }

   

   

//在顶点v和顶点w之间建立一条边

void addEdge(int v, int w)

{

   

assert(v >= 0 && v < n);

assert(w >= 0 && w < n);

   

//如果顶点v和顶点w之间已经存在一条边,

//则直接返回,即排除了平行边

if (hasEdge(v, w))

{

return;

}

   

g[v][w] = true;

//如果是无向图,则g[w][v]处也设为true(无向图沿主对角线对称)

if (!directed)

{

g[w][v] = true;

}

   

m++;

}

   

   

//hasEdge()判断顶点v和顶点w之间是否有边

//hasEdge()的时间复杂度:O(1)

bool hasEdge(int v, int w)

{

assert(v >= 0 && v < n);

assert(w >= 0 && w < n);

return g[v][w];

}

   

   

void show()

{

   

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

cout << g[i][j] << "\t";

}

cout << endl;

}

}

   

   

   

//相邻点迭代器(相邻,即 adjacent

class adjIterator

{

private:

   

DenseGraph &G; //图的引用,即 要迭代的图

int v; //顶点v

int index; //相邻顶点的索引

   

public:

   

adjIterator(DenseGraph &graph, int v) : G(graph)

{

this->v = v;

this->index = -1;

}

   

   

//要迭代的第一个元素

int begin()

{

//找第一个为true的元素,即为要迭代的第一个元素

index = -1;

return next();

}

   

   

//要迭代的下一个元素

int next()

{

for (index += 1; index < G.V(); index++)

{

if (G.g[v][index])

{

return index;

}

}

   

return -1;

}

   

   

//判断迭代是否终止

bool end()

{

return index >= G.V();

}

};

};

   

   

//addEdge()函数隐含着:当使用邻接矩阵表示稠密图时,已经

//不自觉的将平行边给去掉了,即 在添加边时,如果发现已经

//存在该边,就不做任何操作,直接返回即可

//

//事实上,这也是使用邻接矩阵的一个优势可以非常方便的处理

//平行边的问题

//

//另外,由于使用的是邻接矩阵,可以非常快速的用O(1)的方式,

//来判断顶点v和顶点w之间是否有边

   

#endif

   

   

   

ReadGraph.h:

   

#ifndef READGRAPH_H

#define READGRAPH_H

   

#include <iostream>

#include <string>

#include <fstream>

#include <sstream>

#include <cassert>

using namespace std;

   

   

   

//从文件中读取图的测试用例

template <typename Graph>

class ReadGraph

{

   

public:

   

ReadGraph(Graph &graph, const string &filename)

{

   

ifstream file(filename);

string line; //一行一行的读取

int V, E;

   

assert(file.is_open());

   

//读取file中的第一行到line

assert(getline(file, line));

//将字符串line放在stringstream

stringstream ss(line);

//通过stringstream解析出整型变量:顶点数和边数

ss >> V >> E;

   

//确保文件里的顶点数和图的构造函数中传入的顶点数一致

assert(V == graph.V());

   

//读取file中的其它行

for (int i = 0; i < E; i++)

{

   

assert(getline(file, line));

stringstream ss(line);

   

int a, b;

ss >> a >> b;

assert(a >= 0 && a < V);

assert(b >= 0 && b < V);

graph.addEdge(a, b);

}

}

   

};

   

   

#endif

   

   

   

main.cpp:

   

#include "SparseGraph.h"

#include "DenseGraph.h"

#include "ReadGraph.h"

#include <iostream>

using namespace std;

   

   

   

int main()

{

   

string filename = "testG1.txt";

   

SparseGraph g1(13, false);

ReadGraph<SparseGraph> readGraph1(g1, filename);

g1.show();

   

cout << endl;

   

DenseGraph g2(13, false);

ReadGraph<DenseGraph> readGraph2(g2, filename);

g2.show();

   

system("pause");

return 0;

}

   

   

   

   

   

   

   

   

   

   

【made by siwuxie095】

图的算法框架