# Thread: Cant understand Linked list example:

1. ## Cant understand Linked list example:

Hello!
I am trying to work with Linked Lists for quite a while now.
But i came across the following example that i dont follow\:

Code:
```struct Edge
{
int terminal;
struct Edge *next;
};

struct Vertex
{
int visit;
int vertex_no;
char info;
int path_length;
struct Edge *Edge_Ptr;  //I dont know what it points to , what information needs to be retrieved from it.
Can we call one Linked List in the other???
};```

2. It looks to me like Vertex is a node in a graph, which contains a linked list of edges (presumably so an arbitrary number of edges can be sourced at each vertex). Vertex.Edge_Ptr is a pointer to the first edge in the list. I can only assume, then, that Edge.terminal is a reference to the Vertex.vertex_no at which the edge ends.

If you're trying to learn linked lists it might be worth finding a more generic example as this one looks specific to a graph implementation.

3. I found this help me.
Code:
```#include<stdlib.h>
#include<stdio.h>

struct list_el {
int val;
struct list_el * next;
};

typedef struct list_el item;

void main() {
item * curr, * head;
int i;

for(i=1;i<=50;i++) {
curr = (item *)malloc(sizeof(item));
curr->val = i;
}

while(curr) {
printf("%d\n", curr->val);
curr = curr->next ;
}
system("PAUSE");
return EXIT_SUCCESS;
}```

4. I understand basic concept of Linked list. Just wanted to know what it is pointing to...

Yes Vertex corresponds to nodes in the graph.
I also understood that Vertex.Edge_Ptr points to the struct Edge(terminal).
Does it also mean that Vertex has no NEXT pointer ????

5. Indeed, there is no next pointer for vertex, so either there is no linked list of vertices or there is a separate struct that looks something like this:

Code:
```struct vElement {
struct Vertex *data;
struct vElement *next
};```

6. The structures that are used in this example file
Code:
```struct Edge
{
int terminal;
struct Edge *next;
};

struct Vertex
{
int visit;
int vertex_no;
char info;
int path_length;
struct Edge *Edge_Ptr;
};
struct Q
{
int info;
struct Q *next;
};```
there are only 3 lists.
n the example that u put here.
Code:
```struct vElement {
struct Vertex *data;
struct vElement *next
};```
that means that this structure stores2 pointer:
pointer to the data
next pointer that points to the data pointer

7. Exactly. If there is no "next" pointer in the Vertex struct, then there must be an external list constructed of either instances of Vertex or pointers to instances of Vertex. Apparently neither of these exist, therefore there is no list of vertices.

I'm not really sure what your question is any more.

8. Actually i was working towards BFS alog, then I came across this code for BFS.
It works fine and gives correct results.
I wanted to modify it but i dont follow the whole code.
I dont need the path for the traversal path but just wanna know if a particular is connected to the some other particular node(say if 1 is connected to 5 or so).
But i dont where i shd modify.....

