C中有向图的实现

Question

我一直坚持在两个节点之间创建弧线，有人可以为我提供伪代码，这将帮助我继续吗？我不明白如何填充City数组的每个节点指针的邻接表。据我了解，id_tail应该是邻接表的第一个节点的顶​​点，而id_head应该是目的节点的顶点。下面是代码，在其中插入了一些测试功能。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 20
#define DIM 50
#define NUM_NODES_TEST 11

typedef struct node
{
    int vertex_id;
    struct node* link;
}Node;

typedef struct
{
    char name[DIM];
    int  population;
    char country[DIM];
    Node* list_adj;
}City;


void load_city_test(City graph[]);
void load_directed_graph_test(City graph[], int num_nodes);
void create_arc(City graph[], int id_tail, int id_head, int num_nodes);
void print_list_adj(City graph[], int num_nodes);


int main()
{
    City graph[MAX_VERTICES];
    int num_nodes = 0;

    load_city_test(graph);
    for (int i = 0; i < NUM_NODES_TEST; ++i) {
        printf("%s\n", graph[i].name);
    }

    load_directed_graph_test(graph, NUM_NODES_TEST);

    print_list_adj(graph, NUM_NODES_TEST);
}

void load_city_test(City graph[])
{    
    strcpy(graph[0].name, "Cagliari");
    strcpy(graph[0].country, "Italy");
    graph[0].population = 300000;
    graph[0].list_adj = NULL;

    strcpy(graph[1].name, "Zurich");
    strcpy(graph[1].country, "Switzerland");
    graph[1].population = 400000;
    graph[1].list_adj = NULL;

    strcpy(graph[2].name, "Lyon");
    strcpy(graph[2].country, "France");
    graph[2].population = 500000;
    graph[2].list_adj = NULL;

    strcpy(graph[3].name, "Genoa");
    strcpy(graph[3].country, "Italy");
    graph[3].population = 800000;
    graph[3].list_adj = NULL;

    strcpy(graph[4].name, "Rome");
    strcpy(graph[4].country, "Italy");
    graph[4].population = 4000000;
    graph[4].list_adj = NULL;

    strcpy(graph[5].name, "New York");
    strcpy(graph[5].country, "USA");
    graph[5].population = 8500000;
    graph[5].list_adj = NULL;

    strcpy(graph[6].name, "Bilbao");
    strcpy(graph[6].country, "Spain");
    graph[6].population = 350000;
    graph[6].list_adj = NULL;

    strcpy(graph[7].name, "Berlin");
    strcpy(graph[7].country, "Germany");
    graph[7].population= 3500000;
    graph[7].list_adj = NULL;

    strcpy(graph[8].name, "London");
    strcpy(graph[8].country, "Great Britain");
    graph[8].population = 8700000;
    graph[8].list_adj = NULL;

    strcpy(graph[9].name, "Miami");
    strcpy(graph[9].country, "USA");
    graph[9].population = 450000;
    graph[9].list_adj = NULL;

    strcpy(graph[10].name, "Tokyo");
    strcpy(graph[10].country, "Japan");
    graph[10].population = 13700000;
    graph[10].list_adj = NULL;
}

void load_directed_graph_test(City graph[], int num_nodes)
{
    load_city_test(graph);

    create_arc(graph, 0, 1, num_nodes);
    create_arc(graph, 0, 4, num_nodes);
    create_arc(graph, 1, 0, num_nodes);
    create_arc(graph, 1, 2, num_nodes);
    create_arc(graph, 2, 1, num_nodes);
    create_arc(graph, 2, 3, num_nodes);
    create_arc(graph, 4, 0, num_nodes);
    create_arc(graph, 4, 1, num_nodes);
    create_arc(graph, 4, 5, num_nodes);
    create_arc(graph, 4, 6, num_nodes);
    create_arc(graph, 5, 1, num_nodes);
    create_arc(graph, 6, 7, num_nodes);
    create_arc(graph, 8, 9, num_nodes);
    create_arc(graph, 9, 8, num_nodes);
    create_arc(graph, 9, 10, num_nodes);
}

void create_arc(City graph[], int id_tail, int id_head, int num_nodes)
{
    Node* newnode;

    newnode = malloc(sizeof(Node));
    if (!newnode)
        printf("Not allocated!\n");
    else{
        for (int i = 0; i < num_nodes; ++i) {
            newnode->vertex_id = id_tail;
            graph[i].list_adj = newnode;

            /*I'm stuck here*/

        }
    }

}

void print_list_adj(City graph[], int num_nodes)
{
    for (int i = 0; i < num_nodes; ++i) {
        printf("%s\n", graph[i].name);
    }
}

在第一个答案之后，我编写了这段代码，但是我不明白如何使用在函数中作为参数传递的节点数。

void create_arc(City graph[], int id_tail, int id_head, int num_nodes)
{
    Node *newnode = malloc(sizeof(Node)), *prec = NULL, *curr = graph[id_tail].list_adj;

    while (curr && curr->vertex_id < id_head){
        prec = curr;
        curr = curr->link;
    }

    newnode = malloc(sizeof(Node));
    if (!newnode)
        return;
    newnode->vertex_id = id_head;

    if (!prec){ //insert on top
        newnode->link = graph[id_tail].list_adj;
        grafo[id_tail].list_adj = newnode;
    } else{ //insert middle or tail
        prec->link = newnode;
        newnode->link = curr;
    }
}

Answer 1

[City graph[]是您的整个图，但是每个City通过City.list_adj]引用相邻的节点>

并且您会将Node / struct node视为链接列表

所以我将以这种方式更改create_arc：

// shorthand reference
// initialize new node
Node *newnode = malloc(sizeof(Node));
if(newnode == NULL ) {abort();} // prefer spelling out the test.

newnode->vertex_id = tail;
newnode->link=NULL; // not necessary

// insert our new arc at the head of the linked list
City *current = &(graph[head]);
newnode->link = current->list_adj;
current->list_adj = newnode;
逐步：

1. City.list_adj -> NULL
2. [City.list_adj -> NULL，insert0 -> NULL
3. City.list_adj -> insert0 -> NULL
4. [City.list_adj -> insert0 -> NULL，insert1 -> Insert0 ...
5. City.list_adj -> insert1 -> insert0 -> NULL...

您也可以尝试在列表末尾插入，但是您必须搜索列表末尾。