有向图的邻接矩阵
时间: 2023-09-03 16:10:57 浏览: 57
有向图的邻接矩阵是一个方阵,其中第 i 行第 j 列的元素表示从顶点 i 到顶点 j 是否存在一条有向边。如果存在,则该元素的值为1,否则为0。
例如,对于下面这个有向图:
```
1 -> 2
/ \ |
v v v
3 <- 4
```
它的邻接矩阵为:
```
| 1 2 3 4
---|--------
1 | 0 1 0 0
2 | 0 0 0 0
3 | 1 0 0 1
4 | 0 1 1 0
```
其中,第一行表示从顶点1出发的边,第一列表示指向顶点1的边。例如,第一行第二列的元素为1,表示从顶点1到顶点2存在一条有向边。第三行表示从顶点3出发的边,第四列表示指向顶点4的边。
相关问题
c语言定义有向图邻接矩阵
C语言定义有向图邻接矩阵可以通过二维数组来实现。邻接矩阵是一个n*n的矩阵,其中n是有向图中顶点的数量。如果有向图中存在一条从顶点i到顶点j的边,则邻接矩阵中第i行第j列的元素为1,否则为0。在C语言中,可以使用二维数组来表示邻接矩阵,例如:
```
int graph[MAX][MAX]; // MAX为顶点的最大数量
// 初始化邻接矩阵
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
graph[i][j] = 0;
}
}
// 添加边
graph[0][1] = 1; // 添加从顶点0到顶点1的边
graph[1][2] = 1; // 添加从顶点1到顶点2的边
// ...
```
这样,我们就可以使用邻接矩阵来表示有向图,并且可以方便地添加和删除边。
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;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)