как мы представляем список ребер, учитывая, что у нас есть граф с узлами иdge.am, не говоря о списках смежности

Question

Что такое пограничный список? Не смежный список. и как мы представляем список ребер в C-программировании при условии, что нам дан граф с узлами и ребрами?

Answer 1

Используя определение найденного списка ребер здесь и предполагая ненаправленные ребра, эмуляция «человеческого» представления была бы хорошей первой попыткой:

typedef struct UndirectedEdge {
    int ends[2];
};

Где все ваши вершины пронумерованы в диапазоне int. Если они направлены:

typedef struct DirectedEdge {
    int from;
    int to;
}

При необходимости добавьте другие свойства с типом, соответствующим вашей проблеме:

typedef struct WeightedEdge {
    size_t from;
    size_t to;
    double weight;
}

Обратите внимание, что список вершин не требуется, если только для отображения целочисленных индексов вершин на понятные человеку метки, если они существуют в вашей исходной задаче. Кроме того, вы должны определить подходящую функцию сравнения для вашего списка ребер, чтобы обеспечить уникальность ваших ребер в зависимости от свойств вашего графа, таких как направленность.

typedef struct EdgeList {
    size_t edge_count;
    EdgeType *edges;
}

_Bool undirected_edge_equal(UndirectedEdge *this, UndirectedEdge *other) {
    return this->ends[0] == other->ends[0] && this->ends[1] == other->ends[1]
        || this->ends[0] == other->ends[1] && this->ends[1] == other->ends[0]
}

_Bool directed_edge_equal(DirectedEdge *this, DirectedEdge *other) {
    return this->from == other->from && this->to == other->to;
}

Answer 2

Вот базовая структура

struct Edge
{
    int id;
    int weight; // If you need one
    vector<Edge *> neighbours; // List of references on your neightbours
}

vector<Edge> graph;

Но, как заметил Майкл, это выглядит как домашнее задание :) Посмотрите на библиотеку загрузочных графиков.

ОБНОВЛЕНИЕ C версия

struct Edge
{
    int id;
    int weight; // If you need one
    Edge *next; // Next edge in the list
    Edge *neighbours; // List of neightbours
}

Edge *graph;