离散数学邻接矩阵乘法怎么算

邻接矩阵乘法可以用来计算两个图的组合，假设有两个图G1=(V1,E1)和G2=(V2,E2)，它们的邻接矩阵分别为A1和A2，则它们的邻接矩阵乘积C=A1*A2定义为：

C[i][j]=sum(A1[i][k]*A2[k][j])，其中k从1到n

其中，n是图中节点的个数，sum表示求和。

下面是邻接矩阵乘法的实现代码：

int[][] adjacencyMatrixMultiplication(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int sum = 0;
            for (int k = 0; k < n; k++) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
    return C;
}

其中，A和B是两个邻接矩阵，C是它们的乘积。这个算法的时间复杂度是O(n^3)，因为需要三重循环来计算。

相关问题

离散数学求邻接矩阵c语言·

### 回答1：
邻接矩阵是用来表示图的常用数据结构，它是一个二维的矩阵，其中每个元素表示两个顶点之间是否有边相连。如果顶点 $i$ 和顶点 $j$ 之间有边相连，则邻接矩阵中第 $i$ 行第 $j$ 列的元素为 $1$，否则为 $0$。

下面是求无向图邻接矩阵的 C 语言代码：

#include <stdio.h>

#define MAXV 100  // 最大顶点数

int matrix[MAXV][MAXV];  // 邻接矩阵
int V, E;  // 顶点数和边数

int main() {
    int u, v;
    scanf("%d %d", &V, &E);  // 输入顶点数和边数
    for (int i = 0; i < E; i++) {
        scanf("%d %d", &u, &v);  // 输入边
        matrix[u][v] = matrix[v][u] = 1;  // 在邻接矩阵中标记边
    }
    // 输出邻接矩阵
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

这段代码首先定义了一个 $100 \times 100$ 的二维数组 `matrix`，表示邻接矩阵。然后从标准输入中读入顶点数 `V` 和边数 `E`，并利用循环读入每一条边，将邻接矩阵中对应的元素标记为 $1$。最后再利用循环输出邻接矩阵即可。

### 回答2：
离散数学是数学的一个分支领域，主要研究离散结构和离散对象的性质和关系。邻接矩阵是描述无向图或有向图的常用方式之一，可以通过矩阵的形式表示图中各个顶点之间的连接情况。

在C语言中，可以使用二维数组来表示邻接矩阵。假设有一个图的顶点数为n，那么可以定义一个n * n大小的二维数组来表示邻接矩阵。

首先，需要定义一个函数来创建邻接矩阵，函数的参数为图的顶点数n和一个存放边信息的数组edges[]。edges数组用来表示每条边连接的两个顶点。

void createAdjMatrix(int n, int edges[][2]) {
    int adjMatrix[n][n];  // 定义n * n大小的二维数组用来存储邻接矩阵

    // 初始化邻接矩阵
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            adjMatrix[i][j] = 0;  // 初始化所有元素为0
        }
    }

    // 根据edges数组中的信息来更新邻接矩阵
    for(int i = 0; i < n; i++) {
        int src = edges[i][0];   // 起始顶点
        int dest = edges[i][1];  // 终止顶点
        adjMatrix[src][dest] = 1;  // 表示src和dest之间有边

        // 如果是无向图，还需要添加下面这行代码
        // adjMatrix[dest][src] = 1;
    }

    // 输出邻接矩阵
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

以上的代码将会根据传入的顶点数和边信息创建一个邻接矩阵，并输出该矩阵。

需要注意的是，上述代码只给出了无向图的情况，如果是有向图，则不需要添加注释掉的那句代码。

使用该函数时，可以在主函数中定义一个边信息数组，并传入该函数中进行调用：

int main() {
    int n = 5;  // 顶点数
    int edges[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}};  // 边信息数组

    createAdjMatrix(n, edges);  // 创建并输出邻接矩阵

    return 0;
}

以上就是用C语言求解邻接矩阵的一个简单示例。

### 回答3：
离散数学是研究离散对象和离散关系的数学分支，而邻接矩阵是用于表示图的一种常见方式。C语言是一种广泛应用于计算机编程的编程语言，因此可以利用C语言来实现邻接矩阵。

邻接矩阵是一个二维数组，用于表示图中各个顶点之间的连接关系。具体实现邻接矩阵的方式可以通过使用C语言的二维数组来表示，其中矩阵的行和列分别对应图中的各个顶点。

以下是一个用C语言实现邻接矩阵的简单示例：

#include <stdio.h>

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 定义邻接矩阵

void addEdge(int u, int v) {
    adjMatrix[u][v] = 1;  // 将顶点u与顶点v的连接关系设为1
    adjMatrix[v][u] = 1;  // 因为是无向图，所以顶点v与顶点u的连接关系也设为1
}

