1. 基于邻接矩阵存储的有向图，求出度为零的顶点个数

【问题描述】基于邻接矩阵存储的有向图，设计算法求出度为零的顶点个数。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

【输出形式】出度为零的顶点个数。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

【样例输出】

 1

#include <iostream>

using namespace std;

const int MaxSize = 10;
const int MAX = 100000;

template<typename DataType>
class MGraph {
	public:
		MGraph(DataType a[], int n, int e);
		~MGraph() {}
		int CountNodeIsZero();
	private:
		DataType vertex[MaxSize];
		int edge[MaxSize][MaxSize];
		int vertexNum, edgeNum;
};

template<typename DataType>
MGraph<DataType>::MGraph(DataType *a, int n, int e) {
	int i, j, k, value;
	vertexNum = n, edgeNum = e;
	for (i = 0; i < vertexNum; i++)
		vertex[i] = a[i];
	for (i = 0; i < vertexNum; i++)
		for (j = 0; j < vertexNum; j++) {
			if (i == j)
				edge[i][j] = 0;
			else {
				edge[i][j] = MAX;
			}
		}
	for (k = 0; k < edgeNum; k++) {
		char n,m;
		int i,j;
		cin >> n >> m >> value;
		bool config=false;
		for(int s=0; s<vertexNum; s++)
			for(int e=0; e<vertexNum; e++) {
				if(vertex[s]==n&&vertex[e]==m) {
					i=s;
					j=e;
					edge[i][j]=value;
					config= true;
					break;
				}
				if(config)
					break;
			}
	}
}

template<typename DataType>
int MGraph<DataType>::CountNodeIsZero() {
	int ans=0;
	int i,j;
	for(i=0; i<vertexNum; i++) {
		int count=0;
		for (j = 0; j < vertexNum; j++) {
			if (edge[i][j] != MAX && i != j) {
				break;
			} else {
				count++;
			}
		}
		if(count==vertexNum)
			ans++;
	}
	return ans;
}


int main() {
	int verNum,edgeNum;
	cin>>verNum>>edgeNum;
	char a[verNum];
	for(int i=0; i<verNum; i++)
		cin>>a[i];
	MGraph<char> my_graph(a,verNum,edgeNum);
	cout<<my_graph.CountNodeIsZero();
	return 0;
}

2. 基于图的邻接表存储的深度优先遍历

【问题描述】设计算法实现基于邻接表存储的无向图的深度优先遍历。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

最后一行，深度优先遍历的起点。（遍历按照顶点输入的相对顺序）

【输出形式】从起点开始的深度优先遍历序列。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A

【样例输出】

 AFEDCB

#include  <iostream>
#include  <string.h>

using namespace std;

const int MAXSIZE = 100;
int visited[MAXSIZE];
template<class WeightType>
struct EdgeNode {  //定义边表结点
	int adjvex;      //邻接点域
	WeightType weight;
	EdgeNode<WeightType> *next;
};
template<class DataType, class WeightType>
struct VertexNode {
	DataType vertex;
	EdgeNode<WeightType> *firstEdge;
};

template<class DataType, class WeightType>
class ALGraph {
	public:
		ALGraph(DataType a[], int n, int e);

		~ALGraph();

		void DFT(int v);

		int findVertex(DataType ver);    //查找某个顶点在顶点数组中的编号
		int getVertexNum() {
			return vertexNum;
		};

		void show();

	private:
		int vertexNum;
		int edgeNum;
		VertexNode<DataType, WeightType> adjlist[MAXSIZE];//存放顶点表的数组
};

template<class DataType, class WeightType>
ALGraph<DataType, WeightType>::ALGraph(DataType a[], int n, int e) {
	vertexNum = n;
	edgeNum = e;
	for (int i = 0; i < n; ++i) {        //初始化顶点表
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = NULL;
	}
	for (int k = 0; k < e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		EdgeNode<WeightType> *s=new EdgeNode<WeightType>;
		s->adjvex=j;
//        cout<<s->adjvex<<endl;
		s->next=adjlist[i].firstEdge;
		adjlist[i].firstEdge=s;
//        cout<<adjlist[i].firstEdge->adjvex<<endl;
	}
}

