graph.h

用C实现树和图的相关算法

#ifndef GRAPH_H
#define GRAPH_H
#include "list.h"
#include "poly.h"
#include "string.h"
#include "tree.h"

enum edgeClassif {ORD,TRE,BACK,FORW,CROSS};       //边的分类，共有四种：树边、向后边、向前边，行向边，初始值为ORD

typedef struct graphType
{
	list vertices;
	mystring graphName;
}*graph;


typedef struct graphVertexType
{
	list edges;
	int level;
	poly vInfo;
	int visitFlag;                                              //该位标记结点是否被访问，初始值为0，即没被访问
	int x;                                                      //x和y标记，用来确定边的类型
	int y;                                                      //也可以用x和y确定边的入度和出度
}*graphVertex;


typedef struct graphEdgeType
{
	graphVertex from;
	graphVertex to;
	edgeClassif eTpye;
	poly eInfo;
}*graphEdge;


graph newGraph(mystring name);
graphVertex newGraphVertex(poly el);
graphEdge newGraphEdge(graphVertex start,graphVertex end);

void graphInsertVertex (graph g, poly v);
graphVertex searchGraphVertex(graph g,poly x);
void graphInsertEdge(graph g, poly from, poly to);
graphEdge searchEdge(graph g,poly start,poly end);
void graphInsertEdgeInfo (graph g, poly from, poly to, poly info);

void visitGraph(poly x); 

void graphClear(graph p);                     //当结点被一个算法遍历过后，所有的访问标记都为1，该函数把访问标记清零

void graphDfs (graph g, graphVertex start);
tree graphDfsTree (graph g, graphVertex start);

void graphBfs (graph g, graphVertex start);
tree graphBfsTree (graph g, graphVertex start);

tree graphDijkstra(graph g, graphVertex start);
void graphTopoSort(graph g);
tree graphKruskal(graph g);
tree graphPrim(graph g);


void visitGraph(poly p);


//void outputDfsEdge(graph g,graphVertex start); //打印出树边

#endif