#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

#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;

//二维矩阵：n行n列，全部初始化为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

#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

#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;

}