template<class DataType, class WeightType>
ALGraph<DataType, WeightType>::~ALGraph() {
	EdgeNode<WeightType> *p = NULL, *q = NULL;
	for (int i = 0; i < vertexNum; ++i) {
		p = adjlist[i].firstEdge;
		while (p->next != NULL) {
			q = p->next;
			delete q;
			p = q;
		}
	}
	q = NULL;
}

template<class DataType, class WeightType>
int ALGraph<DataType, WeightType>::findVertex(DataType ver) {
	for (int i = 0; i < vertexNum; ++i)
		if (adjlist[i].vertex == ver) return i;
	return -1;
}

template<class DataType, class WeightType>
void ALGraph<DataType, WeightType>::DFT(int v) {
	int j;
	EdgeNode<WeightType> *p=NULL;
	cout<<adjlist[v].vertex;
	visited[v]=1;
	p=adjlist[v].firstEdge;
	while(p!= NULL) {
		j=p->adjvex;
		if(visited[j]==0)
			DFT(j);
		p=p->next;
	}
}

template<class DataType, class WeightType>
void ALGraph<DataType, WeightType>::show() {
	for (int i = 0; i < vertexNum; ++i) {
		EdgeNode<WeightType> *p = adjlist[i].firstEdge;
		cout << adjlist[i].vertex << ":  ";
		while (p != NULL) {
			cout << adjlist[p->adjvex].vertex << "  " << p->weight << ";  ";
			p = p->next;
		}
		cout << endl;
	}
}

int main() {
	int n, e;
	cin >> n >> e;
	char a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	ALGraph<char, int> ALG(a, n, e);
	memset(visited, 0, n);
	char startVer;
	cin >> startVer;
	int start = ALG.findVertex(startVer);
	ALG.DFT(start);
	for (int i = 0; i < ALG.getVertexNum(); ++i) {
		if (visited[i] == 0)
			ALG.DFT(i);
	}
	ALG.~ALGraph();
	return 0;
}

3. 判断无图是否是连通图

设计算法判断无向图是否是连通图，如果是，则输出“YES”；否则输出“NO”。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

【输出形式】无向图是否是连通图，如果是，则输出“YES”；否则输出“NO”。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

【样例输出】

 YES

#include  <iostream>
#include  <string.h>
using  namespace  std;

const  int  MAXSIZE=100;
int  visited[MAXSIZE];
int  cont=0;//记录一次深度优先遍历中图顶点的个数

template  <class  DataType,class  WeightType>
class  MGraph {
	public:
		MGraph(DataType  a[],int  n,int  e);
		~MGraph() {}
		void  DFT(int  v);
		int  findVertex(DataType  ver);    //查找某个顶点在顶点数组中的编号
		int  getVertexNum() {
			return  vertexNum;
		};
		void  show();
	private:
		int  vertexNum;
		int  edgeNum;
		DataType  vertex[MAXSIZE];
		WeightType  edge[MAXSIZE][MAXSIZE];
};

template  <class  DataType,class  WeightType>
MGraph<DataType,WeightType>::MGraph(DataType  a[],int  n,int  e) {
	vertexNum  =  n;
	edgeNum  =  e;
	for(int  i=0; i<n; ++i)
		for(int  j=0; j<n; ++j)
			edge[i][j]  =  0;
	for(int  i=0; i<n; ++i)
		vertex[i]  =  a[i];
	for(int  k=0; k<e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		edge[i][j]=value;
		edge[j][i]=value;
	}
}
template  <class  DataType,class  WeightType>
int  MGraph<DataType,WeightType>::findVertex(DataType  ver) {
	for(int  i=0; i<vertexNum; ++i)
		if(vertex[i]  ==  ver)  return  i;
	return  -1;
}
template  <class  DataType,class  WeightType>
void  MGraph<DataType,WeightType>::DFT(int  v) {
	cont++;
	visited[v]=1;
	for(int j=0; j<vertexNum; j++) {
		if(edge[v][j]!=0&&visited[j]==0)
			DFT(j);
	}

}
template  <class  DataType,class  WeightType>
void  MGraph<DataType,WeightType>::show() {
	for(int  i=0; i<vertexNum; ++i) {
		for(int  j=0; j<vertexNum; ++j)
			cout<<edge[i][j]<<"  ";
		cout<<endl;
	}
}
int  main() {
	int  n,e;
	cin>>n>>e;
	char  a[n];
	for(int  i=0; i<n; i++)
		cin>>a[i];
	MGraph<char,int>  MG(a,n,e);
	memset(visited,0,n);
	MG.DFT(0);  //假设从0号顶点开始遍历
	if(cont  ==  MG.getVertexNum())
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return  0;
}

