已知图G用邻接矩阵存储,设计算法:分别求解顶点vi的入度、出度和度。
时间: 2024-02-16 13:02:36 浏览: 24
分别求解顶点vi的入度、出度和度的算法如下:
1. 入度:对于邻接矩阵中的第i行,统计其中为1的元素个数即为顶点vi的入度。
2. 出度:对于邻接矩阵中的第i列,统计其中为1的元素个数即为顶点vi的出度。
3. 度:将顶点vi的入度和出度相加即为顶点vi的度。
具体实现可以参考以下伪代码:
```
// 邻接矩阵表示的图G,顶点vi的编号为i
int in_degree = 0; // 入度
int out_degree = 0; // 出度
// 计算入度
for(int j=0; j<n; j++){
if(G[j][i] == 1){
in_degree++;
}
}
// 计算出度
for(int j=0; j<n; j++){
if(G[i][j] == 1){
out_degree++;
}
}
// 计算度
int degree = in_degree + out_degree;
```
其中,n为图G的顶点数,G[i][j]表示图G中从顶点i到顶点j是否有边相连,值为1表示有边,值为0表示无边。
相关问题
已知图G用邻接矩阵存储,用C语言设计算法:分别求解顶点vi的入度、出度和度。
好的,以下是C语言的算法实现:
假设邻接矩阵为A,顶点vi的下标为i,则:
1. vi的入度:
```c
int inDegree(int A[][MAX_SIZE], int n, int i) {
int degree = 0;
for (int j = 0; j < n; j++) {
if (A[j][i] == 1) {
degree++;
}
}
return degree;
}
```
2. vi的出度:
```c
int outDegree(int A[][MAX_SIZE], int n, int i) {
int degree = 0;
for (int j = 0; j < n; j++) {
if (A[i][j] == 1) {
degree++;
}
}
return degree;
}
```
3. vi的度:
```c
int degree(int A[][MAX_SIZE], int n, int i) {
int degree = 0;
for (int j = 0; j < n; j++) {
if (A[i][j] == 1 || A[j][i] == 1) {
degree++;
}
}
return degree;
}
```
其中,n为图G的顶点数,MAX_SIZE为邻接矩阵的最大尺寸。这些函数均返回一个整数,表示顶点vi的入度、出度和度。
用C语言写出:已知有向图采用邻接矩阵作为存储结构,设计算法求该图中每个顶点的出度和入度
以下是用C语言实现求有向图邻接矩阵中每个顶点的出度和入度的算法:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 定义邻接矩阵类型
typedef struct {
int vexs[MAX_VERTEX_NUM]; // 存储顶点信息
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的信息
int vex_num, arc_num; // 顶点数、边数
} MGraph;
// 初始化邻接矩阵
void InitMGraph(MGraph *G) {
int i, j;
printf("请输入顶点数和边数:");
scanf("%d%d", &(G->vex_num), &(G->arc_num));
printf("请输入顶点信息:");
for (i = 0; i < G->vex_num; ++i) {
scanf("%d", &(G->vexs[i]));
}
for (i = 0; i < G->vex_num; ++i) {
for (j = 0; j < G->vex_num; ++j) {
G->arcs[i][j] = 0; // 初始化为0,即无连接边
}
}
printf("请输入边的信息:\n");
for (i = 0; i < G->arc_num; ++i) {
int v1, v2;
printf("请输入第%d条边的两个顶点序号:", i+1);
scanf("%d%d", &v1, &v2);
G->arcs[v1][v2] = 1; // 有连接边的位置置为1
}
}
// 计算每个顶点的出度和入度
void CalInOutDegree(MGraph G, int *in_degree, int *out_degree) {
int i, j;
for (i = 0; i < G.vex_num; ++i) {
int in = 0, out = 0;
for (j = 0; j < G.vex_num; ++j) {
if (G.arcs[i][j] == 1) { // 有连接边,则出度+1
out++;
}
if (G.arcs[j][i] == 1) { // 有连接边,则入度+1
in++;
}
}
in_degree[i] = in;
out_degree[i] = out;
}
}
// 输出每个顶点的出度和入度
void PrintInOutDegree(MGraph G, int *in_degree, int *out_degree) {
int i;
printf("每个顶点的出度和入度如下:\n");
for (i = 0; i < G.vex_num; ++i) {
printf("顶点%d:出度%d,入度%d\n", G.vexs[i], out_degree[i], in_degree[i]);
}
}
int main() {
MGraph G;
int in_degree[MAX_VERTEX_NUM], out_degree[MAX_VERTEX_NUM];
InitMGraph(&G);
CalInOutDegree(G, in_degree, out_degree);
PrintInOutDegree(G, in_degree, out_degree);
return 0;
}
```
注意:该算法实现的是有向图邻接矩阵的存储结构,且默认顶点信息为整数,因此输入信息时顶点信息也需为整数。