博客

如题 自用笔记 如有错误欢迎及时指正

所用数据结构定义见下文

https://blog.csdn.net/weixin_46127065/article/details/120631629

/* ===邻接矩阵求有向图所有顶点度数== */
//有向图邻接矩阵行非零元个数为出度 列非零元个数为入度 相加为度数
void GetDegree_Matrix(MatrixGraph G){
    int i, j;       //遍历控制器
    int v;      //控制结点数
    int rowcount, columncount, degree; //计数器
    for (v = 0; v < G->vexnum; v++){        //控制第i个结点
        //出度
        for (i = 0, rowcount = 0; i < G->vexnum;i++){       //求出度 在v行里对列遍历 求v行中非零元个数
            if(v!=i&&G->Edge[v][i]!=INF){       //排除对角线与0元素
                rowcount++;
            }
        }
        //入度
        for (j = 0, columncount = 0; j < G->vexnum; j++){                                       //求入度 在v列里对行遍历 求v列中非零元个数
            if(v!=j&&G->Edge[j][v]!=INF){       //排除对角线与0元素
                columncount++;
            }
        }
        G->OutDegree[v] = rowcount;
        G->InDegree[v] = columncount;
    }
    for (v = 0; v < G->vexnum; v++){
        printf("顶点%d的出度为: %d,入度为: %d,度数为: %d", 
            G->Vex[v], G->OutDegree[v], G->InDegree[v], G->InDegree[v] + G->OutDegree[v]);
        printf("\n");
    }
}

/* ===邻接表求有向图所有顶点度数== */
//有向图 邻接表出度为顶点表对应边表中元素个数 
//求入度要遍历全表 找到当前结点出现的次数
void GetDegree_AdjList(AdjListGraph G){
    int outdegree, indegree, degree; //计数器 保存度数
    int i,j;      //遍历控制
    for (i = 0; i < G->vexnum; i++){
        outdegree = 0;
        indegree = 0;       //初始化
         /* 求出度与入度 */
        //出度 求出边表对应顶点个数
        for (ArcNode *p = G->List[i].firstarc; p != NULL; p = p->nextarc){      //遍历
            outdegree++;        //出边表顶点个数就是出度
        }
        //入度  求顶点i在邻接表中出现次数
        for (j = 0; j < G->vexnum; j++){
            for (ArcNode *p = G->List[j].firstarc; p != NULL; p = p->nextarc){      //遍历全表
                if(i==p->adjvex /*i==p->adjvex而不是j==*/ ){       //结点i在表中出现
                    indegree++;
                }
            }
        }
        G->List[i].outdegree = outdegree;
        G->List[i].indegree = indegree;
    } 
    for (i = 0; i < G->vexnum; i++){
        printf("顶点%d的出度为: %d,入度为: %d,度数为: %d",
               G->List[i].data, G->List[i].outdegree, G->List[i].indegree, G->List[i].indegree + G->List[i].outdegree
               );
        printf("\n");
    }
}