图(有向图,无向图)的邻接矩阵表示C++实现(遍历,拓扑排序,最短路径,最小生成树) Implement of digraph and undigraph using adjacency matrix

本文实现了有向图,无向图的邻接矩阵表示,并且实现了从创建到销毁图的各种操作。

以及两种图的深度优先遍历,广度优先遍历,Dijkstra最短路径算法,Prim最小生成树算法,有向图的拓扑排序算法。

 

通过一个全局变量控制当前图为有向图还是无向图。

若为无向图,则生成的邻接矩阵是对称的,有向图则不对称。

 

PS: 等有时间了作详细的讲解。

#include <iostream>
#include <climits>
#include <sstream> 
#include <queue>
using namespace std;

const bool UNDIGRAPH = 0;
struct Graph
{
	string *vertexLabel;//the number of the labels is equal to vertexes
	int vertexes;
	int edges;
	int **AdjMat;
	bool *visited;//only for DFS,BFS,Dijkstra
	int *distance; //only for Dijkstra
	int *path;//only for Dijkstra
};

void BuildGraph(Graph *&graph, int n)
{
	if (graph == NULL)
	{
		graph = new Graph;
		graph->vertexes = n;
		graph->edges = 0;
		graph->AdjMat = new int *[n];
		graph->vertexLabel = new string[n];
		graph->visited = new bool[n];
		graph->distance = new int[n];
		graph->path = new int[n];
		for (int i = 0; i < graph->vertexes; i++)
		{
			stringstream ss;  
			ss<<"v" << i+1;  
			ss >> graph->vertexLabel[i];
			graph->visited[i] = false;
			graph->distance[i] = INT_MAX;
			graph->path[i] = -1;
			graph->AdjMat[i] = new int[n];

			if(UNDIGRAPH)
				memset(graph->AdjMat[i],0, n * sizeof(int));
			else
			for (int j = 0; j < graph->vertexes; j++)
			{
				if(i == j)
					graph->AdjMat[i][j] = 0;
				else
					graph->AdjMat[i][j] = INT_MAX;
			}
		}
	}
}

void MakeEmpty(Graph *&graph)
{
	if(graph == NULL)
		return;

	delete []graph->vertexLabel;
	delete []graph->visited;
	delete []graph->distance;
	delete []graph->path;
	for (int i = 0; i < graph->vertexes; i++)
	{
		delete []graph->AdjMat[i];
	}
	delete []graph->AdjMat;
	delete graph;
}

void AddEdge(Graph *graph,int v1, int v2, int weight)
{
	if (graph == NULL) return;
	if (v1 < 0 || v1 > graph->vertexes-1) return;
	if (v2 < 0 || v2 > graph->vertexes-1) return;
	if (v1 == v2) return; //no loop is allowed

	if(UNDIGRAPH)
	{
		if (graph->AdjMat[v1][v2] == 0)//not exist,edges plus 1  
			graph->edges++;
		graph->AdjMat[v1][v2] = graph->AdjMat[v2][v1] = weight;
	}
	
	else
	{
		if (graph->AdjMat[v1][v2] == 0 || graph->AdjMat[v1][v2] == INT_MAX)//not exist,edges plus 1
			graph->edges++;
		graph->AdjMat[v1][v2] = weight;
	}
}

void RemoveEdge(Graph *graph, int v1, int v2)
{
	if (graph == NULL) return;
	if (v1 < 0 || v1 > graph->vertexes-1) return;
	if (v2 < 0 || v2 > graph->vertexes-1) return;
	if (v1 == v2) return; //no loop is allowed

	if (UNDIGRAPH)
	{
		if (graph->AdjMat[v1][v2] == 0)//not exists,return  
			return;
		graph->AdjMat[v1][v2] = graph->AdjMat[v2][v1] = 0;  
		graph->edges--;  
	}

	else
	{
		if (graph->AdjMat[v1][v2] == 0 || graph->AdjMat[v1][v2] == INT_MAX)//not exists,return
			return;
		graph->AdjMat[v1][v2] = INT_MAX;
		graph->edges--;
	}
}