4. 基于邻接矩阵存储，判断顶点之间是否存在路径

【问题描述】基于邻接矩阵存储的有向图，设计算法实现判断顶点vi和顶点vj（i不等于j）之间是否存在路径。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

最后一行，输入顶点vi和顶点vj（i不等于j）。

【输出形式】顶点vi和顶点vj如果存在路径，则输出“YES”；否则输出"NO"。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A E

【样例输出】

 YES

#include <iostream>
#include <string.h>
using namespace std;

const int MAXSIZE=100;
int visited[MAXSIZE];

template <class DataType,class WeightType>
class MGraph {
	public:
		MGraph(DataType a[],int n,int e);
		~MGraph() {}
		void DFT(int v);
		int findVertex(DataType ver);  //鏌ユ壘鏌愪釜椤剁偣鍦ㄩ《鐐规暟缁勪腑鐨勭紪鍙?
		int getVertexNum() {
			return vertexNum;
		};
		void show();
	private:
		int vertexNum;
		int edgeNum;
		DataType vertex[MAXSIZE];
		WeightType edge[MAXSIZE][MAXSIZE];
};

template <class DataType,class WeightType>
MGraph<DataType,WeightType>::MGraph(DataType a[],int n,int e) {
	vertexNum = n;
	edgeNum = e;
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			edge[i][j] = 0;
	for(int i=0; i<n; ++i)
		vertex[i] = a[i];
	for(int k=0; k<e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		edge[i][j]=value;

	}
}
template <class DataType,class WeightType>
int MGraph<DataType,WeightType>::findVertex(DataType ver) {
	for(int i=0; i<vertexNum; ++i)
		if(vertex[i] == ver) return i;
	return -1;
}
template <class DataType,class WeightType>
void MGraph<DataType,WeightType>::DFT(int v) {
	visited[v]=1;
	for(int j=0; j<vertexNum; j++) {
		if(edge[v][j]!=0&&visited[j]==0)
			DFT(j);
	}

}
template <class DataType,class WeightType>
void MGraph<DataType,WeightType>::show() {
	for(int i=0; i<vertexNum; ++i) {
		for(int j=0; j<vertexNum; ++j)
			cout<<edge[i][j]<<" ";
		cout<<endl;
	}
}
int main() {
	int n,e;
	cin>>n>>e;
	char a[n];
	for(int i=0; i<n; i++)
		cin>>a[i];
	MGraph<char,int> MG(a,n,e);
	memset(visited,0,n);
	char vi,vj;
	cin>>vi>>vj;
	MG.DFT(MG.findVertex(vi)); //浠庨《鐐箆i寮€濮嬮亶鍘?
	if(visited[MG.findVertex(vi)]==1&&visited[MG.findVertex(vj)]==1)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;

	return 0;
}

5. 基于图的邻接矩阵存储的广度优先遍历

【问题描述】设计算法实现基于邻接矩阵存储的无向图的广度优先遍历。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

最后一行，广度优先遍历的起点。（遍历按照顶点输入的相对顺序）

【输出形式】从起点开始的广度优先遍历序列。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A

【样例输出】

 ABCFED

【说明】注意非连通图的遍历问题。

#include  <iostream>
#include  <string.h>
using  namespace  std;

const  int  MAXSIZE=100;
int  visited[MAXSIZE];

template  <class  DataType,class  WeightType>
class  MGraph {
	public:
		MGraph(DataType  a[],int  n,int  e);
		~MGraph() {}
		void  BFT(int  v);
		int  findVertex(DataType  ver);    //查找某个顶点在顶点数组中的编号
		int  getVertexNum() {
			return  vertexNum;
		};
		void  show();
	private:
		int  vertexNum;
		int  edgeNum;
		DataType  vertex[MAXSIZE];
		WeightType  edge[MAXSIZE][MAXSIZE];
};

