[数据结构与算法]【数据结构基础C++】图论01

【Note】学习的课程是慕课上的 https://coding.imooc.com/class/71.html
老师讲的贼好！

稠密图

1. 用邻接矩阵表示顶点之间的关系（是否有边）。
2. 有向图和无向图的区别：无向图顶点 v 到 w，w 到 v 都要在矩阵中标注，但是边数只加 1 次！
3. 写一个函数判断两个顶点之间是否有边，避免重复记录边数。
4. 用 vector<vector> 表示二维数组。

//头文件
#pragma once
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class DenseGraph {
private:
	int n,m;							//n:顶点数，m：边数
	vector<vector<bool>> g;				//邻接矩阵,二维
	bool directed;

public:
	DenseGraph(int n, bool directed) {
		this->n = n;
		this->m = 0;
		this->directed = directed;
		for (int i = 0; i < n; ++i) {
			g.push_back(vector<bool>(n, false));
		}
	}
	~DenseGraph(){}
	int V() { return n; }
	int E() { return m; }
	void addEdge(int v, int w) {
		
		assert(v >= 0 && v < n);
		assert(w >= 0 && w < n);
		if (hasEdge(v, w)) {
			return;
		}
		g[v][w] = true;
		//如果是无向图
		if (!directed)
			g[w][v] = true;
		m++;

	}
	bool hasEdge(int v, int w) {
		assert(v >= 0 && v < n);
		assert(w >= 0 && w < n);
		return g[v][w];
	}

};

稀疏图

1. 用 邻接表 表示稀疏图。
2. 在添加边的时候，如果去判断两个顶点是否右边，时间复杂度比较高，对于邻接表，在添加边时，暂时不做两个顶点有边的判断。测试用例不包含平行边。

#pragma once
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

class SparseGraph {
private:
	int n, m;
	vector<vector<int>> g;
	bool directed;

public:
	SparseGraph(int n, bool directed) {
		this->n = n;
		this->m = 0;
		this->directed = directed;
		for (int i = 0; i < n; ++i) {
			g.push_back(vector<int>());
		}
	}
	~SparseGraph() {

	}
	int V() { return n; }
	int E() { return m; }

	void addEdge(int v, int w) {
		assert(v >= 0 && v < n);
		assert(w >= 0 && w < n);
		
		g[v].push_back(w);
		if (v != w && !directed )
			g[w].push_back(v);
		m++;
	}

	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;

	}
};