数据结构和算法---图（C++）

图结构以及对应算法

---

最近博主在学习数据结构和算法，主要的学习资料有b站上浙江大学课程数据结构和算法以及《大话数据结构》，这两个用来入门比较不错，但他们都是用c语言来实现，因此博主使用c++来实现图这一复杂结构以及对应的算法。存储结构使用了邻接矩阵、邻接表以及边集数组，分别实现了最小生成树、最短路径以及有向无环图三种应用，其中最小生成树使用了Prim算法、Kruskal算法，最短路径使用了Dijkstra算法、Floyd算法，有向无环图使用了拓扑排序以及关键路径的两种应用。以下是代码：

graph的头文件：

#pragma once
#include<iostream>
#include<fstream>
#include<stack>
using namespace std;
const int MaxVertex = 14;
typedef struct ENode* Edge;


struct Node
{
	int m_Data;
	bool m_visited;
};

struct ENode
{
	int v1, v2;
	int weight;
};

class MGraph
{
private:
	int m_Nv;//节点
	int m_Ne;//边数
	int G[MaxVertex][MaxVertex];
	Node* pNodeArray;
public:
	MGraph(int VertexNum);
	void InsertEdge(int v1,int v2,int weight);
	void InputData(int Vertex,int data);
	void ShowWeight(int v1, int v2);
	void DFS(int Vertex);
	void BFS(int Vertex);
	void MinTree_Prim(int parent[MaxVertex]);
	void MinTree_Kruskal(int parent[MaxVertex]);
	void Dijkstra(int Vertex1,int Vertex2);
	void Floyd(int Vertex1, int Vertex2);
	void GetNodeData(int Vertex) ;
	~MGraph();
};


struct EdgeNode
{
	int m_CurNode;
	int m_Weight;
	struct EdgeNode* next;
};

struct VertexNode
{
	int m_Data;
	int m_in;
	bool m_Visit;
	bool m_Kusal;
	int m_Earliest;
	int m_Latest;
	EdgeNode* FirstEdge;
};


struct EdgeMaxtrix
{
	int m_Begin;
	int m_End;
	int m_Weight;
};


class ALGraph
{
private:
	int m_Nv;//节点
	int m_Ne;//边数
	VertexNode AdjList[MaxVertex];
public:
	ALGraph(int VertexNum);
	void InsertEdge(int v1, int v2, int weight);
	void InputData(int Vertex, int data);
	void ShowWeight(int v1, int v2);
	void DFS(int Vertex);
	void BFS(int Vertex);
	void MinTree_Prim(int parent[MaxVertex]);
	void MinTree_Kruskal(int parent[MaxVertex]);
	void Dijkstra();
	void GetNodeData(int Vertex);
	void GetInNode(int Vertex);
	bool TopoSort();
	bool TopoSortUseCriticalPath(stack<int> & s2);
	void CriticalPath();
	~ALGraph();
};


bool compare(EdgeMaxtrix E1, EdgeMaxtrix E2);
int Find(int* parent, int f);

graph的实现文件：

#include<iostream>
#include"graph.h"
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int mINFINITY = 655550;

MGraph::MGraph(int VertexNum)
{
	int v, w;
	this->m_Nv = VertexNum;
	this->m_Ne = 0;
	for (v = 0; v < VertexNum; v++)
		for (w = 0; w < VertexNum; w++)
			if (v == w)
			{
				G[v][w] = 0;
			}
			else
			{
				G[v][w] = mINFINITY;
			}

	this->pNodeArray = new Node[VertexNum];
	for (int i = 0; i < VertexNum; i++)
	{
		this->pNodeArray[i].m_visited = 0;
	}
}

void MGraph::InsertEdge(int v1, int v2, int weight)
{
	G[v1][v2] = weight;
	G[v2][v1] = weight;
	this->m_Ne++;
}


void MGraph::InputData(int Vertex, int data)
{
	pNodeArray[Vertex].m_Data = data;
}

void MGraph::ShowWeight(int v1, int v2)
{
	if (this->G[v1][v2] != mINFINITY)
	{
		cout << v1 << " 相连 " << v2 << "  " << G[v1][v2] << endl;
	}
	else
	{
		cout << "没有相连" << endl;
	}
}

