adjmlist.h

用Kruskal算法实现若干个城市之间的最短路径.最大城市数目为7个.

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

#if !defined(AFX_ADJMLIST_H__DC4D3D7E_F9AD_4891_AB57_94CA047C1EDC__INCLUDED_)
#define AFX_ADJMLIST_H__DC4D3D7E_F9AD_4891_AB57_94CA047C1EDC__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "iostream.h"

const int MaxV=7;         //最多顶点数

const int MaxValue=99;         //最大权值

struct edgenode          //定义邻接表中的边结点类型
 {
  int adjvex;     //邻接点域
  int weight;     //权值域
  edgenode* next; //指向下一个边结点的链域
};

typedef edgenode** adjlist;          //定义邻接表类型

struct edge              //定义边集数组中的元素类型
{
  int fromvex;           //起点域
  int endvex;            //终点域
  int weight;            //权域
};
struct RCW
{
  int row,col;
  int weight;
};


class adjMList  
{
  int numE;            //当前边数
  int GA[MaxV][MaxV];        //定义邻接矩阵
 public:
	 int Find(int s[],int f);                     //判断是否产生回路
	  void Kruskal(edge GE[],int v,int e);         //利用克鲁斯卡尔方法求边集数组GE
											          //的最小生成树,并输出路径
      void ChangeEdgeSet(edge GE[],int v,int e);       //根据图的邻接矩阵生成图的边集数组
	  void OutputEdgeSet(edge ge[],int e);             //输出边集数组中的每条边
	  void CreateMatrix(int v,int &e,RCW r[]);        //建立带权图的邻接矩阵
           adjMList(edge GE[],int v,int e);           //构造函数,初始化图的邻接矩阵与边集数组
      virtual ~adjMList();
};

#endif // !defined(AFX_ADJMLIST_H__DC4D3D7E_F9AD_4891_AB57_94CA047C1EDC__INCLUDED_)