int GetIndegree(Graph *graph, int v)
{
	if(graph == NULL) return -1;
	if(v < 0 || v > graph->vertexes -1) return -2;
	if(UNDIGRAPH) return -3;
	int degree = 0;
	for (int i = 0; i < graph->vertexes; i++)
	{
		if(graph->AdjMat[i][v] != 0 && graph->AdjMat[i][v] != INT_MAX)
			degree++;
	}
	return degree;
}

int GetOutdegree(Graph *graph, int v)
{
	if(graph == NULL) return -1;
	if(v < 0 || v > graph->vertexes -1) return -2;
	if(UNDIGRAPH) return -3;
	int degree = 0;
	for (int i = 0; i < graph->vertexes; i++)
	{
		if(graph->AdjMat[v][i] != 0 && graph->AdjMat[v][i] != INT_MAX)
			degree++;
	}
	return degree;
}

int GetDegree(Graph *graph, int v)
{
	if(graph == NULL) return -1;
	if(v < 0 || v > graph->vertexes -1) return -2;

	if(UNDIGRAPH)
	{
		int degree = 0;  
		for (int i = 0; i < graph->vertexes; i++)  
		{  
			if(graph->AdjMat[v][i] != 0)  
				degree++;  
		}  
		return degree;  
	}
	else
	return GetIndegree(graph,v) + GetOutdegree(graph,v);
}

void PrintGraph(Graph *graph)
{
	if(graph == NULL)
		return;
	cout << "Vertex: " << graph->vertexes <<"\n";
	cout << "Edge: " << graph->edges << "\n";

	for (int i = 0; i < graph->vertexes; i++)
	{
		cout << "  "<< graph->vertexLabel[i];
	}
	cout << "\n";

	for (int i = 0; i < graph->vertexes; i++)
	{
		for (int j = 0; j < graph->vertexes; j++)
		{
			if(j == 0)
				cout << graph->vertexLabel[i] << " ";

			if(graph->AdjMat[i][j] == INT_MAX)
				cout << "~" << "   ";
			else
				cout << graph->AdjMat[i][j] << "   ";
		}
		cout << "\n";
	}
	cout << "\n";
}

//depth first search (use stack or recursion)
//DFS is similar to preorder traversal of trees
void DFS(Graph *graph, int i)
{
	if (!graph->visited[i])
	{
		cout << graph->vertexLabel[i] << " ";
		graph->visited[i] = true;
	}
	
	for (int j = 0; j < graph->vertexes; j++)
	{
		if (UNDIGRAPH)
		{
			if (graph->AdjMat[i][j] != 0 && !graph->visited[j])
				DFS(graph,j);
		}
		else
		{
			if (graph->AdjMat[i][j] != INT_MAX && !graph->visited[j])
				DFS(graph,j);
		}
	}
}

void BeginDFS(Graph *graph)
{
	if(graph == NULL) return;
	cout << "DFS\n";
	for (int i = 0; i < graph->vertexes; i++)
		graph->visited[i] = false;

	for (int i = 0; i < graph->vertexes; i++)
		DFS(graph,i);
}
//breadth first search(use queue)
//BFS is similar to leverorder traversal of trees
//all of the vertexes will be searched once no matter how the digraph is constructed
void BFS(Graph *graph)
{
	if(graph == NULL)
		return;
	cout << "BFS\n";

	memset(graph->visited,false,graph->vertexes * sizeof(bool));
	queue<int> QVertex;

	for (int i = 0; i < graph->vertexes; i++)
	{
		if (!graph->visited[i])
		{
			QVertex.push(i);
			cout << graph->vertexLabel[i] << " ";
			graph->visited[i] = true;
			while(!QVertex.empty())
			{
				int vtxNO = QVertex.front();
				QVertex.pop();
				for (int j = 0; j < graph->vertexes; j++)
				{
					if (UNDIGRAPH)
					{
						if(!graph->visited[j] && graph->AdjMat[vtxNO][j]!=0)
						{
							cout << graph->vertexLabel[j] << " ";
							graph->visited[j] = true;
							QVertex.push(j);
						}
					}
					else
					{
						if(!graph->visited[j] && graph->AdjMat[vtxNO][j]!=INT_MAX)
						{
							cout << graph->vertexLabel[j] << " ";
							graph->visited[j] = true;
							QVertex.push(j);
						}
					}
					
				}
			}
		}
	}

	cout << "\n";
}

