davidd@wolf.cs.washington.edu (David Doll) (01/14/91)
Hello, I'm working on a problem and I was wondering if I could get some input
from you expert's :-). The problem is the graph-coloring problem;
a k-coloring of an undirected graph G = (V,E) is a function c: V -> {1,2,...k}
such that c(u) != c(v) for every edge (u,v) an element of E. In other words,
the numbers 1,2,...k represent the k colors, and adjacent vertices must have
different colors. The objective is to deteremine the minimum number of colors
needed to color a given graph.
I guess my first question is, does everybody use a collection of adjacency
lists or an adjacency matrix? These seem like the only data structures that
fit into the picture. So would you start with somethig like:
/*
The nodes for the beginning of the lists are kept in an array adj indexed
by vertex. To add an edge connecting x to y to this , we add x to y's
adjacency list and y to x's adjacency list.
*/
#define MAX_V 100
struct node {
int v;
struct node *next;
}
int j,x,y,V,E;
struct node *t, *z;
struct node *adj[MAX_V]
adjlist () {
build adjlist from user input...???
}
Also I not sure about the calls to malloc during this build, any suggestions?
If you can e-mail me, I'll summarize if there's interest.Thanks for your words
and help, I appreciate it.
--
David Doll
Computer Science Dept.
University of Washington
Seattle, WA 98195
M/S: FR-35
davidd@cs.washington.edu