void MGraph::DFS(int Vertex)
{
	int val = Vertex;
	this->pNodeArray[Vertex].m_visited = true;
	cout << this->pNodeArray[Vertex].m_Data << " ";
	for (int i = 0; i < this->m_Nv; i++)
	{
		if (val != i && G[i][val] != mINFINITY )
		{
			if (this->pNodeArray[i].m_visited == false)
			{
				DFS(i);
			}
		}
	}
}

void MGraph::BFS(int Vertex)
{
	queue<int> q1;
	int temp;
	int val = Vertex;
	this->pNodeArray[Vertex].m_visited = true;
	cout << this->pNodeArray[Vertex].m_Data << " ";
	q1.push(Vertex);
	while (!q1.empty())
	{
		temp = q1.front();
		q1.pop();
		for (int i = 0; i < this->m_Nv; i++)
		{
			if (temp != i && G[temp][i] != mINFINITY)
			{
				if (this->pNodeArray[i].m_visited == false)
				{
					this->pNodeArray[i].m_visited = true;
					cout << this->pNodeArray[i].m_Data << " ";
					q1.push(i);
				}
			}
		}
	}
}

void MGraph::MinTree_Prim(int parent[MaxVertex])
{
	int lowcost[MaxVertex];
	/*int parent[MaxVertex];*/
	
	lowcost[0] = 0;
	parent[0] = 0;
	for (int j = 1; j < this->m_Nv; j++)
	{
		lowcost[j] = this->G[0][j];
		parent[j] = 0;
	}
	while (1)
	{
		int min = mINFINITY;
		int temp;
		//找到lowcost除了0之外的最小值
		for (int i = 1; i < this->m_Nv; i++)
		{
			if (lowcost[i] != 0 && lowcost[i] < min)
			{
				min = lowcost[i];
				temp = i;
			}
    	}
		if (min == mINFINITY)
			break;
		lowcost[temp] = 0;
		cout << parent[temp] << " " << temp << endl;

		for (int i = 1; i < this->m_Nv; i++)
		{
			if (lowcost[i] != 0 && this->G[temp][i] < lowcost[i])
			{
				lowcost[i] = this->G[temp][i];
				parent[i] = temp;
			}
		}
	}
}

void MGraph::MinTree_Kruskal(int parent[MaxVertex])
{
	vector< EdgeMaxtrix> Edge(this->m_Ne);
	int k = 0;
	int n, m;
	for (int i = 0; i < this->m_Nv; i++)
	{
		for (int j = i+1; j < this->m_Nv; j++)
		{
			if (this->G[i][j] != 0 && this->G[i][j] < mINFINITY)
			{
				Edge[k].m_Begin = i;
				Edge[k].m_End = j;
				Edge[k].m_Weight = this->G[i][j];
				k++;
			}
		}
	}

	sort(Edge.begin(), Edge.end(), compare);



	for (int i = 0; i < this->m_Nv; i++)
		parent[i] = 0;
	for (int i = 0; i < this->m_Ne; i++)
	{
		n = Find(parent, Edge[i].m_Begin);
		m = Find(parent, Edge[i].m_End);
		if (n != m)
		{
			parent[n] = m;
			cout << n << " " << m << " " << Edge[i].m_Weight << endl;
		}
	}

}

void MGraph::Dijkstra(int Vertex1, int Vertex2)
{
	int Patharc[MaxVertex];
	int ShortPathWeight[MaxVertex];
	int final[MaxVertex];
	int min;
	int j,k = 0;
//初始化Parent和ShortPathWeight
	for (int i = 0; i < this->m_Nv; i++)
	{
		final[i] = 0;
		Patharc[i] = -1;
		ShortPathWeight[i] = this->G[Vertex1][i];
	}
	final[Vertex1] = 1;
	for (int i = 1; i < this->m_Nv; i++)
	{
		min = mINFINITY;
		for (j = 0; j < this->m_Nv; j++)
		{
			if (!final[j] && ShortPathWeight[j] < min)
			{
				min = ShortPathWeight[j];
				k = j;
			}
		}

		final[k] = 1;

		for (int i = 0; i < this->m_Nv; i++)
		{
			if (!final[i] && (min + this->G[k][i] < ShortPathWeight[i]))
			{
				ShortPathWeight[i] = min + this->G[k][i];
				Patharc[i] = k;
			}
		}
	}
	
	cout << "最短路径为： ";
	Patharc[Vertex1] = -2;
	int temp = Vertex2;
	cout << Vertex2 << " ";
	while (Patharc[temp] != -2)
	{
		if (Patharc[temp] >= 0)
		{
			temp = Patharc[temp];
			
		}
		else if (Patharc[temp] == -1)
		{
			temp = Vertex1;
		}
		cout << temp << " ";
	}
	cout << endl;
	cout << "权值最小为： ";
	cout << ShortPathWeight[Vertex2] << endl;
}

