0

I have a program that accepts an adjacency matrix as input and then computes whether the corresponding graph is a tree. I want to modify it so that it determines whether the graph is specifically a binary tree, but I really can't wrap my head around it. What do I need to do?

Here's the original code:

#include<stdio.h>
#include<stdlib.h>

int A[20][20]; // Our two-dimensional array.
int visited[20];
int v = 0;
int count = 0;
int n;
int seq[20];
int s = 0;
int connected = 1;
int acyclic = 1;

// Declaration of the DFS function
void DFS();

// Declaration of the DFSearch function
void DFSearch(int cur);

int main() {
    int i,j;

    printf("\nStep 1 of 2 — Fill in your desired number of vertices: ");
    scanf("%d",&n);

    printf("\nStep 2 of 2 — Fill in the adjacency matrix(1/0):\n");

    for(i=1;i<=n;i++) {
            for(j=1;j<=n;j++) {
        scanf("%d",&A[i][j]);
        }
    }

    printf("\nThe DFS traversal shows:\n");

    DFS();

    for(i=1; i<=n; i++) {
        printf("%c,%d\t", 'a'+seq[i]-1, i);
    }

    if(connected && acyclic) {
            printf("\n\nThis is a connected and non-cyclic graph. Therefore, it IS a tree.");
    }

    if(!connected && acyclic) {
            printf("\n\nThis is a non-connected and non-cyclic graph. Therefore, it is NOT a tree.");
    }

    if(connected && !acyclic) {
        printf("\n\nThis is a connected and cyclic graph. Therefore, it is NOT a tree.");
    }

    if(!connected && !acyclic) {
            printf("\n\nThis is a non-connected and cyclic graph. Therefore, it is NOT a tree.");
    }
    printf("\n\n");
    return 0;
}

// Definition of the DFS function
void DFS() {
    int i;

    for(i=1; i<=n; i++) {
        if(!visited[i]) {
                if(i>1) {
                    connected = 0;
                    DFSearch(i);
                }
        }
    }
}

// Definition of the DFSearch function
void DFSearch(int cur) {
    int i,j;

    visited[cur]=++count;

    seq[count]=cur;

    for(i=1; i<count-1; i++) {
            if(A[cur][seq[i]]) {
                acyclic = 0;
            }
    }

    for(i=1; i<=n; i++) {
        if(A[cur][i] && !visited[i]) {
           DFSearch(i);
        }
    }
}
John Bollinger
  • 160,171
  • 8
  • 81
  • 157
James Gallagher
  • 1
  • 1
    Is your question "how to determine the given graph is a tree by looking at it's adjacency matrix" ? I am pretty sure there is a theorem about it. If not, it worth writing one. – Eugene Sh. Oct 03 '17 at 18:04
  • 1
    `for(i=1; i<=n; i++)` is suspicious. I'd expect `for(i=0; i – chux - Reinstate Monica Oct 03 '17 at 18:06
  • @chux https://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph — I found the code in this thread, pretty far down (props to Majid NK). I don't actually know why the index starts at 1 instead of 0 – James Gallagher Oct 03 '17 at 18:59
  • @EugeneSh. Yes sir, it is—almost. If it is a binary tree is the question. Couldn't really find anything helpful though... – James Gallagher Oct 03 '17 at 19:01

1 Answers1

0

What distinguishes a binary tree from other trees? Presumably you know that it is precisely that no node has more than one parent or more than two children. Of course, distinguishing parent nodes from child nodes requires a directed graph, or at least an ordered one. That, combined with the general property that trees are acyclic, implies that binary trees are also rooted.

Now, directed graphs are naturally supported by the adjacency matrix representation you are using, so that's no problem. In fact, adjacency matrix representation is slightly unnatural for undirected graphs, but you can serve those well enough by representing them as symmetric adjacency matrices.

Following the program's paradigm, then, I suggest adding a variable

int binary = 1;

and testing as you examine each node whether that node has more than two outgoing edges (and thus, more than two children). If you find a node that does, then set the variable to zero, indicating that although the graph might be a tree, it is not a binary one.

Of course, doing that requires analyzing the program well enough to understand how it works. I am not going to rob you of that valuable experience, but perhaps it will be helpful for me to point out that the program is a little more specific than the question suggests. It does not generally compute whether the provided adjacency matrix corresponds to a tree, but rather whether the matrix,

  • interpreted as a representation of a directed graph,
  • corresponds to a tree rooted at the first node.
John Bollinger
  • 160,171
  • 8
  • 81
  • 157