《数据结构》实验六： 图的实验

一．.实验目的

巩固图的相关知识。掌握图的主要存储方法和遍历方法，学会运用图的知识解决实际问题。

1.图的逻辑结构和存储方法，清楚掌握图的遍历操作。

2.掌握图的存储方法的实现代码。

3.学习图的相关知识来解决实际问题。

二．实验时间

准备时间为第13周到第14周，不给具体集中实验时间。在第十五周完成。

三．.实验内容

使用邻接矩阵来存储图

构造的图为：

代码为：

#include<iostream>
using namespace std;
const int Maxsize=10;
template<class T>
class Graph
{
	public:
		Graph(T a[ ],int n,int e);
		~Graph(){}
		void shendu(int v);
		void guangdu(int v);
	private:
		T vertex[Maxsize];
		int arc[Maxsize][Maxsize];
		int vertexnum,arcnum;
};
template<class T>
Graph<T>::Graph(T a[ ],int e)
{
	int i; int j; int k;
	vertexnum=n;arcnum=e;
	for(i=0;i<vertexnum;i++)
		vertex[i]=a[i];
	for(i=0;i<vertexnum;i++)
		for(j=0;j<vertexnum;j++)
			arc[i][j]=0;
		for(k=0;k<arcnum;k++)
		{
			cout<<"请输入边的两个顶点的序号：";
				cin>>i>>j;
			arc[i][j]=1;
			arc[j][i]=1;
		}
}
template<class T>
void Graph<T>::shendu(int v)
{
	int j;
	cout<<vertex[v];
	visited[v]=1;
	for(j=0;j<vertexnum;j++)
		if(arc[v][j]==1&&visited[j]==0)
			shendu(j);
}
template<class T>
void Graph<T>::guangdu(int v)
{
	int d[Maxsize]; int j;
	int front=-1,rear=-1;
	cout<<vertex[v]; visited[v]=1; d[++rear]=v;
	while(front!=rear)
	{
		v=d[++front];
		for(j=0;j<vertexnum;j++)
			if(arc[v][j]==1&&visited[j]==0)
			{
				cout<<vertex[j];
				visited[j]=1;
				d[++rear]=j;
			}
	}
}
int visited[Maxsize]={0};
int main()
{
	int n,e; int i;
	char ch[Maxsize];
	for(i=0;i<Maxsize;i++)
		visited[i]=0;
	cout<<"请输入顶点数和边数：";
		cin>>n>>e;
	cout<<endl<<"请输入顶点:";
	for(i=0;i<n;i++)
		cin>>ch[i];
	Graph<char> g(ch,n,e);
	cout<<"深度优先遍历的序列为：";
	g.shendu(0);
	cout<<endl;
	for(i=0;i<Maxsize;i++)
		visited[i]=0;
	cout<<"广度优先遍历的序列为：";
	g.guangdu(0);
	cout<<endl;
	return 0;
}