c - total vertices without edges C

Question

So I'am studying for my exam, and found the following question which i couldn't understood how to solve it:

The Graph:

        typedef struct NODE{
             int weight;
             int idEdge;
             int idDestination;
             struct NODO *next;
        }Node;

And following this prototype:

    int totVertexWithoutEdges(Node **g, int totv)

I must create the function that gives me the total number of vertex without edges but I have no ideia how to do it, can anyone just explain me how should I solve it, not asking for the answer just some steps to reach it.

Answer 1

您的 totVertexWithoutEdges 只需要浏览您的 Node** g，这将是指向链表的指针的地址。

可能类似于（基于最后一个元素指向 NULL 的事实）

while (*g != NULL)
{
     // Check out what you want about your edge things
     g = &(*g)->next;
}

但如果 totv 表示顶点数，则为

int   counter;

counter = 0;
while (counter < totv)
{
     // Check out what you want about your edge things
     g = &(*g)->next;
     counter = counter + 1;
}

链表是一种众所周知的数据结构；），祝您练习顺利。

Answer 2

一种方法是创建一个数组，每个节点有一个条目。最初，将此数组中的所有元素设置为 0。

然后，遍历所有边。对于每条边，将表示对应于源节点（和/或目标节点，具体取决于您如何解释问题）的数组元素的数组元素更改为 1。这标志着该节点有一条边与之相连。

最后，遍历数组并计算 0 条目的数量，它告诉您没有传入/传出边的节点总数。

希望这可以帮助！