Кодирование списка смежности, представляющей график


Я хочу написать некоторый базовый код на графа, как ДПП, БФС, но перед этим я кодирование графической представленности в смежности список, и некоторые основные функции, такие как readgraphfrommatrix. (Это инициализации графа из матрицы смежности, которые проще поставить в качестве входных данных для тестирования программы.)

Вершина может быть какая-то информация, как имя (скажем, имя города), кромка может иметь некоторую информацию, как вес.

Тут ниже код выглядит достаточно приличный или есть более стандартный признала фрагменты кода для списка смежности представления графов?

struct edge
{
    char *data;
}

struct vertex 
{
    char *data;
};

struct node
{
    int vertexnumber; 
    struct node *next;
}

struct graph
{
    int nvertex,nedges; //
    struct vertex **V; // in main, I will malloc depending on input to have sth like struct vertex V[nvertex];
    struct edge **E //to have like struct edge E[nedges];
    struct node **list ; // to have like struct node* list[nvertex];
}


1827
5
задан 31 мая 2011 в 11:05 Источник Поделиться
Комментарии
1 ответ

Код стиля: использование typedef структуры , а не структуры для чистоты.

Это выглядит нормально в целом, но не является, строго говоря, в список смежности представление. В списке смежности представление вы храните список verticies, и каждая из этих verticies хранить список своих соседей. Эта структура имплицитно кодирует ребер графа.

Более компактное представление смежности может выглядеть чем-то вроде этого:

typedef struct{
char *data;
struct vertex **neighbours;
char **weight; // edge to neighbours[i] stored in weight[i]
} vertex;

typedef struct{
int num_verticies;
struct vertex **V;
} graph;

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

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

3
ответ дан 13 апреля 2012 в 06:04 Источник Поделиться