왜 출력이 올바르지 않습니까?

Question

글자로 그래프를 만들고 싶지만 잘못된 것이 있습니다.

내 코드 :

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

struct AdjListNode 
{ 
    char *dest; 
    struct AdjListNode* next; 
}; 


struct AdjList 
{ 
    struct AdjListNode *head; // pointer to head node of list 
}; 

struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

struct AdjListNode* newAdjListNode(char *dest){ 
struct AdjListNode* newNode = 
    (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
newNode->dest = dest; 
newNode->next = NULL; 
return newNode;} 

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;} 

void addEdge(struct Graph* graph, char *src, char *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 beginin 
struct AdjListNode* newNode = newAdjListNode(dest); 
newNode->next = graph->array[0].head; 
graph->array[0].head = newNode; 

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

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("-> %s", pCrawl->dest); 
     pCrawl = pCrawl->next; 
    } 
    printf("\n");}} 

int main(){ 
// create the graph given in above fugure 
int V = 5; 
struct Graph* graph = createGraph(V); 
addEdge(graph, "a", "b"); 
addEdge(graph, "a", "e"); 
addEdge(graph, "b", "c"); 
addEdge(graph, "b", "d"); 
addEdge(graph, "b", "e"); 
addEdge(graph, "c", "d"); 
addEdge(graph, "d", "e"); 


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

return 0;} 

이처럼 내 출력 :

전자> D-> 전자> D-> A-> B-> C-> B-> A->

내 출력은 다음과 같아야합니다

a->b->e 
b->a->c->d->e 
c->b->d 
d->b->c->e 
e->a->b->d 

저를 도와주세요. 나는 다시 물었다. 그러나 다른 질문. 나는이 산출물을 원한다. 문자로 adjList를 만들고 싶습니다

Answer 1

변경된 부분에 대해 설명하고 이유를 설명했습니다. 코드를 변경하지 않아서 쉽게 이해할 수 있습니다.

이 시도 :

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

struct AdjListNode 
{ 
    char *dest; 
    struct AdjListNode* next; 
}; 

struct AdjList 
{ 
    struct AdjListNode *head; // pointer to head node of list 
}; 

struct Graph 
{ 
    int V; 
    struct AdjList* array; 
}; 

struct AdjListNode* newAdjListNode(char *dest) 
{ 
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode)); 
    newNode->dest = dest; 
    newNode->next = NULL; 
    return newNode; 
} 

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; 
} 

void addEdge(struct Graph* graph, char *src, char *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 beginin 

    struct AdjListNode* newNode = newAdjListNode(dest); 

    //***Changed. you need to add edge in src node. But you were always adding in 0 
    newNode->next = graph->array[src[0]-'a'].head; 
    graph->array[src[0]-'a'].head = newNode; 

    // Since graph is undirected, add an edge from dest to src also 
    newNode = newAdjListNode(src); 

    //***Changed. you need to add edge in dest node. But you were always adding in 1 
    newNode->next = graph->array[dest[0]-'a'].head; 
    graph->array[dest[0]-'a'].head = newNode; 
} 

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 %c", v, v + 'a'); 
     while (pCrawl) 
     { 
      printf("-> %s", pCrawl->dest); 
      pCrawl = pCrawl->next; 
     } 
     printf("\n"); 
    } 
} 

int main() 
{ 
    // create the graph given in above fugure 
    int V = 5; 
    struct Graph* graph = createGraph(V); 
    addEdge(graph, "a", "b"); 
    addEdge(graph, "a", "e"); 
    addEdge(graph, "b", "c"); 
    addEdge(graph, "b", "d"); 
    addEdge(graph, "b", "e"); 
    addEdge(graph, "c", "d"); 
    addEdge(graph, "d", "e"); 


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

    return 0; 
} 

그것은 당신 출력 줄 것이다 :

a-> e-> b 
b-> e-> d-> c-> a 
c-> d-> b 
d-> e-> c-> b 
e-> d-> b-> a 

을 그리고 당신은 다음과 같이 동일한 결과를 얻으려면 :