//after executing this function,the value of AdjMat changed
void TopologicalSort(Graph *graph)
{
	if(UNDIGRAPH) return;
	if(graph == NULL) return;
	cout << "TopologicalSort"<<"\n";
	int counter = 0;
	queue <int> qVertex;
	for (int i = 0; i < graph->vertexes; i++)
	{
		if(GetIndegree(graph,i) == 0)
			qVertex.push(i);
	}
	while (!qVertex.empty())
	{
		int vertexNO = qVertex.front();
		counter++;

		cout << graph->vertexLabel[vertexNO];
		if(counter != graph->vertexes)
			cout << " > ";
		qVertex.pop();
		for (int i = 0; i < graph->vertexes; i++)
		{
			if(i == vertexNO) 
				continue;

			if (GetIndegree(graph,i) != 0)
			{
				graph->AdjMat[vertexNO][i] = INT_MAX;//indegree--
				if(GetIndegree(graph,i) == 0)
					qVertex.push(i);
			}
		}
	}
	cout << "\n";
}

void Dijkstra(Graph *graph, int v)
{
	if(graph == NULL) return;
	if(v < 0 || v > graph->vertexes-1) return;

	for (int i = 0; i < graph->vertexes; i++)
	{
		graph->visited[i] = false;
		graph->distance[i] = INT_MAX;//can delete this line,as initialized in BuildGraph
		graph->path[i] = -1;
	}

	graph->distance[v] = 0;//the rest are all INT_MAX

	while(1)
	{
		int minDisInx = -1;
		int minDis = INT_MAX;
		for (int i = 0; i < graph->vertexes; i++)
		{
			if(!graph->visited[i])
			{
				if(graph->distance[i] < minDis)
				{
					minDis = graph->distance[i];
					minDisInx = i;
				}
			}
		}
		if(minDisInx == -1)//all visited
			break;

		graph->visited[minDisInx] = true;

		for (int i = 0; i < graph->vertexes; i++)
		{
			//unvisited and adjacent to current vertex
			//&& graph->AdjMat[minDisInx][i]!=0 is for undigraph
			if (!graph->visited[i] && graph->AdjMat[minDisInx][i]!=INT_MAX && graph->AdjMat[minDisInx][i]!=0)
			{
				if (graph->distance[minDisInx] + graph->AdjMat[minDisInx][i] < graph->distance[i])
				{
					graph->distance[i] = graph->distance[minDisInx] + graph->AdjMat[minDisInx][i];
					graph->path[i] = minDisInx;
					cout << graph->vertexLabel[i] << " Updated to " << graph->distance[i] <<"\n";
				}
			}
			
		}
	}

	cout << "Vertex  Visited  Distance  Path\n";
	for (int i = 0; i < graph->vertexes; i++)
	{
		cout << graph->vertexLabel[i]<< "	";
		cout << graph->visited[i]<< "	";
		cout << graph->distance[i]<< "	";
		if(graph->path[i] == -1)
			cout << "NONE\n";
		else
		cout << graph->vertexLabel[graph->path[i]]<< "\n";
	}
}

