Adjacency List - Incorrect Order

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

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
Topic archived. No new replies allowed.