template  <class  DataType,class  WeightType>
MGraph<DataType,WeightType>::MGraph(DataType  a[],int  n,int  e) {
	vertexNum  =  n;
	edgeNum  =  e;
	for(int  i=0; i<n; ++i)
		for(int  j=0; j<n; ++j)
			edge[i][j]  =  0;
	for(int  i=0; i<n; ++i)
		vertex[i]  =  a[i];
	for(int  k=0; k<e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		edge[i][j]=value;
		edge[j][i]=value;
	}
}
template  <class  DataType,class  WeightType>
int  MGraph<DataType,WeightType>::findVertex(DataType  ver) {
	for(int  i=0; i<vertexNum; ++i)
		if(vertex[i]  ==  ver)  return  i;
	return  -1;
}
template  <class  DataType,class  WeightType>
void  MGraph<DataType,WeightType>::BFT(int  v) {
	visited[v]=1;
	int w,j,Q[MAXSIZE];
	int front=-1;
	int rear=-1;
	Q[++front]=v;
	cout<<vertex[v];
	while(front!=rear) {
		w=Q[++front];
		for(j=0; j<vertexNum; j++) {
			if(edge[w][j]!=0&&visited[j]==0) {
				cout<<vertex[j];
				visited[j]=1;
				Q[++rear]=j;
			}
		}
	}

}
template  <class  DataType,class  WeightType>
void  MGraph<DataType,WeightType>::show() {
	for(int  i=0; i<vertexNum; ++i) {
		for(int  j=0; j<vertexNum; ++j)
			cout<<edge[i][j]<<"  ";
		cout<<endl;
	}
}
int  main() {
	int  n,e;
	cin>>n>>e;
	char  a[n];
	for(int  i=0; i<n; i++)
		cin>>a[i];
	MGraph<char,int>  MG(a,n,e);
	memset(visited,0,n);
	char  startVer;
	cin>>startVer;
	int  start  =  MG.findVertex(startVer);
	MG.BFT(start);
	for(int  i=0; i<MG.getVertexNum(); ++i) {
		if(visited[i]  ==  0)
			MG.BFT(i);
	}
	return  0;
}

6. 基于图的邻接矩阵存储的深度优先遍历

一、问题描述

设计算法实现基于邻接矩阵存储的无向图的深度优先遍历。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

最后一行，深度优先遍历的起点。（遍历按照顶点输入的相对顺序）

【输出形式】从起点开始的深度优先遍历序列。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A

【样例输出】

 ABEDCF

【说明】注意非连通图的遍历问题。

#include  <iostream>
#include  <string.h>

using namespace std;

const int MAXSIZE = 100;
int visited[MAXSIZE];

template<class DataType, class WeightType>
class MGraph {
	public:
		MGraph(DataType a[], int n, int e);

		~MGraph() {}

		void DFT(int v);

		int findVertex(DataType ver);    //查找某个顶点在顶点数组中的编号
		int getVertexNum() {
			return vertexNum;
		};

		void show();

	private:
		int vertexNum;
		int edgeNum;
		DataType vertex[MAXSIZE];
		WeightType edge[MAXSIZE][MAXSIZE];
};

template<class DataType, class WeightType>
MGraph<DataType, WeightType>::MGraph(DataType a[], int n, int e) {
	vertexNum = n;
	edgeNum = e;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			edge[i][j] = 0;
	for (int i = 0; i < n; ++i)
		vertex[i] = a[i];
	for (int k = 0; k < e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		edge[i][j]=value;
		edge[j][i]=value;
	}
}

template<class DataType, class WeightType>
int MGraph<DataType, WeightType>::findVertex(DataType ver) {
	for (int i = 0; i < vertexNum; ++i)
		if (vertex[i] == ver) return i;
	return -1;
}

template<class DataType, class WeightType>
void MGraph<DataType, WeightType>::DFT(int v) {
	cout<<vertex[v];
	visited[v]=1;
	for(int j=0; j<vertexNum; j++) {
		if(edge[v][j]!=0&&visited[j]==0)
			DFT(j);
	}

}

template<class DataType, class WeightType>
void MGraph<DataType, WeightType>::show() {
	for (int i = 0; i < vertexNum; ++i) {
		for (int j = 0; j < vertexNum; ++j)
			cout << edge[i][j] << "  ";
		cout << endl;
	}
}

