graph.h

图邻接表的建立,深度优先遍历,.广度优先遍历,最小生成树,拓扑排序,单源点到其余各个顶点的最短路径等对图的操作!VC界面!

// Graph.h: interface for the Graph class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_GRAPH_H__D59AAB30_1048_4822_9441_CBD00DA82250__INCLUDED_)
#define AFX_GRAPH_H__D59AAB30_1048_4822_9441_CBD00DA82250__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class EdgeLink
{
public:
	int weight;
	int v1;
	int v2;
    EdgeLink *next;
	EdgeLink (int vt1,int vt2,int w=0, EdgeLink *nxt=0)
	{
		v1=vt1;v2=vt2;weight=w;next=nxt;
	}

};

typedef EdgeLink*  Edge;


struct LinkHead
{
	int Mark;
	Edge next;
};

class Graph
{
private:

	int numVertex;
	int numEdge;
public:
	LinkHead *list;
	CString ch;
	CString str;
	Graph(int v,int e,CString ch1);//建立空图或初始图
	~Graph();
	int n() {return numVertex;}//返回图的顶点个数
	int e() {return numEdge;}//返回图的边条数
	bool InsertEdge(CString u,CString v,int Mark=1,int weight=0);//插入边(u,v)
	bool IsEmpty();//如果为图为空，则返回真，否则返回假
	void ReStart();
	Edge first (int);//返回顶点的第一条边
	bool isEdge(Edge);
	Edge next(Edge);//返回顶点的下一条边
	int v1(Edge);//返回弧的弧尾或边的一个端点
	int v2(Edge);//返回弧的弧头或边的另一个端点
	int weight(int ,int );//返回边的权
	int weight(Edge);
	CString TopSort();
	CString BFS(int start);
	CString DFS(int v);
};


typedef int* Edge1;

class Graph1
{
private:
	int numVertex;     //图的顶点个数
	int numEdge;       //边条数
	CString ch;
	CString str;
public:
	int *matrix;
	Graph1(int v,int e,CString ch1);
	~Graph1();
	int n() {return numVertex;}
	int e() {return numEdge;}
	bool InsertEdge(CString u,CString v,int weight=0,int Mark=0);    //插入边（u,v)
	bool IsEmpty();                      //如果为空，则返回真，否则返回假
	void ReStart();
	Edge1 first(int);
	Edge1 next(Edge1 w);
	bool isEdge(Edge1);
	int v1(Edge1);
	int v2(Edge1);
	int weight(Edge1);
	int minVertex(int *D);
	CString Prim(CString c);
	int *Dijkstra(CString c);
	void printTree(int s,int h);
};



#endif // !defined(AFX_GRAPH_H__D59AAB30_1048_4822_9441_CBD00DA82250__INCLUDED_)