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;

一步一步：

City.list_adj -> NULL
City.list_adj -> NULL , insert0 -> NULL
City.list_adj -> insert0 -> NULL
City.list_adj -> insert0 -> NULL , insert1 -> Insert0 ...
City.list_adj -> insert1 -> insert0 -> NULL ...

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

为了按顺序插入，您必须按以下方式更改代码：

City *current = &(graph[head]);
// list is size 0 no need to look further
if(current->list_adj == NULL) {
    current->list_adj = newnode;
    return;
}
// insert at the head of the list
if(current->list_adj->vertex_id > head) {
    newnode->link = current->list_adj;
    current->list_adj = newnode;
    return;
}
// look at the rest of the list to find 
Node *insert_point = current->list_adj;
while(insert_point->link != NULL) {
    if(insert_point->link->vertex_id > head) { break; }
    insert_point = insert_point->link;
}
newnode->link = insert_point->link;
insert_point->link = newnode;

C中有向图的实现

Implementation of a directed graph in C

c

graph

pseudocode