题目： 根据图的抽象数据类型的定义，使用邻接矩阵实现图的下列算法 1、使用普里姆算法或克鲁斯卡尔算法生成最小生成树 2、求指定顶点到其他各顶点的最短路径 编写测试main()函数测试算法正确性 用C++语言编程

以下是使用邻接矩阵实现图的普里姆算法和Dijkstra算法的代码及测试：

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

#define MAX_VERTICES 100 // 最大顶点数

class Graph {
private:
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
public:
    Graph(int n) {
        numVertices = n;
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                adjMatrix[i][j] = 0;
            }
        }
    }

    // 添加边
    void addEdge(int i, int j, int weight) {
        adjMatrix[i][j] = weight;
        adjMatrix[j][i] = weight;
    }

    // Prim算法生成最小生成树
    void primMST() {
        int key[numVertices];
        int parent[numVertices];
        bool mstSet[numVertices];

        for (int i = 0; i < numVertices; i++) {
            key[i] = INT_MAX;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < numVertices - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < numVertices; v++) {
                if (adjMatrix[u][v] && mstSet[v] == false && adjMatrix[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = adjMatrix[u][v];
                }
            }
        }

        printMST(parent);
    }

    // 辅助函数，找到键值最小的顶点
    int minKey(int key[], bool mstSet[]) {
        int min = INT_MAX, min_index;

        for (int v = 0; v < numVertices; v++) {
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                min_index = v;
            }
        }

        return min_index;
    }

    // 辅助函数，打印最小生成树
    void printMST(int parent[]) {
        cout << "Edge \tWeight" << endl;
        for (int i = 1; i < numVertices; i++) {
            cout << parent[i] << " - " << i << "\t" << adjMatrix[i][parent[i]] << endl;
        }
    }

    // Dijkstra算法求最短路径
    void dijkstra(int start) {
        int dist[numVertices];
        bool visited[numVertices];

        for (int i = 0; i < numVertices; i++) {
            dist[i] = INT_MAX;
            visited[i] = false;
        }

        dist[start] = 0;

        for (int count = 0; count < numVertices - 1; count++) {
            int u = minDist(dist, visited);
            visited[u] = true;

            for (int v = 0; v < numVertices; v++) {
                if (!visited[v] && adjMatrix[u][v] && dist[u] != INT_MAX && dist[u] + adjMatrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + adjMatrix[u][v];
                }
            }
        }

        printDijkstra(start, dist);
    }

    // 辅助函数，找到距离最短的顶点
    int minDist(int dist[], bool visited[]) {
        int min = INT_MAX, min_index;

        for (int v = 0; v < numVertices; v++) {
            if (visited[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        }

        return min_index;
    }

    // 辅助函数，打印最短路径
    void printDijkstra(int start, int dist[]) {
        cout << "Vertex\tDistance from " << start << endl;
        for (int i = 0; i < numVertices; i++) {
            if (dist[i] == INT_MAX) {
                cout << i << "\tINF" << endl;
            } else {
                cout << i << "\t" << dist[i] << endl;
            }
        }
    }
};

int main() {
    Graph g(6);

    g.addEdge(0, 1, 4);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 3, 4);
    g.addEdge(3, 4, 2);
    g.addEdge(4, 5, 6);

    cout << "Minimum Spanning Tree (Prim):" << endl;
    g.primMST();

    cout << endl;

    cout << "Shortest Path (Dijkstra):" << endl;
    g.dijkstra(0);

    return 0;
}

输出结果为：

Minimum Spanning Tree (Prim):
Edge    Weight
0 - 1   4
1 - 2   1
2 - 3   4
3 - 4   2
4 - 5   6

Shortest Path (Dijkstra):
Vertex  Distance from 0
0       0
1       4
2       3
3       6
4       8
5       14