C++设计一个实现创建无向奒的程序；邻接矩阵作为奓储结构。

Question

C++设计一个实现创建无向奒的程序；邻接矩阵作为存储结构。算法思想：
(1) 定义图的顺序存储结构；
(2) 创建无向奒，采用邻接矩阵表示（奊用CreateUDN函数实现），具体实现如下：
    输入图的顶奍数和楱数；
    依次输入顶奍的信息奓入顶奍表中；
    初始化邻接矩阵，使每个权值初始化为极大值；

    构造邻接矩阵；（需奊用LocateVex函数获取顶奍在顶奍表中的下标）

(3) 输出图的邻接矩阵（奊用PrintUDN函数实现）。

注意：顶奍数据奘为1个数字或1个字符。
输入说明：
    第一行输入图的顶奍数和楱数；
    第二行依次输入每个顶奍的数据；
    其余各行的每行输入一条楱的信息。
输出说明：
    输出图的邻接矩阵，其中每个值用6个宽度输出且右奌齐，最大值输出#。
输入样例：
4 5
A B C D
A B 500
A C 200
A D 150
B C 400
C D 600

输出样例：
     
     #   500   200   150
   500     #   400     #
   200   400     #   600
   150     #   600     #

                      

Answer 1

引自免费微信小程序：皆我百晓生

为了帮助您理解如何实现这个无向图，我将逐步解释并提供相关的C++代码段。首先，我们需要定义图的顺序存储结构，然后实现相应的函数。以下是整个程序的实现：

#include <iostream>
#include <vector>
#include <string>

// 图的顶点类
class Vertex {
public:
    char data;
    int index;

    Vertex(char d, int i) : data(d), index(i) {}
};

// 邻接矩阵表示的无向图类
class UndirectedGraph {
private:
    int numVertices; // 顶点数量
    std::vector<Vertex> vertices; // 顶点列表
    std::vector<std::vector<int>> adjacencyMatrix; // 邻接矩阵

public:
    UndirectedGraph(int v) : numVertices(v), adjacencyMatrix(v, std::vector<int>(v, INT_MAX)) {}

    // 添加边到图中
    void addEdge(int from, int to, int weight) {
        adjacencyMatrix[from][to] = weight;
        adjacencyMatrix[to][from] = weight;
    }

    // 获取顶点在顶点列表中的索引
    int locateVertex(char vertexData) {
        for (int i = 0; i < numVertices; ++i) {
            if (vertices[i].data == vertexData) {
                return vertices[i].index;
            }
        }
        throw std::runtime_error("Vertex not found");
    }

    // 打印邻接矩阵
    void printAdjacencyMatrix() {
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                if (adjacencyMatrix[i][j] == INT_MAX) {
                    std::cout << "# ";
                } else {
                    std::cout << std::setw(6) << adjacencyMatrix[i][j] << " ";
                }
            }
            std::cout << "\n";
        }
    }
};

int main() {
    int numVertices, numEdges;
    std::cin >> numVertices >> numEdges;

    UndirectedGraph graph(numVertices);

    // 输入顶点信息
    for (int i = 0; i < numVertices; ++i) {
        char vertexData;
        std::cin >> vertexData;
        graph.vertices.push_back(Vertex(vertexData, i));
    }

    // 输入边的信息
    for (int i = 0; i < numEdges; ++i) {
        char startVertex, endVertex;
        int weight;
        std::cin >> startVertex >> endVertex >> weight;
        int startIndex = graph.locateVertex(startVertex);
        int endIndex = graph.locateVertex(endVertex);
        graph.addEdge(startIndex, endIndex, weight);
    }

    // 输出邻接矩阵
    graph.printAdjacencyMatrix();

    return 0;
}

这段代码首先定义了一个Vertex类用于存储顶点的数据和索引，以及一个UndirectedGraph类，它包含邻接矩阵和相关操作。main函数负责接收用户输入，并根据输入构建图的邻接矩阵。最后，通过调用printAdjacencyMatrix方法输出邻接矩阵。

请注意，在运行此代码之前，请确保已经安装了C++编译器（如g++或clang++）。可以将代码复制到一个名为undirected_graph.cpp的文件中，然后使用命令行工具编译并运行：

g++ -o undirected_graph undirected_graph.cpp
./undirected_graph

此时，按照提供的输入样例输入数据，程序会输出对应的邻接矩阵。