图的基本概念可以翻书

目录

图的模板基类

邻接矩阵

邻接矩阵的具体类实现

邻接矩阵构造函数实现（基于这个构造函数可以初始化一个邻接矩阵）

图的第二种存储方法———邻接表

 邻接表建立算法！

---

图的存储一般来说有四种，但是由于考试还有本人是鶸，所以就只讨论邻接矩阵与邻接表

图的模板基类

const int maxWeight = ……;	    //无穷大的值(=)
const int DefaultVertices = 30;	    //最大顶点数(=n)
template <class T, class E>
class Graph {			    //图的类定义
protected:int maxVertices;		    //图中最大顶点数int numEdges;			    //当前边数int numVertices;		    //当前顶点数int getVertexPos (T vertex);	//给出顶点vertex在图中位置
public:  Graph (int sz = DefaultVertices);  	//构造函数～Graph();				//析构函数bool GraphEmpty () const 		//判图空否{ return numEdges == 0; }	int NumberOfVertices () { return numVertices; }//返回当前顶点数int NumberOfEdges () { return numEdges; }//返回当前边数virtual T getValue (int i);		//取顶点 i 的值virtual E getWeight (int v1, int v2);  //取边上权值virtual int getFirstNeighbor (int v); //取顶点 v 的第一个邻接顶点virtual int getNextNeighbor (int v, int w);//取邻接顶点 w 的下一邻接顶点virtual bool insertVertex (const T vertex);//插入一个顶点vertexvirtual bool insertEdge (int v1, int v2, E cost);//插入边(v1,v2), 权为costvirtual bool removeVertex (int v);	//删去顶点 v 和所有与相关联边virtual bool removeEdge (int v1, int v2);	//在图中删去边(v1,v2)
};

上面只是基类，大概了解一下而已

邻接矩阵

基本概念

 一般来说，有向图边带权值就是网络

 

邻接矩阵的具体类实现

template <class T, class E>
class Graphmtx : public Graph<T, E> {
friend istream& operator >> (istream& in,   Graphmtx<T, E>& G);			//输入
friend ostream& operator << (ostream& out, Graphmtx<T, E>& G);		//输出
private:T *VerticesList; 			//顶点表 ————>可以理解为顶点数组E **Edge;				//邻接矩阵  二级指针代表二维数组，申请数组空间时要注意int getVertexPos (T vertex) {   //给出顶点vertex在图中的位置for (int i = 0; i < numVertices; i++)if (VerticesList[i] == Vertex) return i;        //返回数组下标return -1; };
public:  Graphmtx (int sz = DefaultVertices);    //构造函数～Graphmtx ()				      //析构函数{ delete [ ]VerticesList;  delete [ ]Edge; }T getValue (int i) {  //取顶点 i 的值, i 不合理返回0 [防止越界]return i >= 0 && i <= numVertices ? VerticesList[i] : NULL; }E getWeight (int v1, int v2) {  //取边(v1,v2)上权值if(return v1 != -1 && v2 != -1 )return Edge[v1][v2];elsereturn 0;}int getFirstNeighbor (int v);       //取顶点 v 的第一个邻接顶点int getNextNeighbor (int v, int w);	//取 v 的邻接顶点 w 的下一邻接顶点bool insertVertex (const T vertex);	//插入顶点vertexbool insertEdge (int v1, int v2, E cost);//插入边(v1, v2),权值为costbool removeVertex (int v);//删去顶点 v 和所有与它相关联的边bool removeEdge (int v1, int v2);//在图中删去边(v1,v2)
};

 

邻接矩阵构造函数实现（基于这个构造函数可以初始化一个邻接矩阵）

构造函数里面的每一条边都初始化为极大值

template <class T, class E>
Graphmtx<T, E>::Graphmtx (int sz) {      //构造函数maxVertices = sz;  numVertices = 0;  numEdges = 0;int i, j;VerticesList = new T[maxVertices];  //创建顶点表（顶点数组）Edge = (int **) new int *[maxVertices];for (i = 0; i < maxVertices; i++)Edge[i] = new int[maxVertices];   //构造邻接矩阵，生成二维数组 for (i = 0; i < maxVertices; i++)        //矩阵初始化，都初始化为最大值for (j = 0; j < maxVertices; j++)Edge[i][j] = (i == j) ？ 0 : maxWeight; 
};

找到一个顶点的第一条边

template <class T, class E>
int Graphmtx<T, E>::getFirstNeighbor (int v) {
//给出顶点位置为v的第一个邻接顶点的位置, 
//如果找不到, 则函数返回-1if (v != -1) {for (int col = 0; col < numVertices; col++)if (Edge[v][col] && Edge[v][col] < maxWeight)   return col;}return -1;
};

找到邻接矩阵的一条边的下一条边

