图-数据结构

本文主要是介绍图-数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

常见表达图的形式有，邻接表：数组+链表
邻接矩阵：二维数组
从这组成结构上看，邻接表适合表达稀疏图，邻接矩阵适合表达稠密图
当然表达图结构的方式不止只有上面两种结构。

下面自己定义图的结构，由以下部分组成：
1.图的结构 a.顶点，b.边 ，c.图 d.图生成器
2.图的经典算法：a,深度优先搜索 ，b.广度优先搜索 ，c.拓扑排序 ，d.最小生成树p算法 e.单源最短路径dijkstra算法

// 图.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//2021.7.21
//尽量根据实际情况舍弃一些多余的结构，比如顶点，边，图数据类型，只保存对实际情况有用的数据，使空间复杂度尽可能的小

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

//前置声明
class Node;
class Edge;
class Grape;
class Grapegenerator;    //图生成器
//点
class Node {
public:
	int value;   //值
	int in;      //入度
	int out;      //出度
	//int key;
	vector<Node>* nexts;  //发散出去的点
	vector<Edge>* edges; //发散出去的边
	//构造函数
	Node(int val)
	{
		this->value = val;
		in = 0;                      //入度
		out = 0;                     //出度
		nexts = new vector<Node>();  //由该点发散出来的点集
		edges = new vector<Edge>();  //由该点发散出来的边集
	}
	bool operator < (const Node &a) const
	{
		return value < a.value;                  //图这个数据结构中，value 就是key,不存在两个值相同的顶点
	}
	//析构函数这可以不写  不可乱写，只要图不消亡就不能清内存  可以在图生成器的类中做析构，将所有new出来的数据清
	/*~Node() 
	{
		delete nexts;
		delete edges;
	}*/
};
/*
bool operator == (const Node& a,const Node &b)
{
	return a.value == b.value && a.in == b.in && a.out == b.out && a.nexts == b.nexts && a.edges == b.edges;
}
struct cmpp {
	int operator ()(const Node &a)const
	{
		int zhi = a.value;
		return std::hash<int>()(zhi);
	}
};*/
//边
class Edge {
public:
	int weight; //权重
	Node *from;  //从哪个点出发
	Node *to;    //去哪个点结束
	//构造函数
	Edge(int wgt, Node *from, Node *to) :weight(wgt), from(from), to(to) {}
	/*bool operator <(Edge &a)const
	{
		return weight > a.weight;
	}*/
};
struct cmp {
	bool operator ()(Edge &a,Edge &b)
	{
		return a.weight > b.weight;
	}
};
//图
class Grape {
public:
	unordered_map<int, Node>* nodes;
	unordered_map<string,Edge>* edges;               //点集和边集
	//构造函数
	Grape()
	{
		nodes = new unordered_map<int, Node>();   //每个点有个key作为其编号
		edges = new unordered_map<string,Edge>();    //每条边有个key 作为其编号
	}
	~Grape()
	{
		for (auto i : *nodes)
		{
			delete i.second.nexts;
		}
		delete nodes;
		delete edges;
	}
};

