MENU

求顶点的出入度

• November 12, 2020 •

求邻接矩阵存储结构的有向图G中各顶点的入度


1. 什么是出度与入度?

在有向图中,箭头是具有方向的,从一个顶点指向另一个顶点,这样一来,每个顶点被指向的箭头个数,就是它的入度。从这个顶点指出去的箭头个数,就是它的出度

2. 怎样计算一个顶点的入度与出度

邻接矩阵的行号即代表箭头的出发结点,列号是箭头的指向结点,所以矩阵中同一行为1的表示有从第i个结点指向第j个结点这样一条边

而在同列为1就代表第j个结点被第i个结点指向,因此要求顶点的出度与入度,只需要判断同列为1的个数,同行为1的个数


一个有向图如下所示:


该图邻接矩阵如下:


核心代码块:

计算入度:

计算出度:


算法思想:

按列遍历矩阵,累计每列1的个数,就是第j个顶点的入度

按层遍历矩阵,累计每行1的个数,就是第i个顶点的出度(i,j均从0开始)

辅助测试文件(点击下载)

测试代码:

《Domin.h》

#pragma once
#include"AdjMGraph.h"
#include"ListVertex.h"
//计算有向各点的入度
void penetration(AdjMGraph *map) {
    int numOfVertex = listVertexLength(map->VerTices);
    int count = 0;   //记录入度个数
    for (int j = 0; j < numOfVertex; j++)  //按列遍历
    {
        for (int i = 0; i < numOfVertex; i++)
        {
            if (map->edge[i][j] == 1)
                count++;
        }
        DataType vertex = getVertex(map->VerTices, j);
        printf("顶点 %c :入度为 %d\n", vertex, count);
        count = 0;  //每列遍历完后,个数置0
    }
    printf("\n\n");
}
/*出度*/
void outDegree(AdjMGraph *map) {
    int numOfVertex = listVertexLength(map->VerTices);
    int count = 0;   //记录出度个数
    for (int i = 0; i < numOfVertex; i++)   //按层遍历
    {
        for (int j = 0; j < numOfVertex; j++)
        {
            if (map->edge[i][j] == 1)
                count++;
        }
        DataType vertex = getVertex(map->VerTices, i);
        printf("顶点 %c :出度为 %d\n", vertex, count);
        count = 0;    //每层遍历完后,个数置0
    }
    printf("\n\n");
}

测试函数:

#include"Domin.h"
int main()
{
    AdjMGraph g1;
    DataType a[] = { 'a','b','c','d','e','f','g' };  //图的顶点集合
    RowColWeight row[] = { {0,1},{0,6},{1,6}, {2,1}, {3,2}, {3,5}, {4,3},{5,0},{5,4},{6,2},{6,3},{6,5} };//图中的有向边
    int p[9][9], q[9][9];
    int n = 7, e = 11; //顶点和边的个数
    int i, j, k;
    creatGraph(&g1, a, n, row, e);   //创建一个图
    penetration(&g1);
    outDegree(&g1);
    return 0;
}

运行结果:




代码编译器:Visual Studio 2017
ok

Archives QR Code Tip
QR Code for this page
Tipping QR Code