int main() {
	int n, e;
	cin >> n >> e;
	char a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	MGraph<char, int> MG(a, n, e);
	memset(visited, 0, n);
	char startVer;
	cin >> startVer;
	int start = MG.findVertex(startVer);
	MG.DFT(start);
	for(int i=0; i<MG.getVertexNum(); i++) {
		if(visited[i]==0)
			MG.DFT(i);
	}

	return 0;
}

7. 基于图的邻接表存储的广度优先遍历

【问题描述】设计算法实现基于邻接表存储的有向图的广度优先遍历。

【输入形式】第一行输入图的顶点个数verNum和边的个数edgeNum，用于构造图。

第二行顶点信息；接下来edgeNum行，每行描述一条边的信息，即起点、终点，以及边上的整型权值。

最后一行，广度优先遍历的起点。（遍历按照顶点输入的相对顺序）

【输出形式】从起点开始的广度优先遍历序列。

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A

【样例输出】

 AFCBDE

【说明】注意非连通图的遍历问题

#include  <iostream>
#include  <string.h>

using namespace std;

const int MAXSIZE = 100;
int visited[MAXSIZE];

template<class WeightType>
struct EdgeNode {  //定义边表结点
	int adjvex;      //邻接点域
	WeightType weight;
	EdgeNode<WeightType> *next;
};
template<class DataType, class WeightType>
struct VertexNode {
	DataType vertex;
	EdgeNode<WeightType> *firstEdge;
};

template<class DataType, class WeightType>
class ALGraph {
	public:
		ALGraph(DataType a[], int n, int e);

		~ALGraph();

		void BFT(int v);

		int findVertex(DataType ver);    //查找某个顶点在顶点数组中的编号
		int getVertexNum() {
			return vertexNum;
		};

		void show();

	private:
		int vertexNum;
		int edgeNum;
		VertexNode<DataType, WeightType> adjlist[MAXSIZE];//存放顶点表的数组
};

template<class DataType, class WeightType>
ALGraph<DataType, WeightType>::~ALGraph() {
	EdgeNode<WeightType> *p = NULL, *q = NULL;
	for (int i = 0; i < vertexNum; ++i) {
		q = p = adjlist[i].firstEdge;
		while (p != NULL) {
			p = p->next;
			delete q;
			q = p;
		}
	}
	q = NULL;
}

template<class DataType, class WeightType>
ALGraph<DataType, WeightType>::ALGraph(DataType a[], int n, int e) {
	vertexNum = n;
	edgeNum = e;
	for (int i = 0; i < n; ++i) {        //初始化顶点表
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = NULL;
	}
	for (int k = 0; k < e; ++k) {
		char m,n;
		int value;
		cin>>m>>n>>value;
		int i,j;
		i=findVertex(m);
		j=findVertex(n);
		EdgeNode<WeightType> *s=new EdgeNode<WeightType>;
		s->adjvex=j;
		s->weight=value;
		s->next=adjlist[i].firstEdge;
		adjlist[i].firstEdge=s;
	}
}

template<class DataType, class WeightType>
int ALGraph<DataType, WeightType>::findVertex(DataType ver) {
	for (int i = 0; i < vertexNum; ++i)
		if (adjlist[i].vertex == ver) return i;
	return -1;
}

template<class DataType, class WeightType>
void ALGraph<DataType, WeightType>::BFT(int v) {
	int Q[MAXSIZE];
	int rear,front;
	rear=front=-1;
	Q[++rear]=v;
	cout<<adjlist[v].vertex;
	visited[v]=1;
	while(front!=rear) {
		int w = Q[++front];
		EdgeNode<WeightType> *p=adjlist[w].firstEdge;
		while(p!=NULL) {
			int j=p->adjvex;
			if(visited[j]==0) {
				cout<<adjlist[j].vertex;
				visited[j]=1;
				Q[++rear]=j;
			}
			p=p->next;
		}

	}

}