a-> b-> e 
b-> a-> c-> d-> e 
c-> b-> d 
d-> b-> c-> e 
e-> a-> b-> d 

그냥 addEdge 변경() 함수는 다음과 같습니다.

void addEdge(struct Graph* graph, char *src, char *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 beginin 

    struct AdjListNode* newNode = newAdjListNode(dest); 

    //***Changed. you need to add adge in src node. But you were always adding in 0 
    struct AdjListNode* temp=graph->array[src[0]-'a'].head; 

    if(temp==NULL) // First element of the list 
     graph->array[src[0]-'a'].head=newNode; 
    else 
    { 
     while(temp->next!=NULL) // finding the last element of the list 
      temp=temp->next; 
     temp->next=newNode; // Adding current element to the last 
    } 

    // Since graph is undirected, add an edge from dest to src also 
    newNode = newAdjListNode(src); 

    //***Changed. you need to add adge in dest node. But you were always adding in 1 
    temp = graph->array[dest[0]-'a'].head; 

    if(temp==NULL) // First element of the list 
     graph->array[dest[0]-'a'].head=newNode; 
    else 
    { 
     while(temp->next!=NULL) // finding the last element of the list 
      temp=temp->next; 
     temp->next=newNode; // Adding current element to the last 
    } 
} 

첫 번째 코드는 앞에 새 가장자리를 추가하고 두 번째 코드는 마지막에 추가합니다.
도움이 되길 바랍니다.

Answer 2

크기가 알려져 있기 때문에 선형이지만 효과적 인 2D 배열을 사용하여 구현되었지만 일부 유사성 만 유지해야합니다. 그렇지 않으면 V이 알려졌을 때 나는 #define V 5을 선언하고 정적 2D 배열 int graph[V][V]. 단순화와 별개로, 나는 으로 문자열을 단일 문자로 나타내므로 char* 문자열 인수를 변경했습니다. 또한 함수에 크기 인수 V을 전달했습니다.

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

void printGraph(int *graph, int V) { 
    int v, n; 
    for (v=0; v<V; ++v) { 
     printf ("%c", v + 'a'); 
     for (n=0; n<V; ++n) { 
      if (graph [v * V + n]) 
       printf("->%c", n + 'a'); 
     } 
     printf("\n"); 
    } 
} 

void addEdge(int *graph, int V, int src, int dest) { 
    src = tolower(src) - 'a'; 
    dest = tolower(dest) - 'a'; 
    if (src < 0 || src >= V || dest < 0 || dest >= V || src == dest) 
     return;  // error 
    graph [src * V + dest] = 1; 
    graph [dest * V + src ] = 1; 
} 

int *createGraph (int V) { 
    return calloc (V * V, sizeof(int)); 
} 

int main(){ 
    int V = 5; 
    int *graph; 
    if (graph = createGraph(V)) { 
     addEdge(graph, V, 'a', 'b'); // changed from string to char 
     addEdge(graph, V, 'a', 'e'); 
     addEdge(graph, V, 'b', 'c'); 
     addEdge(graph, V, 'b', 'd'); 
     addEdge(graph, V, 'b', 'e'); 
     addEdge(graph, V, 'c', 'd'); 
     addEdge(graph, V, 'd', 'e'); 

     printGraph(graph, V); 
     free (graph); 
    } 
    return 0; 
} 

당신은 정점에 레이블을 "A"에 "E"를 사용하고

a->b->e 
b->a->c->d->e 
c->b->d 
d->b->c->e 
e->a->b->d 

프로그램 출력. 내 대답은 'a'thru 'e'로 변경하고 5x5 배열을 색인화하기 위해이 레이블을 사용했으며이 정점 레이블을 조작하여 0에서 4 범위에 있도록했습니다. tolower()을 사용하여 'A'레이블을 처리했습니다. 'E'는 사용되었지만 사용되지 않았으므로 실제로 필요하지는 않았습니다. 그런 다음 'a'를 빼서 0부터 레이블의 범위를 정합니다. int 값 '97'은 'a' - 'a' = 0과 'e' - 'a' = 4을 볼 수 있도록 값이 97입니다.