Witam
Chcę napisać w języku C graf skierowany oparty na liście sąsiedztwa. Wyczytałem, że taki graf ma być oparty na tablicy list, gdzie indeksy tablicy mają odpowiadać numerom wierzchołków. Czy wie ktoś może jak zrealizować taki graf w języku C ?
0
1
"... graf ma być oparty na tablicy list ..." - którego słowa nie rozumiesz?
0
A no bo lista to z tego co rozumiem struktura oparta na węzłach tutaj tak ? No i teraz to miałbym wpakować po prostu w taką najzwyklejszą tablicę ?
0
Zrób 2 struktury, Graf i Węzeł. Coś takiego
struct Wezel {
int numer;
Wezel * nastepne[]; //wskaznik na tablice wskaznikow nastepnych elementow typu Wezel, pseudokod
}
struct Graf {
Wezel * poczatkowy;
//jakies funkcje na grafie
}
Jest lista sąsiedztwa, jest tablica, jest graf :D
0
Czy taka implementacja jest poprawna ?
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int value;
struct Node *next;
}node;
node **arrayList;
void addVertex(int nrVertex);
void addEdge(int nrVertex, int value);
int main(void) {
int nrVertex,nrEdge;
arrayList = malloc(sizeof(4 * sizeof(node*)));
for(;;) {
if (scanf("%d",&nrVertex)!= 1) break;
scanf("%d",&nrEdge);
addVertex(nrVertex);
addEdge(nrVertex,nrEdge);
}
return 0;
}
void addVertex(int nrVertex) {
if(!(arrayList[nrVertex])) {
arrayList[nrVertex] = malloc(sizeof(node));
arrayList[nrVertex] = NULL;
}
}
void addEdge(int nrVertex, int value) {
node *newNode;
newNode = malloc(sizeof(node));
newNode->value = value;
newNode->next = arrayList[nrVertex];
arrayList[nrVertex] = newNode;
}
1
Nie. Zadanie brzmi jednoznacznie: Dopiero zauważyłem że masz prawie dobrze, z tym że nie elegancko.
typedef struct _Node
{
//double weight; // ewentualnie waga/koszt
unsigned nodeto;
struct _Node *next;
} Node;
typedef struct _Graph
{
unsigned count;
Node **table;
} Graph;
0
Oo widzisz.
Rozumiem ,że unsigned count
to licznik list, a unsigned nodeto
to numer wierzchołka grafu . A co miałeś na myśli z "//double weight" ?