數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）
/**
?* @brief 鄰接多重表
?* 解決無向圖,每條邊都要存儲(chǔ)兩遍的問題
?*/
#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 獲取節(jié)點(diǎn)的相鄰頂點(diǎn)的索引值
? ? ? ? /// @param idx
? ? ? ? /// @return
? ? ? ? int get_adjacenyIndex(int idx) const
? ? ? ? {
? ? ? ? ? ? return (idx == headvex_idx) ? tailvex_idx : headvex_idx;
? ? ? ? }
? ? ? ? /// @brief 獲取頂點(diǎn)的邊鏈表的下一個(gè)邊
? ? ? ? /// @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 生成一個(gè)條邊
? ? /// @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 頂點(diǎn)邊鏈表添加一條邊
? ? /// @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 打印邊節(jié)點(diǎn)信息
? ? /// @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 獲得頂點(diǎn)的鄰接頂點(diǎn)的索引的函數(shù)對(duì)象(記錄在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; // 邊節(jié)點(diǎn)
? ? ? ? ? ? _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;
? ? ? ? //---------------友元函數(shù)------------------------
? ? ? ? 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 圖的深度優(yōu)先遍歷
?*
?*/
#include "doo_AMGraph.hpp"
#include <bitset>
#include <iostream>
#include <queue>
namespace doo::graph
{
? ? /// @brief 深度優(yōu)先遍歷圖
? ? /// @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 廣度優(yōu)先遍歷圖
? ? /// @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;
///測(cè)試深度優(yōu)先和廣度優(yōu)先
?bitset<5> bset;
? ? dfs<char, 5>(multab, 0, bset);
? ? CR;
? ? bset.reset();
? ? bfs<char, 5>(multab, 0, bset);
? ? CR;