void MGraph::Floyd(int Vertex1, int Vertex2)
{
	int Patharc[MaxVertex][MaxVertex];
	int ShortPath[MaxVertex][MaxVertex];
	for (int i = 0; i < this->m_Nv; i++)
	{
		for (int j = 0; j < this->m_Nv; j++)
		{
			ShortPath[i][j] = this->G[i][j];
			Patharc[i][j] = j;
		}
	}
	for (int k = 0; k < this->m_Nv; k++)
	{
		for (int i = 0; i < this->m_Nv; i++)
			for (int j = 0; j < this->m_Nv; j++)
				if (ShortPath[i][j] > ShortPath[i][k] + ShortPath[k][j])
				{
					ShortPath[i][j] = ShortPath[i][k] + ShortPath[k][j];
					Patharc[i][j] = Patharc[i][k];
				}
	}

	//for (int i = 0; i < this->m_Nv; i++)
	//{
	//	for (int j = 0; j < this->m_Nv; j++)
	//	{
	//		cout << ShortPath[i][j] << " ";
	//	}
	//	cout << endl;
	//}


	cout << "最短路径为：";
	int f = Vertex1;
	while (f != Vertex2)
	{
		cout << f << " ";
		f = Patharc[f][Vertex2];
	}
	cout << f << " " << endl;
	cout << "最小权值为：" << ShortPath[Vertex1][Vertex2] << endl;
}

void MGraph::GetNodeData(int Vertex)
{
	cout << this->pNodeArray[Vertex].m_Data << " ";
}


MGraph::~MGraph()
{
	delete[] this->pNodeArray;
}



ALGraph::ALGraph(int VertexNum)
{
	this->m_Nv = VertexNum;
	this->m_Ne = 0;
	for (int i = 0; i < VertexNum; i++)
	{
		this->AdjList[i].FirstEdge = nullptr;
		this->AdjList[i].m_Visit = 0;
		this->AdjList[i].m_Kusal = 0;
		this->AdjList[i].m_in = 0;
		this->AdjList[i].m_Earliest = 0;
		this->AdjList[i].m_Latest = 0;
	}

}

void ALGraph::InsertEdge(int v1, int v2, int weight)
{
	EdgeNode* e = new EdgeNode;
	e->m_Weight = weight;
	e->m_CurNode = v2;
	e->next = this->AdjList[v1].FirstEdge;
	this->AdjList[v1].FirstEdge = e;
	this->AdjList[v2].m_in = this->AdjList[v2].m_in + 1;
	//EdgeNode* e1 = new EdgeNode;
	//e1->m_Weight = weight;
	//e1->m_CurNode = v1;
	//e1->next = this->AdjList[v2].FirstEdge;
	//this->AdjList[v2].FirstEdge = e1;

	//this->m_Ne++;
}

void ALGraph::InputData(int Vertex, int data)
{
	AdjList[Vertex].m_Data = data;
}

void ALGraph::ShowWeight(int v1, int v2)
{
	EdgeNode* e = this->AdjList[v1].FirstEdge;

	while (e != nullptr)
	{
		if (e->m_CurNode == v2)
		{
			cout << v1 << " 相连 " << v2 << "  " << e->m_Weight << endl;
			return;
		}
		e = e->next;
	}
	cout << "没有相连" << endl;
}

