首页 > 试题广场 >

请设计算法，求出有向图中每个顶点的入度

[问答题]

有 N个顶点的有向图邻接表定义如下：

Struct Enode{                      //定义邻接表的结点
    Vertex num;                    //该弧所指向的顶点的位置
    Enode *eptr;                    //指向下一条弧的指针
}
Struct Vnode{                      //定义邻接表的头结点
    Datatype vinfo;                 //顶点信息
    Enode *firste;                  //指向第一条依附该顶点的弧的指针
}
Vnode adjlist[N];                   //邻接表N个头结点

请设计算法，求出有向图中每个顶点的入度。

张小头

// 仅供参考 
// Created by John on 2021/02/22.
//邻接表求所有顶点入度
//
/**
 * 求邻接表所有顶点的入度
 * 主要思想：使用一个辅助数组count[]来存对应位置顶点的入度，遍历所有邻接表，每次遇到入度就往count[]对应位置+1
 * @param adjlist 顶点数组
 * @param count 入度数组
 */
void in_degree(Vnode adjlist[], int count[]){
    Enode *firstE;//用来占存当前顶点邻接表的第一个结点
    int i;
    for (i = 0; i < sizeof adjlist / sizeof (adjlist[0]); ++i) {
        firstE = adjlist[i].firste;//当前顶点的邻接表第一条弧
        //遍历当前的邻接表，对弧所指向的顶点在对应的count[]位置的值＋1
        while (firstE != NULL){
            count[firstE->num] = count[firstE->num] + 1;
            firstE = firstE -> eptr;
        }
    }
}

发表于 2021-02-23 15:16:16 回复(0)