邻接表上求某点v的入度int InDegree (ALGraph *G,int v)
时间: 2023-12-25 22:04:44 浏览: 29
好的,针对你的问题,我可以给出以下的C++代码实现:
```
// 定义邻接表中的边结构体
typedef struct ArcNode
{
int adjvex; // 该边的邻接点编号
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 定义邻接表中的顶点结构体
typedef struct VNode
{
int data; // 顶点信息
ArcNode *first; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAXV];
// 定义邻接表结构体
typedef struct
{
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;
// 求某点v的入度
int InDegree(ALGraph *G, int v)
{
int i, count = 0;
ArcNode *p;
// 遍历邻接表,统计所有邻接点为v的边的数目
for (i = 0; i < G->vexnum; i++)
{
p = G->vertices[i].first;
while (p != NULL)
{
if (p->adjvex == v)
{
count++;
}
p = p->next;
}
}
return count;
}
```
其中,`ALGraph` 是一个邻接表存储的图结构体,`InDegree` 函数用于求某个顶点的入度。在该函数中,我们遍历整个邻接表,对于每个顶点的每条出边,如果该出边的邻接点为 v,则将 count 值加一。最终返回 count 即为 v 的入度。