template<class DataType, class WeightType>
void ALGraph<DataType, WeightType>::show() {
	for (int i = 0; i < vertexNum; ++i) {
		EdgeNode<WeightType> *p = adjlist[i].firstEdge;
		cout << adjlist[i].vertex << ":  ";
		while (p != NULL) {
			cout << adjlist[p->adjvex].vertex << "  " << p->weight << ";  ";
			p = p->next;
		}
		cout << endl;
	}
}

int main() {
	int n, e;
	cin >> n >> e;
	char a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	ALGraph<char, int> ALG(a, n, e);
	memset(visited, 0, n);
	char startVer;
	cin >> startVer;
	int start = ALG.findVertex(startVer);
	ALG.BFT(start);
	for (int i = 0; i < ALG.getVertexNum(); ++i) {
		if (visited[i] == 0)
			ALG.BFT(i);
	}
	ALG.~ALGraph();
	return 0;
}

8. 图的最小生成树（Prim）

【问题描述】设G=(V,E)是一个无向连通网,如果该图用邻接矩阵存储，现在需要输出该图最小生成树的代价。

【输入形式】第一行图中顶点个数vexNum以及边个数arcNum。第二行图中各顶点的数据。接下来acrNum行：每行输入边的起点和终点，以及边的权重。最后一行是最小生成树的某个点。

【输出形式】最小生成树的代价

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

A

【样例输出】99

#include  <iostream>
#include  <string.h>

using namespace std;

const int MAXSIZE = 100;
const int MAXVALUE = 0x3f3f3f3f;
int lowcost[MAXSIZE];    //存储最短边
int adjvex[MAXSIZE];      //存储最短边的邻接顶点

template<class DataType, class WeightType>
class MGraph {
	public:
		MGraph(DataType a[], int n, int e);

		~MGraph() {}

		WeightType prim(int v);

		int findVertex(DataType ver);    //查找某个顶点在顶点数组中的编号
		int minEdge(WeightType lowcost[], int len);

		int getVertexNum() {
			return vertexNum;
		};

		void show();

	private:
		int vertexNum;
		int edgeNum;
		DataType vertex[MAXSIZE];
		WeightType edge[MAXSIZE][MAXSIZE];
};

template<class DataType, class WeightType>
MGraph<DataType, WeightType>::MGraph(DataType a[], int n, int e) {
	vertexNum = n;
	edgeNum = e;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			edge[i][j] = MAXVALUE;      //求最小生成树时，需要对比交小值，所以这里初始化为无穷大
		}
	for (int i = 0; i < n; ++i)
		vertex[i] = a[i];
	for (int k = 0; k < e; ++k) {
		DataType startVer, endVer;
		WeightType weight;
		cin >> startVer >> endVer >> weight;
		int i, j;
		i = findVertex(startVer);
		j = findVertex(endVer);
		edge[i][j] = weight;
		edge[j][i] = weight;
	}
}

template<class DataType, class WeightType>
int MGraph<DataType, WeightType>::findVertex(DataType ver) {
	for (int i = 0; i < vertexNum; ++i)
		if (vertex[i] == ver) return i;
	return -1;
}

template<class DataType, class WeightType>
WeightType MGraph<DataType, WeightType>::prim(int v) {
	int minCost = 0;
	int i, j, k;
	for (i = 0; i < vertexNum; i++) { // 初始化辅助数组
		lowcost[i] = edge[v][i];  //最短边的权值
		adjvex[i] = v;    // 最短边的邻接点
	}
	lowcost[v] = 0; // 到自己的权值为0
	for (k = 1; k < vertexNum; k++) {  // 迭代执行n-1次  寻找n-1个点
		j=minEdge(lowcost,vertexNum);   //寻找最短边的邻接点
		minCost+=lowcost[j];
		lowcost[j]=0;   //顶点j加入到集合U
		for(i=0; i<vertexNum; i++) {
			if(edge[i][j]<lowcost[i]) {
				lowcost[i]=edge[i][j];
				adjvex[i]=j;
			}
		}


	}

	return minCost;
}

template<class DataType, class WeightType>
int MGraph<DataType, WeightType>::minEdge(WeightType lowcost[], int len) {
	WeightType minValue = MAXVALUE;
	int minIndex = -1;
	for (int i = 0; i < len; ++i) {
		if (minValue > lowcost[i] && lowcost[i] != 0) {
			minValue = lowcost[i];
			minIndex = i;
		}
	}
	return minIndex;
}

