带权有向图邻接矩阵怎么输入
时间: 2023-09-03 07:11:00 浏览: 73
带权有向图的邻接矩阵可以用一个二维数组来表示。如果有 $n$ 个节点,那么这个数组的大小就是 $n\times n$。对于每个节点 $i$ 和 $j$,如果它们之间有一条边,那么数组中第 $i$ 行第 $j$ 列的元素就是这条边的权值;否则这个元素就是一个特定的无穷大值,表示它们之间没有边。
以下是一个简单的示例:
```
4 5
1 2 2
1 3 3
2 3 1
3 4 4
4 1 5
```
这个示例表示一个有 $4$ 个节点、$5$ 条边的带权有向图。第一行是节点数和边数,后面 $5$ 行分别是每条边的起点、终点和权值。我们可以用一个邻接矩阵来表示它:
```
inf 2 3 inf
inf inf 1 inf
inf inf inf 4
5 inf inf inf
```
其中,inf 表示无穷大。第 $i$ 行第 $j$ 列的元素表示节点 $i$ 到节点 $j$ 的边权值,如果没有边,则为无穷大。
相关问题
c语言带权有向图邻接矩阵
以下是C语言中带权有向图邻接矩阵的示例代码:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
char vexs[MAX_VERTEX_NUM]; // 顶点数组
int vexnum; // 顶点数
int arcnum; // 弧数
MGraph;
// 输出邻接矩阵
void OutMGraph(MGraph G) {
int i, j, count = 0;
printf("\t");
for (i = 0; i < G.vexnum; i++)
printf("\t%c", G.vexs[i]);
printf("\n");
for (i = 0; i < G.vexnum; i++) {
printf("\t%c", G.vexs[i]);
for (j = 0; j < G.vexnum; j++) {
printf("\t%d", G.arcs[i][j]);
count++;
if (count % G.vexnum == 0)
printf("\n");
}
}
}
int main() {
MGraph G;
int i, j;
// 初始化顶点数和弧数
G.vexnum = 4;
G.arcnum = 6;
// 初始化顶点数组
G.vexs[0] = 'A';
G.vexs[1] = 'B';
G.vexs[2] = 'C';
G.vexs[3] = 'D';
// 初始化邻接矩阵
for (i = 0; i < G.vexnum; i++) {
for (j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
// 添加边的权值
G.arcs[0][1] = 1;
G.arcs[0][2] = 2;
G.arcs[1][2] = 3;
G.arcs[1][3] = 4;
G.arcs[2][3] = 5;
G.arcs[3][0] = 6;
// 输出邻接矩阵
OutMGraph(G);
return 0;
}
```
用邻接矩阵存储带权有向图
邻接矩阵是一种常用的图的存储方法。对于带权有向图,我们可以使用一个二维数组来表示邻接矩阵。假设有 $n$ 个顶点,我们可以定义一个 $n \times n$ 的数组 $a$,其中 $a_{ij}$ 表示从顶点 $i$ 到顶点 $j$ 的边的权值。如果 $i$ 和 $j$ 不相邻,则 $a_{ij}$ 的值为无穷大或者一个特殊的标记,表示它们之间没有边。
对于有向图而言,如果从顶点 $i$ 到顶点 $j$ 有一条边,则 $a_{ij}$ 不为无穷大或特殊标记,否则 $a_{ij}$ 为无穷大或特殊标记。
邻接矩阵存储带权有向图的优点是方便查找任意两个顶点之间的边的权值,缺点是如果图比较稀疏,则会浪费较多的空间。