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

}

//相邻点迭代器（相邻，即 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];

}

//相邻点迭代器（相邻，即 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

#include "SparseGraph.h"

#include "DenseGraph.h"

#include <iostream>

#include <ctime>

using namespace std;

int main()

{

int N = 20; //20个顶点

int M = 100; //100条边

srand(time(NULL));

// Sparse Graph：随机生成一张稀疏图

//（因为实现中没有过滤平行边，所以

//有可能存在平行边）

SparseGraph g1(N, false);

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

{

int a = rand() % N;

int b = rand() % N;

g1.addEdge(a, b);

}

// 打印所有的邻边，时间复杂度：O(E)

//即 有多少边就遍历多少次

for (int v = 0; v < N; v++)

{

cout << v << " : ";

//对于每一个顶点都声明一个相邻点迭代器

SparseGraph::adjIterator adj(g1, v);

for (int w = adj.begin(); !adj.end(); w = adj.next())

{

cout << w << " ";

}

cout << endl;

}

cout << endl;

// Dense Graph：随机生成一张稠密图

DenseGraph g2(N, false);

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

{

int a = rand() % N;

int b = rand() % N;

g2.addEdge(a, b);

}

// 打印所有的邻边，时间复杂度：O(V^2)，

//如果V^2远远大于E的话，就能看出来这种

//稀疏图的实现的优势

for (int v = 0; v < N; v++)

{

cout << v << " : ";

DenseGraph::adjIterator adj(g2, v);

for (int w = adj.begin(); !adj.end(); w = adj.next())

{

cout << w << " ";

}

cout << endl;

}

system("pause");

return 0;

}

//原本的实现思路：

//最简单的方式其实是将DenseGraph和SparseGraph类中的 g 的访问控制符，

//由 private 改成 public，在外面就可以直接对 g 的某一行进行循环，就

//已经实现了遍历邻边的功能

//

//但它的缺点就是将 g 这个数据暴露在了外面，外面的调用用户就有可能不

//经意间修改 g，导致产生奇怪的 bug，当然如果大家只是写一些小的算法，

//或者应付面试中的一个算法的实现，这样实现就完全够了

//

//

//

//现在的实现思路：

//保持 g 本身还是 private，借助迭代器让外面能够遍历

//（PS：如果不用迭代器，也可以写一个函数，直接要到某一个顶点的所有

//相邻顶点，但这样做的缺点是:不得不要把 g 的某一行复制一份，这也是

//不够好的，所以这里借助迭代器的思想）

//

//

//之所以设置这样的一个迭代器，还有一个非常重要的意义，就是将稀疏图

//和稠密图这两个类里面的具体实现屏蔽了，而从用户的角度看，它们呈现

//给外面的接口是完全一样的，这为后续实现图相关的算法带来了方便

//

//每一个图的算法都将对稀疏图和稠密图同时成立，因为都是调用同样的接

//口，换句话说，图算法都将封装在模板类中，那么这个模板就可以任意的

//传入稀疏图或稠密图