最小生成树

Prim算法

int AMGraph::sum(string v)
{int start, totalW, cnt, minW, u, vv, i, j;start = LocateVex(v); // 获取起始顶点编号memset(visited, false, sizeof(visited)); // 初始化访问状态visited[start] = true;totalW = 0; // 最小生成树的总权重cnt = 1; // 当前生成树包含的顶点数while (cnt < vexnum){minW = INT_MAX; // 当前最小边权值u = -1; // 最小边的两个端点vv = -1;for (i = 0; i < vexnum; i++){// 遍历已加入生成树的顶点if (visited[i]){for (j = 0; j < vexnum; j++){if (!visited[j] && arcs[i][j] < minW){minW = arcs[i][j];u = i; // 起始点vv = j; // 终点}}}}// 无法继续扩展生成树if (vv == -1){break;}visited[vv] = true; // 将v加入生成树totalW += minW; // 累加权值cnt++; // 增加生成树的顶点计数}return totalW;
}

Kruskal算法

void AMGraph::kruskal()
{int i, j;for (i = 0; i < arcnum; i++) // 将所有的边按照从小到大排序{for (j = i + 1; j < arcnum; j++){if ((edges[i].w > edges[j].w) || (edges[i].w == edges[j].w && edges[i].u > edges[j].u)){Edge temp = edges[i];edges[i] = edges[j];edges[j] = temp;}}}for (i = 0; i < vexnum; i++) // 初始化{Vexset[i] = i;}for (i = 0; i < arcnum; i++) // 遍历所有的边{int v1 = edges[i].u; // 边的始点的下标int v2 = edges[i].v; // 边的终点的下标int vs1 = Vexset[v1]; // 连通分量int vs2 = Vexset[v2];// 如果两个节点不在同一棵树中，说明这条边可以添加到最小生成树中if (vs1 != vs2){if (edges[i].u < edges[i].v){cout << vexs[edges[i].u] << " " << vexs[edges[i].v] << " " << edges[i].w << endl;}else{cout << vexs[edges[i].v] << " " << vexs[edges[i].u] << " " << edges[i].w << endl;}// 合并两个分量for (j = 0; j < arcnum; j++){if (Vexset[j] == vs2){Vexset[j] = vs1;}}}}
}

两种算法比较

最短路径

Dijkstra算法

#include <iostream>
#include <climits>
#include <algorithm>
#include <string>
using namespace std;const int MaxLen = 100; // 设定图最多包含顶点class Map
{
private:string vexsU[MaxLen]; // 顶点表bool visited[MaxLen]; // 访问标志数组int Maxtrix[MaxLen][MaxLen]; // 图的邻接矩阵int Vexnum; // 图的顶点个数int dist[MaxLen]; // 存储源点到每个节点的最短距离int path[MaxLen]; // 用于存储每个顶点的前驱节点
public:void SetMatrix(int vnum, int mx[MaxLen][MaxLen], string vexs[MaxLen]);void Dijkstra(int n, string s);int LocateVex(string u);void PrintPath(int start, int end); // 打印从 start 到 end 的路径
};// 设置邻接矩阵和顶点表
void Map::SetMatrix(int vnum, int mx[MaxLen][MaxLen], string vexs[MaxLen])
{Vexnum = vnum;for (int i = 0; i < vnum; i++){vexsU[i] = vexs[i]; // 初始化顶点表for (int j = 0; j < vnum; j++){Maxtrix[i][j] = mx[i][j];}}
}// 打印路径
void Map::PrintPath(int start, int end)
{if (start == end){cout << vexsU[start];return;}if (path[end] == -1){cout << "无路径";return;}PrintPath(start, path[end]);cout << " " << vexsU[end];
}// 迪杰斯特拉算法
void Map::Dijkstra(int n, string s)
{// 初始化距离数组、访问数组和路径数组for (int i = 0; i < n; i++){dist[i] = INT_MAX;visited[i] = false;path[i] = -1; // -1 表示无前驱}int start = LocateVex(s);dist[start] = 0; // 起点到自身的距离为 0for (int i = 0; i < n; i++){int u = -1;// 从未访问的节点中找到距离最近的节点 ufor (int j = 0; j < n; j++){if (!visited[j] && (u == -1 || dist[j] < dist[u])){u = j;}}if (u == -1 || dist[u] == INT_MAX){break; // 剩余节点不可达}visited[u] = true; // 标记该节点为已访问// 更新所有与 u 相邻的节点的距离for (int v = 0; v < n; v++){if (Maxtrix[u][v] != INT_MAX && dist[u] + Maxtrix[u][v] < dist[v]){dist[v] = dist[u] + Maxtrix[u][v];path[v] = u; // 更新前驱节点}}}// 输出最短路径for (int i = 1; i < n; i++){cout << vexsU[start] << "-" << vexsU[i] << "-";if (dist[i] == INT_MAX){cout << "-1" << endl; // 不可达}else{cout << dist[i] << "----[";PrintPath(start, i);cout << " ]" << endl;}}
}// 定位顶点索引
int Map::LocateVex(string u)
{for (int i = 0; i < Vexnum; i++){if (u == vexsU[i]){return i;}}return -1;
}int main()
{int t, n, i, j, Matrix[MaxLen][MaxLen];string vexs[MaxLen], start;cin >> t;while (t--){cin >> n; // 顶点数for (i = 0; i < n; i++){cin >> vexs[i]; // 输入每个顶点名称}for (i = 0; i < n; i++){for (j = 0; j < n; j++){cin >> Matrix[i][j];if (Matrix[i][j] == 0 && i != j){Matrix[i][j] = INT_MAX; // 没有边的情况}}}cin >> start;Map m;m.SetMatrix(n, Matrix, vexs);m.Dijkstra(n, start);}return 0;
}

Foyed算法

拓扑排序

// 求各顶点的入度
void Map::FindInDegree()
{int i, j;// 初始化for (i = 0; i < MaxLen; i++){indegree[i] = 0;}for (i = 0; i < Vexnum; i++){for (j = 0; j < Vexnum; j++){if (Maxtrix[i][j] == 1){indegree[j]++;}}}
}// 输出拓扑排序的结果
void Map::topo()
{int i, k, m, current;queue<int> q;FindInDegree(); // 求各顶点的入度for (i = 0; i < Vexnum; i++){// 入度为0者进栈if (indegree[i] == 0){q.push(i);}}m = 0; // 对输出顶点计数，初始为0while (!q.empty()){current = q.front();q.pop();tp[m] = current;m++;for (k = 0; k < Vexnum; k++){if (Maxtrix[current][k] == 1){indegree[k]--;if (indegree[k] == 0){q.push(k);}}}}if (m == Vexnum){for (i = 0; i < m; i++){cout << tp[i] << " ";}}cout << endl;
}

关键路径