//almost for undigraph
void Prim(Graph *graph, int v)
{
	if(graph == NULL) return;
	if(v < 0 || v > graph->vertexes-1) return;

	for (int i = 0; i < graph->vertexes; i++)
	{
		graph->visited[i] = false;
		graph->distance[i] = INT_MAX;//can delete this line,as initialized in BuildGraph
		graph->path[i] = -1;
	}

	graph->distance[v] = 0;//the rest are all INT_MAX

	while(1)
	{
		int minDisInx = -1;
		int minDis = INT_MAX;
		for (int i = 0; i < graph->vertexes; i++)
		{
			if(!graph->visited[i])
			{
				if(graph->distance[i] < minDis)
				{
					minDis = graph->distance[i];
					minDisInx = i;
				}
			}
		}
		if(minDisInx == -1)//all visited
			break;

		graph->visited[minDisInx] = true;

		for (int i = 0; i < graph->vertexes; i++)
		{
			//unvisited and adjacent to current vertex
			//&& graph->AdjMat[minDisInx][i]!=0 is for undigraph
			if (!graph->visited[i] && graph->AdjMat[minDisInx][i]!=INT_MAX && graph->AdjMat[minDisInx][i]!=0)
			{
				if (graph->AdjMat[minDisInx][i] < graph->distance[i])
				{
					graph->distance[i] = graph->AdjMat[minDisInx][i];
					graph->path[i] = minDisInx;
					cout << graph->vertexLabel[i] << " Updated to " << graph->distance[i] <<"\n";
				}
			}

		}
	}

	cout << "Vertex  Visited  Distance  Path\n";
	for (int i = 0; i < graph->vertexes; i++)
	{
		cout << graph->vertexLabel[i]<< "	";
		cout << graph->visited[i]<< "	";
		cout << graph->distance[i]<< "	";
		if(graph->path[i] == -1)
			cout << "NONE\n";
		else
			cout << graph->vertexLabel[graph->path[i]]<< "\n";
	}
	
}
int main()
{
	Graph *graph = NULL;
	BuildGraph(graph,7);

	PrintGraph(graph);

	//for simple test, 0 indexed
	/*AddEdge(graph,0,1,1);
	AddEdge(graph,0,2,1);
	AddEdge(graph,1,3,1);*/

	//for TopologicalSort
	//0 indexed
	/*AddEdge(graph,0,1,1);
	AddEdge(graph,0,2,1);
	AddEdge(graph,0,3,1);
	AddEdge(graph,1,3,1);
	AddEdge(graph,1,4,1);
	AddEdge(graph,2,5,1);
	AddEdge(graph,3,2,1);
	AddEdge(graph,3,5,1);
	AddEdge(graph,3,6,1);
	AddEdge(graph,4,3,1);
	AddEdge(graph,4,6,1);
	AddEdge(graph,6,5,1);*/
	

	//for Dijkstra(shortest path),Prim(minimum spanning tree)
	//0 indexed
	AddEdge(graph,0,1,2);  
	AddEdge(graph,0,3,1);  
	AddEdge(graph,1,3,3);  
	AddEdge(graph,1,4,10);  
	AddEdge(graph,2,0,4);  
	AddEdge(graph,2,5,5);  
	AddEdge(graph,3,2,2);
	AddEdge(graph,3,4,2);
	AddEdge(graph,3,5,8);  
	AddEdge(graph,3,6,4);  
	AddEdge(graph,4,6,6);  
	AddEdge(graph,6,5,1);

	PrintGraph(graph);
	BeginDFS(graph);
	cout << "\n";
	BFS(graph);
	for (int i = 0; i < graph->vertexes; i++)
	{
		cout << "\n";
		Dijkstra(graph,i);
	}
	Prim(graph,0);
	
	TopologicalSort(graph);
	MakeEmpty(graph);
	return 0;
}




图(有向图,无向图)的邻接矩阵表示C++实现(遍历,拓扑排序,最短路径,最小生成树) Implement of digraph and undigraph using adjacency matrix,布布扣,bubuko.com

图(有向图,无向图)的邻接矩阵表示C++实现(遍历,拓扑排序,最短路径,最小生成树) Implement of digraph and undigraph using adjacency matrix

上一篇:陈正冲老师讲c语言之const关键字


下一篇:[MySQL] group by 聚合函数的原理和聚合限制原因SELECT list is not in GROUP BY clause and contains nonaggregated column