c++ 邻接矩阵建图

C++邻接矩阵建图是一种基于矩阵的图存储方法，它是指用一个二维数组来表示一个图。其中，数组的行和列表示图中的各个顶点，数组元素表示相应顶点之间的边或权值。邻接矩阵在空间复杂度上是比较高的，但是在查找两个顶点之间是否存在边的时候比较方便。

具体实现方式如下：
1. 定义一个二维数组，数组元素类型为int，数组大小为N * N，其中N为图中顶点数。
2. 初始化二维数组元素值为0，表示各个顶点之间没有边。
3. 对于每条边(u, v)，在二维数组中将(u, v)和(v, u)对应位置的元素值设为1或者边的权值，表示存在一条边。
4. 如果是有向图，只需要在(u, v)对应位置的元素值设为1或者边的权值即可。

相关问题

邻接矩阵建图 acwing

邻接矩阵是一种常见的图表示方法，可以用于建立图的结构。在acwing平台上，您可以使用以下代码来建立邻接矩阵图：

#include <iostream>
#include <vector>

using namespace std;

const int N = 1005;  // 假设图中最多有1005个节点

vector<vector<int>> graph(N, vector<int>(N, 0));  // 初始化邻接矩阵

int main() {
    int n, m;
    cin >> n >> m;  // 输入节点数和边数

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;  // 输入边的起点和终点

        // 在邻接矩阵中标记该边
        graph[u][v] = 1;
        graph[v][u] = 1;
    }

    // 输出邻接矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

这段代码首先定义了一个大小为1005x1005的二维矩阵graph作为邻接矩阵。然后，根据输入的节点数和边数，利用循环读入每条边的起点和终点，并在邻接矩阵中标记该边。最后，通过两个嵌套的循环输出邻接矩阵。

请注意，这只是建立邻接矩阵图的基本示例，您可以根据实际需要进行修改和扩展。

无向图的邻接矩阵建图和度数输出

无向图的邻接矩阵建图和度数输出可以通过以下步骤实现：

1. 读取输入文件，获取节点个数和节点的邻接表示。
2. 创建一个大小为节点个数的二维数组，作为邻接矩阵。
3. 根据邻接表示，将邻接矩阵中对应的位置置为1，表示两个节点之间有边相连。
4. 遍历邻接矩阵的每一行，统计每个节点的度数，即该节点与其他节点相连的边的数量。
5. 输出每个节点的度数。

以下是一个示例代码：

def build_graph(input_file):
    with open(input_file, 'r') as file:
        lines = file.readlines()
        num_nodes = int(lines[0])
        adjacency_matrix = [[0] * num_nodes for _ in range(num_nodes)]
        for line in lines[1:]:
            if line.strip() == '':
                break
            nodes = list(map(int, line.strip().split()))
            node1 = nodes[0]
            for node2 in nodes[1:]:
                adjacency_matrix[node1][node2] = 1
                adjacency_matrix[node2][node1] = 1
    return adjacency_matrix

def calculate_degrees(adjacency_matrix):
    degrees = []
    for row in adjacency_matrix:
        degree = sum(row)
        degrees.append(degree)
    return degrees

input_file = 'input_7_1.txt'
output_file = 'output_7_1.txt'

adjacency_matrix = build_graph(input_file)
degrees = calculate_degrees(adjacency_matrix)

with open(output_file, 'w') as file:
    for degree in degrees:
        file.write(str(degree) + ' ')
    file.write('\n')

输出结果将会保存在`output_7_1.txt`文件中，每一行对应一个图的节点度数。