图的基本概念以及DFS与BFS算法

// 邻接矩阵
namespace matrix
{
	// V代表的是顶点的元素类型
	// W代表的是边的权值类型
	// MAX_W是边的权值，以INT_MAX代表无穷大
	// Direction代表的true为有向图，false为无向图
	template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:
		// 图的创建
		// 1、IO输入 -- 不方便测试，更适合oj
		// 2、图结构关系写到文件，读取文件
		// 3、手动添加边，方便调试，这里选用这种方式
		Graph(const V* a, size_t n)
		{
			// 初始化顶点集合和顶点映射的下标
			_vertexs.reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.push_back(a[i]);
				_vIndexMap[a[i]] = i;
			}

			// 初始化矩阵
			_matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
				_matrix[i].resize(n, MAX_W);
		}

		// 链接边的函数
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			_matrix[srci][dsti] = w;
			// 判断是否为无向图，是的话矩阵要对称赋值
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}

		// 查找顶点映射的下标
		size_t GetVertexIndex(const V& v)
		{
			// 为了防止顶点不存在的情况，这里我们使用map的find函数
			auto it = _vIndexMap.find(v);
			if (it == _vIndexMap.end())
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
			else
			{
				return it->second;
			}
		}

		// 为了方便观察，要实现一个打印函数
		void Print()
		{
			// 顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			// 矩阵
			// 横下标
			cout << "  ";
			for (int i = 0; i < _vertexs.size(); ++i)
			{
				//cout << i << " ";
				printf("%4d", i);
			}
			cout << endl;

			for (int i = 0; i < _matrix.size(); ++i)
			{
				cout << i << " "; // 竖下标
				for (int j = 0; j < _matrix[i].size(); ++j)
				{
					//cout << _matrix[i][j] << " ";
					if (_matrix[i][j] == MAX_W)
					{
						//cout << "* ";
						printf("%4c", '*');
					}
					else
					{
						//cout << _matrix[i][j] << " ";
						printf("%4d", _matrix[i][j]);
					}
				}
				cout << endl;
			}
			cout << endl;
		}
	private:
		vector<V> _vertexs;    // 顶点集合
		vector<vector<W>> _matrix;    // 存储边集合的矩阵
		map<V, size_t> _vIndexMap;    // 相应顶点映射的下标
	};

	void TestGraph()
	{
		Graph<char, int, INT_MAX, true> g("0123", 4);
		g.AddEdge('0', '1', 1);
		g.AddEdge('0', '3', 4);
		g.AddEdge('1', '3', 2);
		g.AddEdge('1', '2', 9);
		g.AddEdge('2', '3', 8);
		g.AddEdge('2', '1', 5);
		g.AddEdge('2', '0', 3);
		g.AddEdge('3', '2', 6);
		g.Print();
	}
}

// 运行结果
[0]->0
[1]->1
[2]->2
[3]->3
     0   1   2   3
0    *   1   *   4
1    *   *   9   2
2    3   5   *   8
3    *   *   6   *

// 邻接表
namespace Adjacency_table
{
	template <class W>
	struct Edge
	{
		//size_t _srcIndex;  // 这是入度的下标，一般不用实现
		size_t _dstIndex; // 代表出度下标
		W _weight; // 权值
		Edge<W>* _next; // 链表的下一个节点

		Edge(size_t dstIndex, W weight = W())
			:_dstIndex(dstIndex)
			, _weight(weight)
			, _next(nullptr)
		{}
	};

	// V代表的是顶点的元素类型
	// W代表的是边的权值类型
	// MAX_W是边的权值，以INT_MAX代表无穷大
	// Direction代表的true为有向图，false为无向图
	template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* a, size_t n)
		{
			_vertexs.reserve(n);
			_tables.resize(n, nullptr);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.push_back(a[i]);
				_vIndexMap[a[i]] = i;
			}
		}

		// 链接边的函数
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			// 进行头插
			Edge* newEdge = new Edge(dsti, w);
			newEdge->_next = _tables[srci];
			_tables[srci] = newEdge;

			// 判断是否为无向图
			if (Direction == false)
			{
				// 同样进行头插
				Edge* newEdge = new Edge(srci, w);
				newEdge->_next = _tables[dsti];
				_tables[dsti] = newEdge;
			}
		}

		// 查找顶点映射的下标
		size_t GetVertexIndex(const V& v)
		{
			// 为了防止顶点不存在的情况，这里我们使用map的find函数
			auto it = _vIndexMap.find(v);
			if (it == _vIndexMap.end())
			{
				throw invalid_argument("顶点不存在");
				return -1;
			}
			else
			{
				return it->second;
			}
		}

		// 为了方便观察，要实现一个打印函数
		void Print()
		{
			// 顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cout << _vertexs[i] << "[" << i << "]->";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << "[" << _vertexs[cur->_dstIndex] << ":" << cur->_dstIndex << ":" << cur->_weight << "]->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}
	private:
		vector<V> _vertexs;    // 顶点集合
		map<V, size_t> _vIndexMap;    // 相应顶点映射的下标
		vector<Edge*> _tables;    // 存放边集合的指针数组
	};

	void TestGraph()
	{
		string a[] = { "张三", "李四", "王五", "赵六" };
		Graph<string, int, INT_MAX, true> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.Print();
	}
}

