// 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_)