如题 自用笔记 如有错误欢迎及时指正
所用数据结构定义见下文
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");
}
}
版权声明:本文为weixin_46127065原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。