Tree - Connected acyclic graph - Representation

Question

From wiki,

a tree is an undirected graph in which any two vertices are connected by exactly one Path.

Path is connected sequence of edges

Tree - Example:

enter image description here

It was relatively easy to write multi-walk representation of rooted tree,

typedef struct multiWalkTreeNode{
  struct multiWalkTreeNode * parent;
  void *item;
  struct multiWalkTreeNode **childPointer;
}Node;

typedef struct multiWalkTree{
  Node *root;
  int size; /*Number of nodes in the tree*/
}Tree;

Question:

In a Tree(non-rooted), there are no children/ancestors to any node

1)

How to represent a Tree(non-rooted)?

2) From maintaining huge size Tree & better find() performance aspect, Do we have multiple representations for a Tree(non-rooted)?


Show source
| C   | data-structures   | graph   | tree   2016-12-14 05:12 2 Answers

Answers to Tree - Connected acyclic graph - Representation ( 2 )

  1. 2016-12-14 06:12

    1) Instead of having tracking child and parent links separately, simply add the parent pointer to child and use child as a complete list of adjacent vertices. From a practical perspective you'll have to maintain a pointer to some vertex as an entry point for find(), but otherwise there won't be anything special about any one node.

    2) The two most common methods of tree navigation are Depth First Search and Breadth First Search. Generally, Breadth checks if any of the children are the requested node before the recursive calls on the children. Depth checks itself then performs the recursive call on the children until it reaches a leaf. Neither of these are particularly efficient from a memory standpoint, but they're simple enough to write.

    You could begin your search of the tree at any of the nodes, and the search time would vary greatly, but I wouldn't call it a different representation of the same tree.

  2. 2016-12-14 06:12

    The two basic ways to represent a tree (directed or undirected) are as a adjacency matrix or as an adjacency list. If it is a "dense" tree (i.e. more than half the n2 possible edges for a tree with n nodes), then it is more efficient to represent it as a matrix. If it is a "sparse" tree (less than half the possible n2 edges), then an adjacency list is more efficient.

    Your example tree, represented as an adjacency matrix would be something like: (please forgive the ASCII art)

         1 2 3 4 5 6
        -------------
     1:  0 0 0 1 0 0
     2:  0 0 0 1 0 0
     3:  0 0 0 1 0 0
     4:  1 1 1 0 1 0
     5:  0 0 0 1 0 1
     6:  0 0 0 0 1 0
    

    Each index (horizontally and vertically) corresponds to a node, and a 1 is placed in the matrix if the node for that row has an edge to the node for that column, or a 0 if there is no edge. For example, there is an edge between nodes 3 and 4, so in the matrix, position (3,4) has a 1. (Don't forget that in C, of course, array indexes start with 0. I started with 1 because that was the label of the lowest node and this is just an example.)

    This is a symmetric matrix because it is an undirected graph. You could implement a directed graph by using the row index as the source of the edge, and the column as destination of the edge. Another expansion is to make a weighted directed graph by using the value in the matrix as the weight of the edge, instead of just a 1.

    But notice how inefficient this is for your graph. For a graph with n nodes, you need an n×n matrix (in terms of space, n2 times the size of storing one value). Most of the spaces are empty (0) anyway.

    The other basic method is the adjacency list, which is just that: a list of the adjacent nodes---a list of edges. An adjacency list for your graph might be:

       1,4
       2,4
       3,4
       4,5
       5,6
    

    As long as you know this is an undirected graph, you can get away with only recording 1,4 and just know that this is equivalent to 4,1. For a directed graph, of course, you could say that 1,4 means only "from 1 to 4". Notice that the amount of information you have to store using the adjacency list representation depends on the number of edges, not the number of nodes as with the matrix representation.

    I'll leave it you to figure out how to implement in C a two-dimensional matrix or a list of pairs of values.

    Note that both the adjacency matrix and adjacency list only represent the edges between the nodes. You might also want to store some data in each node. This would require a separate structure, such as a list or an array.

Leave a reply to - Tree - Connected acyclic graph - Representation

◀ Go back