Реализация графа со списком смежности в C - PullRequest
Новая
       45

Реализация графа со списком смежности в C

1 голос
/ 18 апреля 2019

Я прочитал код, реализующий граф со списком смежности.Но я такойсбит с толку насчет функции addEdge.

В функции следующего кода, когда назначается newNode-> nextс массивом [src] .head.Это означает, что следующий узел newNodeМассив [SRC] .Head.Но после оператора "graph-> array [src] .head = newNode;" порядок будет обратным, когда мы проверяем результат.Может кто-нибудь объяснить мне?Спасибо! 

#include <stdio.h> 
#include <stdlib.h> 

// A structure to represent an adjacency list node 
struct AdjListNode 
{ 
    int dest; 
    struct AdjListNode* next; 
}; 

// A structure to represent an adjacency list 
struct AdjList 
{ 
    struct AdjListNode *head;  
}; 

// A structure to represent a graph. A graph 
// is an array of adjacency lists. 
// Size of array will be V (number of vertices  
// in graph) 
struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

// A utility function to create a new adjacency list node 
struct AdjListNode* newAdjListNode(int dest) 
{ 
    struct AdjListNode* newNode = 
     (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
    newNode->dest = dest; 
    newNode->next = NULL; 
    return newNode; 
} 

// A utility function that creates a graph of V vertices 
struct Graph* createGraph(int V) 
{ 
    struct Graph* graph =  
        (struct Graph*) malloc(sizeof(struct Graph)); 
    graph->V = V; 

    // Create an array of adjacency lists.  Size of  
    // array will be V 
    graph->array =  
      (struct AdjList*) malloc(V * sizeof(struct AdjList)); 

    // Initialize each adjacency list as empty by  
    // making head as NULL 
    int i; 
    for (i = 0; i < V; ++i) 
        graph->array[i].head = NULL; 

    return graph; 
} 

// Adds an edge to an undirected graph 
void addEdge(struct Graph* graph, int src, int dest) 
{ 
    // Add an edge from src to dest.  A new node is  
    // added to the adjacency list of src.  The node 
    // is added at the begining 
    struct AdjListNode* newNode = newAdjListNode(dest); 
    newNode->next = graph->array[src].head; 
    graph->array[src].head = newNode; 

    // Since graph is undirected, add an edge from 
    // dest to src also 
    newNode = newAdjListNode(src); 
    newNode->next = graph->array[dest].head; 
    graph->array[dest].head = newNode; 
} 

// A utility function to print the adjacency list  
// representation of graph 
void printGraph(struct Graph* graph) 
{ 
    int v; 
    for (v = 0; v < graph->V; ++v) 
    { 
        struct AdjListNode* pCrawl = graph->array[v].head; 
        printf("\n Adjacency list of vertex %d\n head ", v); 
        while (pCrawl) 
        { 
            printf("-> %d", pCrawl->dest); 
            pCrawl = pCrawl->next; 
        } 
        printf("\n"); 
    } 
} 

// Driver program to test above functions 
int main() 
{ 
    // create the graph given in above fugure 
    int V = 5; 
    struct Graph* graph = createGraph(V); 
    addEdge(graph, 0, 1); 
    addEdge(graph, 0, 4); 
    addEdge(graph, 1, 2); 
    addEdge(graph, 1, 3); 
    addEdge(graph, 1, 4); 
    addEdge(graph, 2, 3); 
    addEdge(graph, 3, 4); 

    // print the adjacency list representation of the above graph 
    printGraph(graph); 

    return 0; 
}

1 Ответ

1 голос
/ 18 апреля 2019

В функции следующего кода, когда newNode->next назначается с array[src].head.Это означает, что next узел newNode равен array[src].head.Но после утверждения graph->array[src].head = newNode; порядок меняется, когда мы проверяем результат.Может кто-нибудь объяснить мне?Спасибо!

Это правильно.Функция addEdge вставляет новый узел в начало списка, как вы подтвердили из результатов теста.

Эта строка: 

newNode->next = graph->array[dest].head;

делает указатель next нового узла указателем на начало текущего списка (до обновления списка).

Тогда этострока: 

graph->array[dest].head = newNode;

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

Теперь список выглядит так: 

[head == new-node] -> [... state of list before addEdge was called ...]
...