数据结构与算法基础（青岛大学-王卓）
/**
* @brief 邻接多重表
* 解决无向图,每条边都要存储两遍的问题
*/
#include "doo_graph.hpp"
#include <memory>
#include <vector>
#include <algorithm>
#include <iostream>
namespace doo::graph
{
/// @brief 边的定义
/// @tparam Info
template <typename Info>
struct _edge
{
Info info;
int headvex_idx;
int tailvex_idx;
std::shared_ptr<_edge<Info>> head_node;
std::shared_ptr<_edge<Info>> tail_node;
_edge() : info(Info()), headvex_idx(-1), tailvex_idx(-1),
head_node(nullptr), tail_node(nullptr) {}
_edge(int hidx, int tidx, const Info &inf)
: info(inf), headvex_idx(hidx), tailvex_idx(tidx),
head_node(nullptr), tail_node(nullptr) {}
/// @brief 获取节点的相邻顶点的索引值
/// @param idx
/// @return
int get_adjacenyIndex(int idx) const
{
return (idx == headvex_idx) ? tailvex_idx : headvex_idx;
}
/// @brief 获取顶点的边链表的下一个边
/// @param idx
/// @return
std::shared_ptr<_edge<Info>> &get_next(int idx)
{
return (idx == headvex_idx) ? head_node : tail_node;
}
};
template <typename Info>
std::ostream &operator<<(std::ostream &os, const _edge<Info> &edg)
{
return os << "{[" << edg.headvex_idx << ":" << edg.tailvex_idx << "]"
<< edg.info << "}";
}
/// @brief 边的定义
/// @tparam Info
template <typename Info>
using edge = std::shared_ptr<_edge<Info>>;
/// @brief 生成一个条边
/// @tparam T
/// @param hidx
/// @param tidx
/// @param inf
/// @return
template <typename T>
edge<T> make_edge(int hidx, int tidx, const T &inf)
{
return std::make_shared<_edge<T>>(hidx, tidx, inf);
}
template <typename Info, typename ObjFun>
void adj_mulTab_travelNode(edge<Info> node, int vexIdx, ObjFun proc)
{
while (node)
{
proc(node);
node = node->get_next(vexIdx);
}
}
/// @brief 顶点边链表添加一条边
/// @tparam Info
/// @param lst
/// @param vexidx
/// @param newNode
template <typename Info>
void adj_mulTab_push_back(edge<Info> &lst,
int vexidx,
const edge<Info> &newNode)
{
if (lst == nullptr)
{
lst = newNode;
}
else
{
edge<Info> tmp = lst;
edge<Info> tt = nullptr;
while (tmp)
{
tt = (*tmp).get_next(vexidx);
if (tt)
tmp = tt;
else
break;
}
tmp->get_next(vexidx) = newNode;
}
}
/// @brief 打印边节点信息
/// @tparam T
/// @tparam Info
template <typename T, typename Info>
class adj_mulTab_print
{
public:
adj_mulTab_print(std::ostream &os) : m_os(os) {}
void operator()(const edge<Info> &edge) const
{
m_os << *edge << " "
<< "->";
}
private:
std::ostream &m_os;
};
/// @brief 获得顶点的邻接顶点的索引的函数对象(记录在vector引用中)
/// @tparam T
/// @tparam Info
template <typename T, typename Info>
class adj_mulTab_getAdjacenyIdx
{
public:
adj_mulTab_getAdjacenyIdx(std::vector<int> &vet, int vexIdx)
: m_vet(vet), m_vexidx(vexIdx) {}
void operator()(const edge<Info> &edge) const
{
m_vet.push_back(edge->get_adjacenyIndex(m_vexidx));
}
private:
std::vector<int> &m_vet;
int m_vexidx;
};
/// @brief 链接多重表 (用来表示无向图)
/// @tparam T
/// @tparam Info
template <typename T, typename Info>
class adjacenty_mulTab : virtual public IGraph_search<T>
{
public:
adjacenty_mulTab() : m_array() {}
explicit adjacenty_mulTab(const std::initializer_list<T> &lst)
: adjacenty_mulTab()
{
for (auto val : lst)
m_array.push_back(_item(val));
}
void set_edge(const T &head, const T &tail, const Info &inf)
{
int hidx = get_index(head);
int tidx = get_index(tail);
if (hidx == -1 || tidx == -1)
return;
_set_edge(hidx, tidx, inf);
}
//------------IGraph_search接口--------------------------
const T &get_value(int vexIdx) const override
{
return m_array[vexIdx].value;
}
std::vector<int> get_ajacenyNode(int vexIdx) const override
{
std::vector<int> tmpVet;
adj_mulTab_travelNode(m_array[vexIdx].arcs, vexIdx,
adj_mulTab_getAdjacenyIdx<T, Info>(tmpVet, vexIdx));
return tmpVet;
}
private:
struct _item
{
T value;
edge<Info> arcs; // 边节点
_item() : value(T()), arcs(nullptr) {}
explicit _item(const T &val) : value(val), arcs(nullptr) {}
};
private:
int get_index(const T &val) const
{
int idx = 0;
for (auto im : m_array)
{
if (im.value == val)
return idx;
++idx;
}
return -1;
}
void _set_edge(int hidx, int tidx, const Info &inf)
{
edge<Info> newNode = make_edge(hidx, tidx, inf);
adj_mulTab_push_back(m_array[hidx].arcs,
hidx,
newNode);
adj_mulTab_push_back(m_array[tidx].arcs,
tidx,
newNode);
}
private:
std::vector<_item> m_array;
//---------------友元函数------------------------
friend std::ostream &operator<<(std::ostream &os, const adjacenty_mulTab &multab)
{
int idx = 0;
for (auto val : multab.m_array)
{
os << idx << "[" << val.value << "]-->";
adj_mulTab_travelNode(val.arcs, idx, adj_mulTab_print<T, Info>(os));
os << '\n';
++idx;
}
return os;
}
};
}
////接口定义
/// @brief 图的搜索接口
template <typename T>
struct IGraph_search
{
virtual const T &get_value(int vexIdx) const = 0;
virtual std::vector<int> get_ajacenyNode(int vexIdx) const = 0;
};
///DFS算法
#pragma once
/**
* @brief 图的深度优先遍历
*
*/
#include "doo_AMGraph.hpp"
#include <bitset>
#include <iostream>
#include <queue>
namespace doo::graph
{
/// @brief 深度优先遍历图
/// @tparam T
/// @tparam N
/// @param graph
/// @param vexIdx
/// @param bset
template <typename T, int N>
void dfs(const IGraph_search<T> &graph, int vexIdx, std::bitset<N> &bset)
{
std::cout << graph.get_value(vexIdx) << " ";
bset.set(vexIdx);
std::vector<int> vet = graph.get_ajacenyNode(vexIdx);
for (int i = 0; i < vet.size(); i++)
{
if (!bset.test(vet[i]))
dfs<T, N>(graph, vet[i], bset);
}
}
/// @brief 广度优先遍历图
/// @tparam T
/// @tparam N
/// @param graph
/// @param vexIdx
/// @param bset
template <typename T, int N>
void bfs(const IGraph_search<T> &graph,
int vexIdx,
std::bitset<N> &bset)
{
std::queue<int> que;
que.push(vexIdx);
while (!que.empty())
{
int vidx = que.front();
que.pop();
if (!bset.test(vidx))
std::cout << graph.get_value(vidx) << " ";
bset.set(vidx);
std::vector<int> vet = graph.get_ajacenyNode(vidx);
for (int i = 0; i < vet.size(); i++)
if (!bset.test(vet[i]))
que.push(vet[i]);
}
}
}
//-------------------------------用法---------------
adjacenty_mulTab<char, int> multab({'A', 'B', 'C', 'D', 'E'});
multab.set_edge('A', 'B', 0);
multab.set_edge('A', 'D', 0);
// multab.set_edge('A','C',0);
multab.set_edge('B', 'C', 0);
multab.set_edge('B', 'E', 0);
multab.set_edge('C', 'E', 0);
multab.set_edge('C', 'D', 0);
cout << multab << endl;
///测试深度优先和广度优先
bitset<5> bset;
dfs<char, 5>(multab, 0, bset);
CR;
bset.reset();
bfs<char, 5>(multab, 0, bset);
CR;