class Grapegenerator {
public:
	Grapegenerator(const vector<vector<int>> &inmtx)  //以一个二维数组作为输入 根据实际需要可以对图做剪枝（只保留所需要的信息）
	{
		mygrape = new Grape();
		for (int i = 0; i < inmtx.size(); i++)
		{
			int weight = inmtx[i][0];
			int from = inmtx[i][1];
			int to = inmtx[i][2];    //获取一组点的信息
			if (mygrape->nodes->find(from) == mygrape->nodes->end())
			{
				mygrape->nodes->emplace(from, Node(from));
			}
			if (mygrape->nodes->find(to) == mygrape->nodes->end())
			{
				mygrape->nodes->emplace(to, Node(to));                     //图的点集
			}
			Node *fromNode = &(mygrape->nodes->at(from));
			Node *toNode = &(mygrape->nodes->at(to));
			Edge newEdge = Edge(weight, fromNode, toNode);
			fromNode->out++;
			toNode->in++;
			fromNode->nexts->emplace_back(*toNode);
			fromNode->edges->emplace_back(newEdge);
			string edge_key = to_string(from); // keg_edge
			edge_key.push_back('-');
			edge_key += to_string(to);
			//cout << edge_key << endl;
			mygrape->edges->emplace(edge_key, newEdge);//给边做个标号     //图的边集
		}
	}
	~Grapegenerator()
	{
		delete mygrape;
	}
	//图的深度优先遍历  需要一个出发节点
	void dfs()
	{
		Node *node = &mygrape->nodes->at(1);   //选定一个出发点
		if (node == nullptr)
		{
			return;
		}
		stack<Node*> mystack;
		set<Node> hstable;
		mystack.push(node);
		hstable.emplace(*node);
		cout << node->value << endl;
		while (!mystack.empty())
		{
			Node *temp = mystack.top();
			mystack.pop();
			for (int i = 0; i < temp->nexts->size(); i++)
			{
				if (hstable.find(temp->nexts->at(i)) == hstable.end())
				{
					mystack.push(temp);
					mystack.push(&temp->nexts->at(i));
					hstable.emplace(temp->nexts->at(i));
					cout << temp->nexts->at(i).value << endl;
					break;    //退出进入下一个节点 栈中实际上是保存了深度优先遍历的路径
				}
			}
		}
	}
	//图的宽度优先遍历  需要一个出发节点  每一层的顺序不重要，但是层的关系要体现出来 队列
	void bfs()
	{

		Node *node = &(mygrape->nodes->at(1));
		if (node == nullptr)  //无效数据直接退出
		{
			return;
		}
		queue<Node *> myqueue;     //队列
		set<Node> hstable;         //备忘录
		myqueue.emplace(node);
		hstable.emplace(*node);
		while (!myqueue.empty())
		{
			int n = myqueue.size();
			vector<int> vec;
			for (int j = 0; j < n; j++)
			{
				Node *temp = myqueue.front();
				myqueue.pop();
				//cout << temp->value << endl;
				vec.emplace_back(temp->value);
				for (int i = 0; i < temp->nexts->size(); i++)
				{
					if (hstable.find(temp->nexts->at(i)) == hstable.end())   //查备忘录
					{
						hstable.emplace(temp->nexts->at(i));
						myqueue.push(&(temp->nexts->at(i)));
					}
				}
			}
			for (auto i : vec)
			{
				cout << i << ' ';
			}
			cout << endl;

		}
	}
	//拓朴排序    顶点之间的依赖关系  有向图 有入度为0的顶点，没有环
	vector<int> tpsort()
	{
		set<Node> hstable;
		queue<Node> myqueue;
		for (auto i : *(mygrape->nodes))
		{
			hstable.emplace(i.second);
			if (i.second.in == 0)
			{
				myqueue.push(i.second);
			}
		}
		vector<int> ans;
		while (!myqueue.empty())
		{
			Node temp = myqueue.front();
			myqueue.pop();
			ans.emplace_back(temp.value);    //压入值
			for (Node i : *(temp.nexts))
			{   //这里要注意，这里很奇怪，直接修改指针指向的内容会有问题
				Node next = *hstable.find(i);
				hstable.erase(hstable.find(i));   //清除之前的那个顶点
				next.in--;
				hstable.emplace(next);            //压入改变in之后的顶点
				
				if (hstable.find(i)->in == 0)
				{
					myqueue.push(i);
				}
			}
		}
		return ans;
	}
	//最小生成树p算法 k算法需要不断的合并集合，所以不推荐
	int ptree()
	{
		priority_queue<Edge,vector<Edge>,cmp> s_heal;   //以边的weight 由小权重开始排  小根堆
		//vector<Edge> ans;                    //存放结果
		int ans = 0;
		set<Node> hstable;                  //备忘录
		for (auto i:*(mygrape->nodes))      //任何一个起点
		{
			hstable.emplace(i.second);
			for (Edge j:*i.second.edges)   //由一个点解锁一票边
			{
				s_heal.emplace(j);
			}
			while (!s_heal.empty())
			{
				Edge temp = s_heal.top();      //取出权值最小的边
				s_heal.pop();
				if (hstable.find(*temp.to) == hstable.end())   //查备忘录
				{
					//ans.emplace_back(temp);
					ans += temp.weight;
					hstable.emplace(*temp.to);
					for (Edge next : *temp.to->edges)
					{
						s_heal.emplace(next);
					}
				}
			}
			break;
		}
		return ans;
	}

	//迪杰特斯拉算法 dijkstra  适合没有权值为负数的边的图
	//用最小的点去遍历能得到最优的结果
	Node getminandunusepoint(map<Node,int> &a,set<Node> &b)
	{
		int minval = INT_MAX;
		Node ans = Node(0);  //临时对象
		for (auto i : a)
		{
			Node node = i.first;
			int distance = i.second;
			if (b.find(node) == b.end() && distance<minval)
			{
				ans = node;
				minval = distance;
			}
		}
		return ans;
	}
	map<Node, int> dijkstra()
	{
		Node node = mygrape->nodes->at(1);    //起始点
		map<Node, int> distance;
		distance.emplace(node,0);         //自己到自己距离为0
		set<Node> hstable;      //存放已经摸过的点
		Node temp = getminandunusepoint(distance,hstable);  //获取最小可用的顶点
		while (temp.value != 0 )      //0一般不为出现，因为我们的图设定从1开始的
		{
			int dis = distance[temp];
			for (Edge i : *(temp.edges))                        //放入多个点
			{
				Node toNode = *i.to;
				if (distance.find(toNode) == distance.end())  //还没加入备忘录中
				{
					distance.emplace(toNode,i.weight+dis);
				}
				else {                                      //已经加入备忘录中的
					distance[toNode] = min(distance[toNode],i.weight+dis);
				}
			}
			hstable.emplace(temp);   //不可以用了
			temp = getminandunusepoint(distance,hstable);  //更新点
		}
		return distance;
	}
private:
	Grape* mygrape;
};


int main()
{
    
	cout << "********************开始*********************" << endl;
	cout << "图中有几个点" << endl;
	cout << "权重  from  to" << endl;
	vector<vector<int>> test;
	vector<int> temp;
	int n;
	cin >> n;
	for (int i = 0;i<n;i++)
	{
		for (int j = 0;j<3;j++)
		{
			int mid;
			cin >> mid;
			temp.emplace_back(mid);
		}
		test.emplace_back(temp);
		temp.clear();
	}
	Grapegenerator zj = Grapegenerator(test);
	//zj.bfs();
	//zj.dfs();
	/*vector<int> temp1;
	temp1 = zj.tpsort();
	for (int i:temp1)
	{
		cout << i << endl;
	}*/
	/*vector<Edge> myedge;
	myedge = zj.ptree();
	for (Edge i:myedge)
	{
		cout << i.weight << endl;
	}*/
	map<Node,int> ans;
	ans = zj.dijkstra();
	for (auto i : ans)
	{
		cout << i.first.value << ':' << i.second << endl;
	}
	return 0;
}

这篇关于图-数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！