《数据结构》实验六-----邻接矩阵 无向图

实验目的

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

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

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

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

实验内容

1.自己画一无个图（有向或无向均可），使用分别邻接矩阵和邻接表存放图。实现图的输入，并使用两种遍历方法输出图顶点。

图结构如下：

源代码：

头文件MGraph.h：

#ifndef MGraph_H
#define MGraph_H
const int N = 10;
template<class T>
class MGraph
{
public:
	MGraph(T arr[],int n,int e);
	~MGraph(){};
	void BFS(int v);
	void DFS(int v);
private:
	T vertex[N];
	int arc[N][N];
	int vertexNum,arcNum;
};
template<class T>
MGraph<T>::MGraph(T arr[],int e)
{
	int i,j,k;
	vertexNum = n,arcNum = e;
	for (i = 0; i < vertexNum; i++)
		vertex[i] = arr[i];
	for (i = 0; i < vertexNum; i++)
		for (j = 0; j < vertexNum; j++)
			arc[i][j] = 0;
	for (k = 0; k < arcNum; k++)
	{
		cout << "输入两点的编号：n";
		cin >> i;
		cin>> j;
		arc[i][j] = 1; arc[j][i] = 1;
	}
}
template<class T>
void MGraph<T>::DFS(int v)
{
	int j;
	cout << vertex[v];
	visited[v] = 1;
	for (j = 0; j < vertexNum; j++)
		if (arc[v][j] == 1 && visited[j] == 0)
			DFS(j);
}
template<class T>
void MGraph<T>::BFS(int v)
{
	int Q[N];
	int front = -1; 
	int rear = -1;
	cout << vertex[v];
	visited[v] = 1; Q[++rear] = v;
	while (front!=rear)
	{
		v = Q[++front];
		for (int j = 0;j<vertexNum;j++)
			if (arc[v][j] == 1 && visited[j] == 0)
			{
			cout << vertex[j];
			visited[j] = 1;
			Q[++rear] = j;
			}
	}
}
#endif

#include<iostream>
#include<stdlib.h>
#include"MGraph.h"
using namespace std;
char response;
int visited[N]={0};
int main()
{
	char S[]{'A','B','C','D','E','F'};
	MGraph<char> G(S,6,6);
	for (int i = 0; i < N; i++)
		visited[i] = 0;
	cout << "深度优先遍历的序列为：";
	G.DFS(0);
	cout << endl;
	for (int i = 0; i < N; i++)
		visited[i] = 0;
	cout << "广度优先遍历的序列为：";
	G.BFS(0);
	cout << endl;
	system("pause");
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!