template<class DataType, class WeightType>
void MGraph<DataType, WeightType>::show() {
	for (int i = 0; i < vertexNum; ++i) {
		for (int j = 0; j < vertexNum; ++j) {
			if (edge[i][j] == MAXVALUE) cout << "∞" << "  ";
			else cout << edge[i][j] << "  ";
		}
		cout << endl;
	}
}

int main() {
	int n, e;
	cin >> n >> e;
	char a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	MGraph<char, int> MG(a, n, e);
	char startVer;
	cin >> startVer;
	//MG.show();
	cout << MG.prim(MG.findVertex(startVer)) << endl;
	return 0;
}

9. 图的最小生成树（Kruskal）

【问题描述】设G=(V,E)是一个无向连通网,如果该图用邻接矩阵存储，现在需要输出该图最小生成树的代价。

【输入形式】第一行图中顶点个数vexNum以及边个数arcNum。第二行图中各顶点的数据。接下来acrNum行：每行输入边的起点和终点，以及边的权重。

【输出形式】最小生成树的代价

【样例输入】

6 9

A B C D E F

A B 34

A C 46

A F 19

B E 12

C D 17

C F 25

D E 38

D F 25

E F 26

【样例输出】99

#include  <iostream>

using namespace std;

const int MAXSIZE = 100;
template<class WeightType>
struct EdgeType {
	int from, to;
	WeightType weight;
};


template<class DataType, class WeightType>
class EdgeGraph {
	public:
		EdgeGraph(DataType a[], int n, int e);

		~EdgeGraph() {}

		WeightType kruskal();

		int findVertex(DataType ver);    //查找某个顶点在顶点数组中的编号
		int FindRoot(int parent[], int v);

		void show();

	private:
		int vertexNum;
		int edgeNum;
		DataType vertex[MAXSIZE];
		EdgeType<WeightType> edge[MAXSIZE];
};

template<class DataType, class WeightType>
EdgeGraph<DataType, WeightType>::EdgeGraph(DataType a[], int n, int e) {
	vertexNum = n;
	edgeNum = e;
	for (int i = 0; i < n; ++i)
		vertex[i] = a[i];
	for (int k = 0; k < edgeNum; ++k) {
		char m, n;
		int value;
		cin >> m >> n >> value;
		int i = findVertex(m);
		int j = findVertex(n);
		edge[k].weight = value;
		edge[k].from = i;
		edge[k].to = j;
	}

	//按照边的权值大小排序
	for (int i = 0; i < edgeNum - 1; ++i)
		for (int j = 0; j < edgeNum - 1 - i; ++j)
			if (edge[j].weight > edge[j + 1].weight) {
				EdgeType<WeightType> tmp = edge[j];
				edge[j] = edge[j + 1];
				edge[j + 1] = tmp;
			}
}

template<class DataType, class WeightType>
int EdgeGraph<DataType, WeightType>::findVertex(DataType ver) {
	for (int i = 0; i < vertexNum; ++i)
		if (vertex[i] == ver) return i;
	return -1;

}

template<class DataType, class WeightType>
WeightType EdgeGraph<DataType, WeightType>::kruskal() {
	WeightType minCost = 0;
	int num = 0, i, vex1, vex2;
	int parent[vertexNum];
	for (i = 0; i < vertexNum; i++)
		parent[i] = -1;
	for (num = 0, i = 0; num < vertexNum - 1; i++) {
		vex1 = FindRoot(parent, edge[i].from);
		vex2 = FindRoot(parent, edge[i].to);
		if (vex1 != vex2) {
			parent[vex1] = vex2;
			minCost += edge[i].weight;
		}
		num++;
	}

	return minCost;
}

template<class DataType, class WeightType>
int EdgeGraph<DataType, WeightType>::FindRoot(int parent[], int v) {
	int t = v;
	while (parent[t] != -1) {
		t = parent[t];
	}
	return t;
}

template<class DataType, class WeightType>
void EdgeGraph<DataType, WeightType>::show() {
	for (int i = 0; i < edgeNum; ++i)
		cout << "(" << vertex[edge[i].from] << "," << vertex[edge[i].to] << ")  :" << edge[i].weight << endl;
}