the code is
Code:
```# include <stdio.h>
# define size 20
# define T 1
# define F 0

struct Edge
{
int terminal;
struct Edge *next;
};

struct Vertex
{
int visit;
int vertex_no;
char info;
int path_length;
struct Edge *Edge_Ptr;
};
struct Q
{
int info;
struct Q *next;
};

void Table(int , int matrix [size][size], struct Vertex vert[size]);
struct Edge *Insert_Vertex (int , struct Edge *);
void BFS ( int , struct Vertex vert [size]);
void Input(int, int mat [size][size]);
void Output(int number, int mat [size][size]);
struct Q *Insert_Queue(int vertex_no, struct Q *first);
struct Q *Delete_Queue(int *vertex_no, struct Q *first);

/* Insert vertex into connectivity list */

struct Edge * Insert_Vertex (int vertex_no, struct Edge*first) {
struct Edge *new1, *current;
new1 = (struct Edge *) malloc(sizeof(struct Edge));
new1->terminal = vertex_no;
new1->next = NULL;
if (!first)
return (new1);
for (current = first; current->next; current = current->next);
current->next = new1;
return (first);
}

/* Insert vertices into queue */

struct Q * Insert_Queue(int vertex_no, struct Q *first)
{
struct Q *new1, *current;
new1 =(struct Q *) malloc(sizeof(struct Q));
new1->info = vertex_no;
new1->next = NULL;
if (!first)
return (new1);
for (current = first; current->next; current = current->next);
current->next = new1;
return (first);
}

struct Q * Delete_Queue(int *vertex_no, struct Q *first)
{
struct Q *previous;
if (!first)
return (NULL);
*vertex_no = first->info;
previous = first;
first = first->next;
free(previous);
return (first);
}

/* Initializing entries */

void Table(int vertex_num, int matrix [size][size],struct Vertex vert[size])
{
int i, j;
for (i = 0; i < vertex_num; i++)
{
vert [i].visit = F;
vert [i].vertex_no = i+1;
vert [i].info = 'A'+ i;
vert [i].path_length = 0;
vert [i].Edge_Ptr = NULL;
}

for (i =0; i < vertex_num ; i++)
for (j =0; j < vertex_num ; j++)
if (matrix [i][j] > 0 )
vert [i].Edge_Ptr = Insert_Vertex (j, vert [i].Edge_Ptr);
}

/* Computing path length */

void BFS ( int index, struct Vertex vert [size])
{
struct Q *queue = NULL;
vert [index].visit = T;
queue = Insert_Queue(index, queue);
while(queue)
{
queue = Delete_Queue(&index, queue);
{
if (vert [Link->terminal].visit == F)
{
queue = Insert_Queue(Link->terminal, queue);
}
}
}
}

/* Input function to read adjacency matrix */

void Input(int number, int mat [size][size])
{
int i, j;
printf("\n Input the adjacency matrix \n");
for (i =0; i < number; i++)
{
for (j=0; j < number; j ++)
{
scanf("%d", &mat [i][j]);
}
printf("\n");
}
}

/* Output function to display adjacency matrix */

void Output(int number, int mat [size][size])
{
int i, j;
printf("\n Adjacency matrix \n");
for (i =0; i < number; i++)
{
for (j=0; j < number; j ++)
{
printf(" %d", mat [i][j]);
}
printf("\n");
}
}

/* Function main */
int main()
{
int i, number, index;
int mat [size][size];
struct Vertex vert [size];
struct Edge *List;
printf("\n Input the number of vertices in the graph: ");
scanf("%d", &number);
Input(number, mat);
Output(number, mat);
Table(number, mat, vert);
printf("\n Input the starting vertex 0- %d :",number-1);
scanf("%d", &index);
BFS (index, vert);
printf("\n Path length of the vertex from %c", vert[index].info)
;
printf("\n Vertex Length Vertex Connectivity \n ");
for (i = 0; i < number; i++)
{
printf("\n %c %d ",vert[i].info, vert[i].path_length);
for (List= vert[i].Edge_Ptr; List; List = List->next)
{
printf(" ");

putchar(List->terminal+'A');
}
}
}```
thanks.

9. Well, for each vertex you have an adjacency list. A list of edges, each with a terminal vertex. To determine if vertex u is adjacent to vertex v, just traverse u's adjacency list (starting at u.Edge_Ptr) until you find (i->terminal == v.vertex_no).

10. ohhh.......
that means I shd modify ""struct Edge *Insert_Vertex (int , struct Edge *);""
only rite...

11. Just to be clear, you want to check if a given vertex is adjacent to another (i.e. they are directly connected by a single edge)? If so, you're going to want to do something like this:

Code:
```int isAdjacent (Vertex *u, Vertex *v) {
int number = v->vertex_no;
Edge *current = u->Edge_Ptr;

while(current) {
if (current->terminal == number)
return 1;
current = current->next;
}
return 0;
}```
Edit: Or you could just look it up in the adjacency matrix that's produced for you.

12. No, i dont want id they are directly adjacent to each other.
I want to if A is connected to E(it doesnt really matter how many nodes come in between them, is there a path from A to E dats all)

Actually I have a huge matrix of 42 x 42 matrices.
I just wanna now i there is a connection b=from the source to target(as i name them).

n the second issue is my matrix is 3D...i mean Row x Colx number of iterations.
can you help me here too.....
thanks a lot!!!!!

13. Ah right, sorry. I was misunderstanding what you were asking. Okay, so you want to use this program to determine if two vertices are connected.

So after BFS(source, vert), vert[i] is connected to source if vert[i].path_length > 0. So the easiest way to do this from what you have is probably just to modify main after line 165 to:

Code:
```printf("\n Input option.");
scanf("%d", &option);
if(vert[option].path_length > 0)
printf("\nConnected.\n");
else
printf("\nNot connected.\n");
}```

14. but I dont know what is it asking as option .
Is it asking for the starting node or the final node to establish the connection.....

sorry If m annoying you but i need to get it done.
Thanks.

15. The BFS function updates the path lengths to each node, from "index", so vert[option].path_length gives you the length of the path from the starting vertex to the vertex named option. If this is greater than zero (as all lengths default to zero and will remain at zero if there is no path), you have a path.

So when it asks for the starting vertex, input your source and where it asks for "option", input your target.

That's the quick and dirty way. Better would be to extract the BFS function and modify it to return true if it comes across the desired vertex. But it depends entirely upon whether you want a program or an answer.

Popular pages Recent additions