本文主要是介绍图（有向图，无向图）的邻接矩阵表示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 vertexesint vertexes;int edges;int **AdjMat;bool *visited;//only for DFS,BFS,Dijkstraint *distance; //only for Dijkstraint *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));elsefor (int j = 0; j < graph->vertexes; j++){if(i == j)graph->AdjMat[i][j] = 0;elsegraph->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 allowedif(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 (gra这篇关于图（有向图，无向图）的邻接矩阵表示C++实现(遍历，拓扑排序，最短路径，最小生成树) Implement of digraph and undigraph using adjacency matrix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
