Adjacency List - Incorrect Order
Dec 2, 2011 at 5:14am UTC
I am having problem to create adjacent list in correct order. I think there is some problem in CreateAdjList(void)method. I run out of ideas. Please give me some tips. Basically I have graph and creating Adjacency list on connected edges.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
#include <stdio.h>
#include <stdlib.h>
#define maxV 100
typedef struct graphnode{
int vertex;
struct graphnode *next;
}Node;
Node **node;
Node **nodeT;
FILE *fp;
void initial(int nv);
void AdjList(void );
void PrintAdjList(int nv);
int main()
{
int nv;
fp= fopen("input.txt" ,"r" );
fscanf(fp,"%d" ,&nv);
initial(nv);
CreateAdjList();
PrintAdjList(nv);
return 0;
}
//INTIAL NODE STRUCT
void initial(int nv)
{
int i;
node = new Node *[maxV];
for (i=1;i<=nv;i++){
node[i] = (Node *)malloc(sizeof (Node));
node[i]->next=NULL;
}
}
//CREATE ADJACENCY LIST -
void CreateAdjList(void )
{
int v1,v2;
Node *ptr;
while (fscanf(fp,"%d%d" ,&v1,&v2)!=EOF){
ptr = (Node *)malloc(sizeof (Node));
ptr->vertex = v2;
ptr->next = node[v1]->next; //Problem could be here
node[v1]->next = ptr;
}
fclose(fp);
}
//PRINT LIST
void PrintAdjList(int nv)
{
int i;
Node *ptr;
for (i=1; i<=nv; i++){
ptr = node[i]->next;
printf(" node[%2d] " ,i);
while (ptr != NULL){
printf(" -->%2d" , ptr->vertex);
ptr=ptr->next;
}
printf("\n" );
}
printf("\n" );
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Input:
8
1 2
2 3
2 5
2 6
3 4
3 7
4 3
4 8
5 1
5 6
6 7
7 6
7 8
8 8
This is Expected output
1: 2
2: 3 5 6
3: 4 7
4: 3 8
5: 1 6
6: 7
7: 6 8
8: 8
ACTUAL PROGRAM OUTPUT - WRONG ORDER
However I am getting in reverse way .
node[ 1] --> 2
node[ 2] --> 6 --> 5 --> 3
node[ 3] --> 7 --> 4
node[ 4] --> 8 --> 3
node[ 5] --> 6 --> 1
node[ 6] --> 7
node[ 7] --> 8 --> 6
node[ 8] --> 8
Dec 2, 2011 at 5:34am UTC
How about push new node at back?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
void CreateAdjList(void )
{
int v1,v2;
Node *ptr;
while (fscanf(fp,"%d%d" ,&v1,&v2)!=EOF){
//create a new node
ptr = (Node *)malloc(sizeof (Node));
ptr->vertex = v2;
// search the tail of the v1-th node
Node *tail_of_the_node=node[v1];
while (tail_of_the_node->next){
tail_of_the_node=tail_of_the_node->next;
}
// connect to it.
ptr->next = tail_of_the_node->next;
tail_of_the_node->next = ptr;
}
fclose(fp);
}
Last edited on Dec 2, 2011 at 5:39am UTC
Topic archived. No new replies allowed.