void ALGraph::DFS(int Vertex)
{
	EdgeNode* e = this->AdjList[Vertex].FirstEdge;
	int val = Vertex;
	this->AdjList[Vertex].m_Visit = true;
	cout << this->AdjList[Vertex].m_Data << " ";
	while(e != nullptr)
	{
		if (this->AdjList[e->m_CurNode].m_Visit == false)
		{
			DFS(e->m_CurNode);
		}
		e = e->next;
	}
}

void ALGraph::BFS(int Vertex)
{
	EdgeNode* e ;
	queue<int> q1;
	int temp;
	int val = Vertex;
	this->AdjList[Vertex].m_Visit = true;
	cout << this->AdjList[Vertex].m_Data << " ";
	q1.push(Vertex);
	while (!q1.empty())
	{
		temp = q1.front();
		q1.pop();
		e = this->AdjList[temp].FirstEdge;
		while (e != nullptr)
		{
			if (this->AdjList[e->m_CurNode].m_Visit == false)
			{
				this->AdjList[e->m_CurNode].m_Visit = true;
				cout << this->AdjList[e->m_CurNode].m_Data << " ";
					q1.push(e->m_CurNode);
			}
			e = e->next;
		}
	}
}

void ALGraph::MinTree_Prim(int parent[MaxVertex])
{
	int lowcost[MaxVertex];
	lowcost[0] = 0;
	parent[0] = 0;
	for (int j = 1; j < this->m_Nv; j++)
	{
		lowcost[j] = mINFINITY;
		parent[j] = 0;
	}
	EdgeNode* e = this->AdjList[0].FirstEdge;
	while (e != nullptr)
	{
		lowcost[e->m_CurNode] = e->m_Weight;
		e = e->next;
	}

	while (1)
	{
		int min = mINFINITY;
		int temp;
		//找到lowcost除了0之外的最小值
		for (int i = 1; i < this->m_Nv; i++)
		{
			if (lowcost[i] != 0 && lowcost[i] < min)
			{
				min = lowcost[i];
				temp = i;
			}
		}
		if (min == mINFINITY)
			break;
		lowcost[temp] = 0;
		cout << parent[temp] << " " << temp << endl;
		EdgeNode* e1 = this->AdjList[temp].FirstEdge;
		while (e1 != nullptr)
		{
			if (e1->m_Weight < lowcost[e1->m_CurNode])
			{
				lowcost[e1->m_CurNode] = e1->m_Weight;
				parent[e1->m_CurNode] = temp;
			}
			e1 = e1->next;
		}
	}
}

void ALGraph::MinTree_Kruskal(int parent[MaxVertex])
{
	vector< EdgeMaxtrix> Edge(this->m_Ne);
	int k = 0;
	int n, m;


	for (int i = 0; i < this->m_Nv; i++)
	{
		EdgeNode* e = this->AdjList[i].FirstEdge;
		this->AdjList[i].m_Kusal = true;
		while (e != nullptr)
		{
			if (this->AdjList[e->m_CurNode].m_Kusal == false)
			{
				Edge[k].m_Begin = i;
				Edge[k].m_End = e->m_CurNode;
				Edge[k].m_Weight = e->m_Weight;
				k++;	
			}
			e = e->next;
		}
	}

	sort(Edge.begin(), Edge.end(), compare);

	for (int i = 0; i < this->m_Nv; i++)
		parent[i] = 0;
	for (int i = 0; i < this->m_Ne; i++)
	{
		n = Find(parent, Edge[i].m_Begin);
		m = Find(parent, Edge[i].m_End);
		if (n != m)
		{
			parent[n] = m;
			cout << n << " " << m << " " << Edge[i].m_Weight << endl;
		}
	}
}

void ALGraph::GetNodeData(int Vertex)
{
	cout << this->AdjList[Vertex].m_Data << " ";
}

void ALGraph::GetInNode(int Vertex)
{
	cout << this->AdjList[Vertex].m_in << " ";
}

