LinuxQuestions.org - how to define a structure node in graph in a c program

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - how to define a structure node in graph in a c program (https://www.linuxquestions.org/questions/programming-9/how-to-define-a-structure-node-in-graph-in-a-c-program-840778/)

how to define a structure node in graph in a c program

I wanted to implement a graph.By graph I mean to say that I am writing programs for BFS,DFS and other such stuff and want to see them in action.

For this I started writing a program.The first entry point is to define a graph.
I took a pen and paper and made a graph.
Now to be able to code this in C.I defined a structure but I am finding problem in defining this structure.
I looked into Google and came across incidence list and adjacency list representation
http://en.wikipedia.org/wiki/Incidence_list
after understanding that I am not able to understand how do I define my structure that would be a node in graph.

Here is what my graph looks like

Quote:

|-----------31
| |
| 2---4---6---8
| |
--- 5--13-------|
| 19
|---12---27-----|
| | |
----- |
28

This is the above graph the numbers would be what I will give as input but I am not able to understand how do I define a structure for the same.

27 is connected to 28
12 has an edge to itself
31 is connected to 6 and not 2 as you see in question
The formating of above graph in forum is not coming clearly so when I save in quotes/code tags the changes get lost.
Ok here is a pictorial representation

http://www.flickr.com/photos/55167530@N02/5119750360/

Quote:

I looked into Google and came across incidence list and adjacency list representation

I would suggest ignoring the "Incidence List" article in wikipedia, which complicates the data structure (my suspicion is that the article was added to promote the book that it references; edge oriented adjacency lists have been around since at least the 1970s).

However, it is worth reading the adjacency list and adjacency matrix articles.

The simplest representation is an array of pairs, where each pair structure contains the vertices of a single edge. This is effectively a list of edges. However, this representation is slow for many applications such as traversals, because it is hard to find the next vertices as you traverse the graph.

An adjacency matrix is a two dimensional array, which contains the connection between each pair of vertices. In other words, each index combination represents two vertices, and the value of the array is the edge cost; vertices that are not connected will have a dummy value at that point of the array (eg 0). An adjacency matrix is fast for some applications (though not for traversal). And for graphs where the number of edges is significantly less than the number of vertices squared, it wastes a lot of storage.

An adjacency list is an array of vertices, where each array entry has a list of other vertices adjacent to that vertex. It is an efficient way of storing all the data, and allows easy traversal of the graph, so it is a reasonable structure for your application.

Your example (undirected) graph:

Code:

|--------------31

|              |

|    2-----4----6-----8

|    |

|----5-----13---\

    |          19

    12-----27---/

          |

          28

For your example, the adjacency list would look like this:

Code:

2: 4, 5

4: 2, 6

5: 2, 12, 13, 31

6: 4, 8, 31

8: 6

12: 5, 27

13: 5, 19

19: 13, 27

27: 12, 19, 28

28: 27

31: 5, 6

and the adjacency matrix like this:

Code:

    2  4  5  6  8 12 13 19 27 28 31

 2    1  1

 4  1        1

 5  1              1  1          1

 6    1        1                1

 8          1

12        1                1

13        1              1

19                    1    1

27                1    1    1

28                          1

31        1  1

I know what an adjacency list is I also know the matrix thing.
I am asking for a data structure some like of struc node {};
thing what do I need to define this struct node as?

Quote:

Originally Posted by jamesbon (Post 4141963)

I am asking for a data structure some like of struc node {}; thing what do I need to define this struct node as?

The main list will be an array of node structures.

The node structure will contain the list of adjacent nodes.

The simplest would be to number the nodes (ie, use integers to index them), which means that the adjacency list will be a list of integers. You could implement this as a pointer to integer (and use malloc to allocate the array of integers) along with a length value.

Or you could implement the list it as a linked list, and the structure would contain a pointer to the head of the list.