c - 在 C 中实现有向图
问题描述
我坚持在两个节点之间创建一个弧,有人可以为我提供一个伪代码,这将帮助我继续吗?我不明白如何填充 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;
}
}
解决方案
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++ - CMAKE_C_FLAGS 在子目录中附加标志
- python - Python 单向加密
- wordpress - 如何使用 wp rest nonce 执行 wc api 请求
- spring - 将所有元数据放在 Spring SAML 中的路径中
- flutter - 当我们单击按钮时,如何在 youtube_player_flutter 库中自定义值 YoutubePlayerFlags?
- r - 满足条件时播放声音
- flutter - 如何在滑块上方添加刻度和标签?
- openssl - 无法加载动态库 'openssl' - PHP 启动
- node.js - 未捕获(承诺)错误:在 XMLHttpRequest.handleError (xhr.js:99) 的 createError (createError.js:16) 处出现网络错误
- spring-boot - OpenAPI 生成的 Spring Boot 服务器不验证所需的属性