int main() {
	int n, e;
	cin >> n >> e;
	char a[n];
	for (int i = 0; i < n; i++)
		cin >> a[i];
	EdgeGraph<char, int> EG(a, n, e);
	//EG.show();
	cout << EG.kruskal() << endl;
	return 0;
}

10. 判断有向图中是否存在回路

【问题描述】设G=(V,E)是一个有向图,如果该图用邻接矩阵存储，现在需要判断该有向图中是否存在回路。

【输入形式】第一行图中顶点个数vexNum以及边个数edgeNum。第二行图中各顶点的数据。接下来edgeNum行：每行依次输入边的起点和终点。

【输出形式】如果该有向图中存在回路，则输出“YES”；否则输出“NO”。

【样例输入】

6 9

A B C D E F

A B

A C

A F

B E

C D

C F

D E

D F

E F

【样例输出】NO

#include  <iostream>
#include  <string.h>
using  namespace  std;

const  int  MAXSIZE=100;

template  <class  DataType,class  WeightType>
class  MGraph {
	public:
		MGraph(DataType  a[],int  n,int  e);
		~MGraph() {}
		int  TopSort(  );
		int  findVertex(DataType  ver);    //查找某个顶点在顶点数组中的编号
		int  getVertexNum() {
			return  vertexNum;
		};
		void  show();
	private:
		int  vertexNum;
		int  edgeNum;
		DataType  vertex[MAXSIZE];
		WeightType  edge[MAXSIZE][MAXSIZE];
};

template  <class  DataType,class  WeightType>
MGraph<DataType,WeightType>::MGraph(DataType  a[],int  n,int  e) {
	vertexNum  =  n;
	edgeNum  =  e;
	for(int  i=0; i<n; ++i)
		for(int  j=0; j<n; ++j)
			edge[i][j]  =  0;
	for(int  i=0; i<n; ++i)
		vertex[i]  =  a[i];
	for(int  k=0; k<e; ++k) {
		DataType  startVer,endVer;
		cin>>startVer>>endVer;
		int  i  =  findVertex(startVer);
		int  j  =  findVertex(endVer);
		edge[i][j]  =1;    //构造有向图
	}
}
template  <class  DataType,class  WeightType>
int  MGraph<DataType,WeightType>::findVertex(DataType  ver) {
	for(int  i=0; i<vertexNum; ++i)
		if(vertex[i]  ==  ver)  return  i;
	return  -1;
}
template  <class  DataType,class  WeightType>
int  MGraph<DataType,WeightType>::TopSort(  ) {
	int  cont=0;  //cont统计拓扑序列中顶点的个数

	int in[vertexNum]= {0},i,j;
	int S[vertexNum],top=-1;

	for( j=0; j<vertexNum; j++) {
		in[j]=0;
		for( i=0; i<vertexNum; i++)
			if(edge[i][j]!=0)in[j]++;
		if(in[j]==0)S[++top]=j;
	}

//        for(j=0;j<vertexNum;j++)cout<<in[j]<<" ";
//        cout<<endl;

	while(top!=-1) {
		i=S[top--];
		cont++;
		for( j=0; j<vertexNum; j++) {
			if(edge[i][j]!=0) {
				in[j]--;
				if(in[j]==0)S[++top]=j;
			}
		}
	}

	return  cont;
}
template  <class  DataType,class  WeightType>
void  MGraph<DataType,WeightType>::show() {
	for(int  i=0; i<vertexNum; ++i) {
		for(int  j=0; j<vertexNum; ++j)
			cout<<edge[i][j]<<"  ";
		cout<<endl;
	}
}
int  main() {
	int  n,e;
	cin>>n>>e;
	char  a[n];
	for(int  i=0; i<n; i++)
		cin>>a[i];
	MGraph<char,int>  MG(a,n,e);
	if(MG.getVertexNum()  ==  MG.TopSort())
		cout<<"NO"<<endl;
	else
		cout<<"YES"<<endl;
	return  0;
}

结语

如果你发现文章有什么问题，欢迎留言指正。
如果你觉得这篇文章还可以，别忘记点个赞加个关注再走哦。
如果你不嫌弃，还可以关注微信公众号———梦码城（持续更新中）。
梦码在这里感激不尽！！