graph_matrix.h

这个代码包括求图的最大生成树和Ｍ着色问题．

#ifndef GRAPH_MATRIX_H
#define GRAPH_MATRIX_H
/* 32 bit biggest int, to make two vertex disconnect, set their distance to MAX_INT */
#define MAX_INT 0xFFFFFFFF
#define MAX_DIS MAX_INT
#define OK 0
#define ERROR -1

/* structure: edge
 * description: to descript a edge
 */
class edge
{
public:
	int src;	//source vertex
	int dst;	//dest vertex
	size_t	length;//length from source to dest

	bool operator < (edge &e){ return length < e.length;}
	bool operator = (edge &e){ src = e.src; dst = e.dst; length = e.length; return true;}
};
/* class: mgraph
 * description: a weighted and directed graph, implementing as a matrix
 */
class mgraph
{
 public:
  size_t size;			/* how many vertex in the graph */
  size_t *edgematrix;		/* edge matrix edgematrix[i][j] is the length from i to j */

   mgraph(size_t size);	/* creater */
   ~mgraph();		/* destroyer */

   int connect(int i, int j, int distance); /* make i and j connected, the distance between i and j is distance */
   int read_file(char *file);	/* read graph from file */
   int print();					/* print the graph out */
   int max_span_tree(mgraph &g);		/* return he's max spanning tree */
 private:

};
#endif	/*  GRAPH_MATRIX_H */