template <class T, class E>
int Graphmtx<T, E>::getNextNeighbor (int v, int w) {
//给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 && w != -1) {for (int col = w+1; col < numVertices; col++) if (Edge[v][col] && Edge[v][col] < maxWeight)  return col; }return -1;
};

图的第二种存储方法———邻接表

注意：节约空间就选邻接表，节约时间就选邻接矩阵，时间复杂度可以根据链表与矩阵的特性进行分析

 

 

邻接表的每一个节点的构造函数

template <class T, class E>
struct Edge {			   //边结点的定义int dest;				   //边的另一顶点位置E cost;				   //边上的权值Edge<T, E> *link;		   //下一条边链指针Edge () {}				   //构造函数Edge (int num, E cost) 	   //构造函数: dest (num), weight (cost), link (NULL) { }bool operator != (Edge<T, E>& R) const{ return dest != R.dest; }	   //判边等否
};

邻接表的顶点定义

template <class T, class E>
struct Vertex {			   //顶点的定义T data;				   //顶点的名字Edge<T, E> *adj;		   //边链表的头指针
};

邻接表类的定义

template <class T, class E>
class Graphlnk : public Graph<T, E> {   //图的类定义
friend istream& operator >> (istream& in, 	Graphlnk<T, E>& G);		    //输入
friend ostream& operator << (ostream& out, 	Graphlnk<T, E>& G);		    //输出
private:Vertex<T, E> *NodeTable;//顶点表 (各边链表的头结点)int getVertexPos (const T vertx) {	//给出顶点vertex在图中的位置for (int i = 0; i < numVertices; i++)if (NodeTable[i].data == vertx) return i;return -1; }
public:Graphlnk (int sz = DefaultVertices);  //构造函数~Graphlnk();				   //析构函数T getValue (int i) {		     //取顶点 i 的值return (i >= 0 && i < NumVertices) ? NodeTable[i].data : 0;}E getWeight (int v1, int v2);	     //取边(v1,v2)权值bool insertVertex (const T& vertex);bool removeVertex (int v);bool insertEdge (int v1, int v2, E cost);bool removeEdge (int v1, int v2);int getFirstNeighbor (int v);int getNextNeighbor (int v, int w);	
};

邻接表构造函数

template <class T, class E>
Graphlnk<T, E>::Graphlnk (int sz) {
//构造函数：建立一个空的邻接表maxVertices = sz;numVertices = 0;  numEdges = 0;NodeTable = new Vertex<T, E>[maxVertices];		//创建顶点表数组if (NodeTable == NULL) { cerr << "存储分配错！" << endl;  exit(1); }for (int i = 0; i < maxVertices; i++) NodeTable[i].adj = NULL;
};

template <class T, class E>
Graphlnk<T, E>::～Graphlnk() {	
//析构函数：删除一个邻接表for (int i = 0; i < numVertices; i++ ) {Edge<T, E> *p = NodeTable[i].adj;while (p != NULL) {				NodeTable[i].adj = p->link;delete p;  p = NodeTable[i].adj;}} delete [ ]NodeTable;  		     //删除顶点表数组
};template <class T, class E>
int Graphlnk<T, E>::getFirstNeighbor (int v) {
//给出顶点位置为 v 的第一个邻接顶点的位置, 
//如果找不到, 则函数返回-1if (v != -1) {			//顶点v存在Edge<T, E> *p = NodeTable[v].adj;			//对应边链表第一个边结点if (p != NULL) return p->dest;				//存在, 返回第一个邻接顶点}return -1;		//第一个邻接顶点不存在
};template <class T, class E>
int Graphlnk<T, E>::getNextNeighbor (int v, int w) {
//给出顶点v的邻接顶点w的下一个邻接顶点的位置,
//若没有下一个邻接顶点, 则函数返回-1if (v != -1) {				//顶点v存在Edge<T, E> *p = NodeTable[v].adj;while (p != NULL && p->dest != w)p = p->link;if (p != NULL && p->link != NULL) return p->link->dest; 	//返回下一个邻接顶点}return -1; 			//下一邻接顶点不存在
};

 邻接表建立算法！

template<class T , class E>
void Graphlnk<T,E>::CreateNodeTable(void){int n,i,j,m;Edge<T,E> *p;cin>>n;//结点个数for(i=1;i<=n;i++){NodeTable[i].adj=0;cin>>NodeTable[i].data;//输入结点值cin>>m;					//每个结点的邻接点个数for(j=0;j<m;j++){p=new Edge<T,E>;cin>>p->dest;		//建立边结点，输入结点值到dest域p->link=NodeTable[i].adj;//带权图则多加一个权值的输入  cin>>p->cost;NodeTable[i].adj=p;	//头插法建立}}
}