// 运行结果
[0]->张三
[1]->李四
[2]->王五
[3]->赵六

张三[0]->[王五:2:200]->[李四:1:100]->nullptr
李四[1]->nullptr
王五[2]->[赵六:3:30]->nullptr
赵六[3]->nullptr

// 广度优先遍历
void BFS()
{
    // visited数组标记是否访问过节点
    vector<bool> visited;
    visited.resize(_vertexs.size(), false);
    queue<int> qe;

    size_t n = _vertexs.size();
    for(size_t i = 0; i < n; ++i)
    {
        if (visited[i] == false)
        {
            qe.push(i);
            visited[i] = true;
            while (!qe.empty())
            {
                int front = qe.front();
                qe.pop();
                cout << front << ":[" << _vertexs[front] << ']' << endl;

                // 遍历该顶点矩阵中的出边，将它们入队，并标记一下表示出现过
                for (size_t j = 0; j < n; ++j)
                {
                    if (_matrix[front][j] != MAX_W && visited[j] == false)
                    {
                        qe.push(j);
                        visited[i] = true;
                    }
                }
            }
            cout << endl;
        }
    }
}
void TestGraphBFS()
{
    string a[] = { "张三", "李四", "王五", "赵六", "周七" };
    Graph<string, int, INT_MAX, true> g1(a, sizeof(a) / sizeof(string));
    g1.AddEdge("张三", "李四", 100);
    g1.AddEdge("张三", "王五", 200);
    g1.AddEdge("王五", "赵六", 30);
    g1.Print();
    g1.BFS();
}

// 运行结果
[0]->张三
[1]->李四
[2]->王五
[3]->赵六
[4]->周七
     0   1   2   3   4
0    * 100 200   *   *
1    *   *   *   *   *
2    *   *   *  30   *
3    *   *   *   *   *
4    *   *   *   *   *

0:[张三]
1:[李四]
2:[王五]
3:[赵六]

4:[周七]

// 深度优先遍历
void DFS()
{
    vector<bool> visited(_vertexs.size(), false);

    // 遍历所有的顶点，判断是否都是true防止了遗漏一些不连通的子图
    for (size_t i = 0; i < _vertexs.size(); ++i)
    {
        if (visited[i] == false)
        {
            // 交给子函数去递归解决
            _DFS(i, visited);
        }
    }
    cout << endl;
}

void _DFS(size_t srci, vector<bool>& visited)
{
    cout << srci << ":[" << _vertexs[srci] << ']' << endl;
    
    // 将该节点的下标标记为访问过
    visited[srci] = true;
    for (size_t i = 0; i < _vertexs.size(); ++i)
    {
        if (_matrix[srci][i] != MAX_W && visited[i] == false)
        {
            _DFS(i, visited);
        }
    }
}

void TestGraphDFS()
{
    string a[] = { "张三", "李四", "王五", "liren", "赵六", "周七"};
    Graph<string, int, INT_MAX, true> g1(a, sizeof(a) / sizeof(string));
    g1.AddEdge("张三", "李四", 100);
    g1.AddEdge("张三", "王五", 200);
    g1.AddEdge("王五", "赵六", 30);
    g1.AddEdge("王五", "周七", 30);
    g1.DFS();
    g1.Print();
}

//运行结果
0:[张三]
1:[李四]
2:[王五]
4:[赵六]
5:[周七]
3:[liren]

[0]->张三
[1]->李四
[2]->王五
[3]->liren
[4]->赵六
[5]->周七

     0   1   2   3   4   5
0    * 100 200   *   *   *
1    *   *   *   *   *   *
2    *   *   *   *  30  30
3    *   *   *   *   *   *
4    *   *   *   *   *   *
5    *   *   *   *   *   *