bosthhe1
commented
1 year ago #define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<map>
#include<functional>
#include<queue>
using namespace std;
template<class T>
class UnioFindSet
{
public:
UnioFindSet(const size_t& n)
{
v.resize(n, -1);
}
int FindRoot(size_t i)
{
int j = i;
while (v[j] >= 0)
{
j = v[j];
}
int k = i;
int next = v[k];
while (next != v[j])
{
v[k] = j;
k = next;
next = v[k];
}
return j;
}
bool Union(size_t a,size_t b)
{
int i = FindRoot(a);
int j = FindRoot(b);
if (i!=j)
{
if (abs(v[i]) < abs(v[j]))
swap(v[i], v[j]);
v[i] += v[j];
v[j] = i;
return true;
}
return false;
}
bool Inset(size_t j,size_t k)
{
return FindRoot(j) == FindRoot(k);
}
public:
private:
vector<T> v;
};
template<class W>
struct Edge
{
size_t _dest;
W _w;
Edge<W>* next;
Edge(size_t dest,const W& w)
:_dest(dest)
,_w(w)
,next(nullptr)
{}
};
template<class V, class W, W Max_w = INT_MAX, bool Direction = false>
class _Graph
{
typedef Edge<W> Edge;
public:
_Graph(const V* v, size_t n)//图的外面会给进来一个V类型数组,将数组中的每一个元素都分散开来，存在对应的下标
{
_vertexs.resize(n);
for (int i = 0; i < n; i++)
{
_vertexs[i] = v[i];
_IndexMap[v[i]] = i;
}
_table.resize(n, nullptr);
}
size_t GetVertexIndex(const V& v)
{
auto ret = _IndexMap.find(v);
if (ret != _IndexMap.end())
{
return _IndexMap[v[i]];
}
return -1;
}
void AddEdge(const V& src, const V& dst, const W& w)
{
if (_IndexMap.find(src) != _IndexMap.end() &&
_IndexMap.find(dst) != _IndexMap.end() &&
_IndexMap.find(src) != _IndexMap.find(dst))
{
int srci = _IndexMap[src];
int dsti = _IndexMap[dst];
Edge* Ed = new Edge(dsti, w);
Ed->next = _table[srci];
_table[srci] = Ed;
if (Direction == false)
{
Edge* Ed = new Edge(srci, w);
Ed->next = _table[dsti];
_table[dsti] = Ed;
}
}
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
Edge* cur = _table[i];
cout << "_table" << "[" << i << "] :";
while (cur)
{
cout << "[" << cur->_dest << "]:"<<(_vertexs[cur->_dest].c_str())<<" ->";
cur = cur->next;
}
cout << "nullptr" << endl;
cout << endl;
}
}
private:
vector<V> _vertexs;//顶点集合
map<V, int> _IndexMap;//顶点和下标的映射关系
vector<Edge*> _table;//出边表
};
template<class V,class W,W Max_w = INT_MAX,bool Direction = false>
class Graph
{
typedef Graph<V, W, INT_MAX, Direction> Self;
public:
Graph() = default;
Graph(const V* v,size_t n)//图的外面会给进来一个v类型数组,将数组中的每一个元素都分散开来，存在对应的下标
{
_vertexs.resize(n);
for (int i = 0; i < n; i++)
{
_vertexs[i] = v[i];
_IndexMap[v[i]] = i;
}
_matrix.resize(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
_matrix[i].push_back(INT_MAX);
}
}
}
size_t GetVertexIndex(const V& v)
{
auto ret = _IndexMap.find(v);
if (ret != _IndexMap.end())
{
return _IndexMap[v[i]];
}
return -1;
}
void _AddEdge(size_t src, size_t dst, const W w)
{
_matrix[src][dst] = w;
if (Direction == false)
_matrix[src][dst] = w;
}
void AddEdge(const V& src, const V& dst, const W& w)
{
if (_IndexMap.find(src) != _IndexMap.end()&&
_IndexMap.find(dst) != _IndexMap.end()&&
_IndexMap.find(src) != _IndexMap.find(dst))
{
int j = _IndexMap[src];
int k = _IndexMap[dst];
_matrix[j][k] = w;
if (Direction == false)
_matrix[k][j] = w;
}
}
void Print()
{
cout << " ";
for (int i = 0; i < _matrix.size(); i++)
{
cout << i << " ";
}
cout << endl;
for (int i = 0; i < _matrix.size(); i++)
{
cout << i << " ";
for (int j = 0; j < _matrix[i].size(); j++)
{
if (_matrix[i][j] == INT_MAX)
{
cout << "*" << " ";
}
else
{
cout << _matrix[i][j] << " ";
}
}
cout << endl;
}
}
void BFS(size_t n)
{
//自己想的，还不错
//queue<vector<W>> q;
//vector<bool> index(_vertexs.size(),false);
//q.push(_matrix[n]);
//int Count = 1;
//index[n] = true;
//cout << _vertexs[n].c_str() << endl;
//while (!q.empty())
//{
// vector<W> vw = (q.front());
// q.pop();
// Count--;
// for (int i = 0; i < vw.size(); i++)
// {
// if (vw[i] != INT_MAX&&index[i]==false)
// {
// cout << _vertexs[i].c_str() << "[" << i << "]:" << " ";
// index[i] = true;
// q.push(_matrix[i]);
// }
// }
// if (Count == 0)
// {
// Count = q.size();
// cout << endl;
// }
//}
queue<int> q;
vector<bool> index(_vertexs.size(), false);
q.push(n);
int Count = 1;
size_t i = _vertexs.size();
index[n] = true;
cout << _vertexs[n].c_str() << endl;
while (!q.empty())
{
while (Count--)
{
int src = q.front();
q.pop();
for (int j = 0; j < i; j++)
{
if (_matrix[src][j] != INT_MAX&&index[j] == false)
{
cout << _vertexs[j].c_str() << "[" << j << "]:" << " ";
index[j] = true;
q.push(j);
}
}
}
Count = q.size();
cout << endl;
if (q.empty())
{
for (int j = 0; j < n;j++)
{
q.push(j);
break;
}
}
}
}
void DFS(size_t i)
{
int n = _vertexs.size();
vector<bool> index(n, false);
index[i] = true;
cout << _vertexs[i].c_str() << " ";
_DFS(i,index);
}
struct Edge
{
size_t _src;
size_t _dest;
W _w;
Edge(size_t src,size_t dest, const W& w)
:_src(src)
,_dest(dest)
, _w(w)
{}
bool operator>(const Edge& e2)const
{
return _w > e2._w;
}
};
W Kruskal(Self& mintree)
{
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
size_t n = _vertexs.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (_matrix[i][j] != INT_MAX)
{
Edge ed(i, j, _matrix[i][j]);
pq.push(ed);
}
}
}
W _w =W();
vector<bool> v(n, false);
UnioFindSet<int> ufs(n);
while (!pq.empty())
{
Edge e = pq.top();
pq.pop();
if (ufs.Union(e._src, e._dest))
{
cout << e._src << "->" << e._dest << ":" << e._w << endl;
mintree._AddEdge(e._src, e._dest, e._w);
_w += e._w;
n--;
}
}
if (n == 1)
{
return _w;
}
return W();
}
private:
void _DFS(size_t src, vector<bool>& index)
{
for (int i = 0; i < _vertexs.size();i++)
{
if (_matrix[src][i] != INT_MAX&&index[i] == false)
{
cout << _vertexs[i].c_str() << " ";
index[i] = true;
_DFS(i, index);
}
}
return;
}
private:
vector<V> _vertexs;//顶点集合
map<V, int> _IndexMap;//顶点和下标的映射关系
vector<vector<W>> _matrix;//顶点和顶点的权值关系
};
图是由顶点集合和顶点间的关系组成的数据结构：G=(V,E),其中顶点集合V={x|x属于某个数据对象集合}是有穷非空集合 E={(X,Y)|X,Y属于V是顶点与顶点之间关系的有穷集合} (x,y)表示x到y的一条双通路，既(x,y)是无向图的一条边，Path(x,y)表示从x到y是单通路的，既路劲为 x->y 顶点和边：途中的节点称为顶点，第i个顶点基座vi。两个顶点的vi和vj相连叫做vi和vj之间存在一条边 在有向图，顶点对<x,y>是有序的，既<x,y>和<y,x>是不同的
完全图：在n个顶点的无向图中，若存在n(n-1)/2（这个是等差数列，第一个点和剩下n-1个点存在链接，第二个点和n-2个点存在链接，依次推导）条边，既任意两个顶点之间存在有且仅有一条边，则称为完全无向图。有向图中，若存在n(n-1)条边，则任意两个顶点之间存在有且仅有方向相反的边，称为完全有向图，这个完全有向图是最稠密的图
邻接顶点：在无向图中，若(x,y)是无向图的一两个顶点，且存在一条边，则x和y互称为邻接顶点，并称为边(x,y)依附于顶点x和顶点y，在有向图中，若x，y是有向图的两个顶点，且存在边<x,y>u，则称为x邻接到y，y邻接到自定点x，并称边u和顶点x和顶点y相关联
顶点的度：顶点x的度，是指和x相关联边的条数，记作deg(v)，在有向图中顶点的度等于该顶点的入度和出度之和，在无向图中，顶底的度就是和顶点之间关联的边的条数
路径:从顶点vi触发有一组边使其可以达到顶点vj，则称为顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路劲 路劲长度:对于不带权的图，路径长度就是指该路径上的边的条数，带权的图的路径是能到到目的地的权值的和
子图：若存在图G，另外存在图U，图U的顶点为G中存在的顶点，图U的边在G中存在的边，就像是sub_str()
连通图：在无向图中，若存在顶点v1到顶点v2存在路径，称v1到v2连通。若任意一对顶点之间都是连通的，则称为图为连通图。 强连通图：在有向图中，若存在每一对顶点v1和v2之间存在一条v1到v2的路径，也存在一条从v2到v1的路径，称为此图为强连通图
生成树：一个连通图的最小连通子图称作图的生成树，有n个顶点的连通图的生成树存在n个顶点和n-1条边，生成树中禁止存在环型结构 最小生成树：在生成树的基础上，存在总路劲之和最小