bool ALGraph::TopoSort()
{
	int temp,count = 0;
	int k;
	EdgeNode* e;
	stack<int> s;
	for (int i = 0; i < this->m_Nv; i++)
	{
		if (0 == this->AdjList[i].m_in)
			s.push(i);
	}

	while (!s.empty())
	{
		temp = s.top();
		s.pop();
		cout << this->AdjList[temp].m_Data << " ";
		count++;
		for (e = this->AdjList[temp].FirstEdge; e != nullptr; e = e->next)
		{
			k = e->m_CurNode;
			this->AdjList[k].m_in--;
			if(!this->AdjList[k].m_in)
				s.push(k);
		}
	}

	if (count < this->m_Nv)
	{
		cout << "有环" << endl;
		return false;
	}
	else
		return true;

}

bool ALGraph::TopoSortUseCriticalPath(stack<int>& s2)
{
	int temp, count = 0;
	int k;
	EdgeNode* e;
	stack<int> s1;

	for (int i = 0; i < this->m_Nv; i++)
	{
		if (0 == this->AdjList[i].m_in)//把度为0的节点压栈
			s1.push(i);
	}

	while (!s1.empty())
	{
		temp = s1.top();
		s1.pop();
		count++;
		s2.push(temp);
		for (e = this->AdjList[temp].FirstEdge; e != nullptr; e = e->next)
		{
			k = e->m_CurNode;
			this->AdjList[k].m_in--;
			if (!this->AdjList[k].m_in)
				s1.push(k);
			if (this->AdjList[temp].m_Earliest + e->m_Weight > this->AdjList[k].m_Earliest)
				this->AdjList[k].m_Earliest = this->AdjList[temp].m_Earliest + e->m_Weight;
		}
	}

	if (count < this->m_Nv)
	{
		cout << "有环" << endl;
		return false;
	}
	else
		return true;
}

void ALGraph::CriticalPath()
{
	EdgeNode* Node;
	stack<int> s;
	int ete;
	int lte;
	int temp;
	this->TopoSortUseCriticalPath(s);
	for (int i = 0; i < this->m_Nv; i++)
	{
		this->AdjList[i].m_Latest = this->AdjList[this->m_Nv - 1].m_Earliest;
	}

	//计算latest time
	while (!s.empty())
	{
		temp = s.top();
		s.pop();

		for (Node = this->AdjList[temp].FirstEdge; Node != nullptr; Node = Node->next)
		{
			if (this->AdjList[Node->m_CurNode].m_Latest - Node->m_Weight < this->AdjList[temp].m_Latest)
				this->AdjList[temp].m_Latest = this->AdjList[Node->m_CurNode].m_Latest - Node->m_Weight;
		}
	}

	for (int j = 0; j < this->m_Nv; j++)
	{
		for (Node = this->AdjList[j].FirstEdge; Node != nullptr; Node = Node->next)
		{
			ete = this->AdjList[j].m_Earliest;
			lte = this->AdjList[Node->m_CurNode].m_Latest - Node->m_Weight;
			if (ete == lte)
			{
				cout << j << " ";
			}
		}
	}
	cout << this->m_Nv - 1;
}

ALGraph::~ALGraph()
{
	EdgeNode* e;

	for (int i = 0; i < this->m_Nv; i++)
	{
		e = this->AdjList[i].FirstEdge;
		while (e != nullptr)
		{
            this->AdjList[i].FirstEdge = this->AdjList[i].FirstEdge->next;
			delete e;
			e = this->AdjList[i].FirstEdge;
		}
	}
}

bool compare(EdgeMaxtrix E1, EdgeMaxtrix E2)
{
	return E1.m_Weight < E2.m_Weight;
}

int Find(int* parent, int f)
{
	while (parent[f] > 0)
		f = parent[f];
	return f;
}

main文件

#include<iostream>
#include"graph.h"
using namespace std;


int main()
{
	ifstream ifs;
	ifs.open("yao.txt");
	int parent[MaxVertex];
	int VertexNum,EdgeNum,data;
	int Vertex1, Vertex2, Weight;
	ifs >> VertexNum >> EdgeNum;

	ALGraph A1(VertexNum);
	for (int i = 0; i < VertexNum; i++)
	{
		ifs >> data;
		A1.InputData(i, data);
	}
	for (int i = 0; i < EdgeNum; i++)
	{
		ifs >> Vertex1 >> Vertex2 >> Weight;
		A1.InsertEdge(Vertex1, Vertex2, Weight);
	}

	A1.CriticalPath();
	system("pause");
	return 0;
}