实现图的过程中一些小笔记

ds

先放上最终代码

#pragma once
#include <iostream>
#include <vector>
#include <set>
#include "Edge.h"


class Graph
{
public:
	Graph() = default;

	Graph(size_t nodeNum)
	{
		tbl.resize(nodeNum);
	}

	~Graph()
	{
	}


	bool addEdge(size_t ID1, size_t ID2)
	{
		if (tbl[ID1].insert(Edge(ID2)).second && tbl[ID2].insert(Edge(ID1)).second) return true;
		return false;
	}

	void printGraph()
	{
		size_t nodeCounter = 0;
		for (auto& it : tbl)
		{
			std::cout << nodeCounter << "    ";
			for (auto& it2:it)
			{
				std::cout << it2<<" ";
			}
			std::cout << std::endl;
			++nodeCounter;
		}
	}

	std::vector<std::set<Edge>> tbl;
};



//分割线

#pragma once
#include <ostream>

class Edge
{
public:
	size_t ID;

	Edge() = default;

	Edge(size_t id): ID(id)
	{
	}

	friend std::ostream& operator<<(std::ostream& output, const Edge& D)
	{
		output << D.ID;
		return output;
	}
	bool operator < (const Edge& a) const
	{
		return this->ID < a.ID;
	}

};

//分割线

#include <iostream>
#include<vector>
#include "Graph.h"

using namespace std;


int main()
{
	auto p = new Graph(2);
	p->addEdge(0, 1);
	p->printGraph();
}

首先是graph定义的数据结构, 我使用了邻接表, 原型是vector<set<EDGE>>原因是我这个图不允许存在重复边, 所以使用了set

set需要把内容元素设定一个小于操作符, 如果不设定的话会报错很多东西, 没有明确提示是未设置小于符号

set不是用push_back添加, 而是insert, 返回值是pair, pair.first是偏移, pair.second是插入是否成功, 插入失败意味着插入了重复元素, 此时也会返回插入偏移在first里面

另外, 对于impl分离的写法, 可以采用tbl[0]来对impl指针解引用, 也可以用*解引用, 最终我没有选择分离写法, 因为对于指针的泄露管制会比较麻烦, 虽然可以用makeshared, 但是我这边还没有看完more EC上面的一个章节, 那个章节讲述了如何强制要求新建对象在heap上

另外, for range based loop 不能采用非引用的计数器, 因为有额外开销, 必须要采用auto& 这样省去了开销

在addEdge函数中, 我使用了短路求值优化,如果1到2有一条边并且false了, 就不会再做2到1的边添加了, 因为是同样重复的, 这里利用了短路求值