int main() {
    int n, m; // n表示顶点数，m表示边数
    scanf("%d %d", &n, &m); // 输入顶点数和边数

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v); // 输入边的两个顶点u和v，表示u与v之间存在一条边
        addEdge(u, v); // 在邻接矩阵中添加边的连接关系
    }

    // 打印邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

以上的代码实现了一个简单的邻接矩阵，通过输入顶点数和边数，以及各条边的起始顶点和结束顶点，即可得到对应的邻接矩阵。利用C语言的二维数组特性，可以方便地表示和操作邻接矩阵，并且适用于较小规模的图结构。当图规模较大时，可能需要考虑其他数据结构和算法的优化。

离散数学有向图求邻接矩阵c语言

### 回答1：
假设有向图的顶点数为n，邻接矩阵为A[n][n]，则可以按照以下步骤求出邻接矩阵：

1. 定义一个二维数组A[n][n]，并将所有元素初始化为0。

2. 遍历有向图的每一条边(u, v)，将A[u][v]的值设置为1，表示从顶点u到顶点v有一条有向边。

3. 输出邻接矩阵A。

以下是示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

int main()
{
    int n; // 顶点数
    int A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵

    // 输入顶点数和边数
    printf("请输入有向图的顶点数：");
    scanf("%d", &n);

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            A[i][j] = 0;
        }
    }

    // 输入有向图的边
    int m;
    printf("请输入有向图的边数：");
    scanf("%d", &m);
    printf("请输入每条边的起点和终点，用空格隔开：\n");
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        A[u][v] = 1;
    }

    // 输出邻接矩阵
    printf("邻接矩阵：\n");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }

    return 0;
}

注意：以上代码中的顶点编号从0开始。如果需要从1开始，只需要在输入和输出时将顶点编号加1即可。

### 回答2：
离散数学中的有向图可以通过邻接矩阵来表示，邻接矩阵是一个二维数组，其中的元素表示有向图中的边的连接关系。

在C语言中，我们可以使用二维数组来表示邻接矩阵。以下是一个示例代码：

#include <stdio.h>

#define MAX_VERTICES 100

int main()
{
    int numVertices;
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

    // 输入顶点数量
    printf("请输入顶点的数量：");
    scanf("%d", &numVertices);

    // 输入有向边的连接关系，并构建邻接矩阵
    printf("请输入有向边的连接关系：\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            scanf("%d", &adjacencyMatrix[i][j]);
        }
    }

    // 输出邻接矩阵
    printf("邻接矩阵为：\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            printf("%d ", adjacencyMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

以上代码首先定义了一个二维数组`adjacencyMatrix`用于存储邻接矩阵，以及一个变量`numVertices`用于记录顶点的数量。然后通过用户输入来构建邻接矩阵，最后将邻接矩阵输出到控制台。

注意，上述代码中的二维数组`adjacencyMatrix`的大小是固定的，可以根据实际需求进行调整。另外，这里假设顶点的编号从0开始递增，可以根据实际需求进行修改。

### 回答3：
离散数学中的有向图是由一组顶点和一组有向边构成的图结构。邻接矩阵是一种常用的表示有向图的方法，用一个矩阵来表示图中顶点之间的连接关系。

在C语言中，我们可以利用二维数组来表示邻接矩阵。首先，我们需要确定图中的顶点个数n，然后创建一个n × n的二维数组来表示邻接矩阵。数组的元素可以是0或1，分别代表顶点之间不存在或存在有向边。

下面是求解有向图邻接矩阵的C语言代码示例：

#include <stdio.h>

#define MAX_VERTICES 100

// 定义全局变量
int adjacency_matrix[MAX_VERTICES][MAX_VERTICES];

// 构造邻接矩阵
void constructAdjacencyMatrix(int vertices, int edges, int edgeList[][2]) {
    // 初始化邻接矩阵为0
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjacency_matrix[i][j] = 0;
        }
    }

    // 根据边的信息更新邻接矩阵
    for (int i = 0; i < edges; i++) {
        int source = edgeList[i][0];
        int target = edgeList[i][1];
        adjacency_matrix[source][target] = 1;
    }
}

// 打印邻接矩阵
void printAdjacencyMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", adjacency_matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int vertices, edges;
    int edgeList[MAX_VERTICES][2];

    printf("请输入图的顶点数和边数：\n");
    scanf("%d %d", &vertices, &edges);

    printf("请输入每条边的起点和终点：\n");
    for (int i = 0; i < edges; i++) {
        scanf("%d %d", &edgeList[i][0], &edgeList[i][1]);
    }

    constructAdjacencyMatrix(vertices, edges, edgeList);
    printf("邻接矩阵为：\n");
    printAdjacencyMatrix(vertices);

    return 0;
}

以上是一个简单的C语言程序，可以读取用户输入的有向图信息（顶点数、边数、边的起点和终点），然后构造出对应的邻接矩阵并打印出来。