图的基本操作及BFS与DFS的实现以及飞机换乘问题_dfs算法换乘问题

运用STL中的queue队列实现BFS。

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
enum ResultCode { Underflow, Duplicate, Failure, Success, NotPresent };
template<class T>
class Graph
{
public:
	virtual ResultCode Insert(int u, int v, T&w) = 0;
	virtual ResultCode Remove(int u, int v) = 0;
	virtual bool Exist(int u, int v)const = 0;
protected:
	int n, e;
};
template<class T>
class MGraph :public Graph<T>    //邻接矩阵类
{
public:
	MGraph(int mSize, const T& noedg);
	~MGraph();
	ResultCode Insert(int u, int v, T&w);
	ResultCode Remove(int u, int v);
	bool Exist(int u, int v)const;
	void DFS();
	void BFS();
protected:
	T **a;
	T noEdge;
	void DFS(int v, bool *visited);
	void BFS(int v, bool *visited);
};
 
template<class T>
void MGraph<T>::DFS()   //深度优先遍历
{
	bool *visited = new bool[n];
	for (int i = 0; i<n; i++)
		visited[i] = false;
	for (int i = 0; i<n; i++)
		if (!visited[i])
			DFS(i, visited);
	delete[]visited;
	cout << endl;
}
template<class T>
void MGraph<T>::DFS(int v, bool *visited)
{
	visited[v] = true;
	cout << " " << v;
	for (int i = 0; i < n; i++)
		if (a[v][i] != noEdge&&a[v][i] != 0 && !visited[i])
			DFS(i, visited);
}
template<class T>
void MGraph<T>::BFS()   //宽度游先遍历
{
	bool *visited = new bool[n];
	for (int i = 0; i<n; i++)
		visited[i] = false;
	for (int i = 0; i<n; i++)
		if (!visited[i])
			BFS(i, visited);
	delete[]visited;
	cout << endl;
}
template<class T>
void MGraph<T>::BFS(int v, bool *visited)
{
	visited[v] = true;
	cout << " " << v;
	queue<int> q;
	q.push(v);
	while (!q.empty())
	{
		v=q.front();
		q.pop();
		for (int i = 0; i < n; i++)
		{
			if (a[v][i] != noEdge&&a[v][i] != 0 && !visited[i])
			{
				visited[i] = true;
				cout << " " << i;
				q.push(i);
			}
		}
	}
}
 
template <class T>
MGraph<T>::MGraph(int mSize, const T&noedg)  //构造函数
{
	n = mSize;
	e = 0;
	noEdge = noedg;
	a = new T*[n];
	for (int i = 0; i<n; i++)
	{
		a[i] = new T[n];
		for (int j = 0; j<n; j++)
			a[i][j] = noEdge;
		a[i][i] = 0;
	}
}
template <class T>
MGraph<T>::~MGraph()   //析构函数
{
	for (int i = 0; i<n; i++)
		delete[]a[i];
	delete[]a;
}
template <class T>
ResultCode MGraph<T>::Insert(int u, int v, T&w)    //插入函数
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v)
		return Failure;
	if (a[u][v] != noEdge)
		return Duplicate;
	a[u][v] = w;
	e++;
	return Success;
}
template <class T>
ResultCode MGraph<T>::Remove(int u, int v)    //删除函数
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v)
		return Failure;
	if (a[u][v] == noEdge)
		return NotPresent;
	a[u][v] = noEdge;
	e--;
	return Success;
}
template<class T>
bool MGraph<T>::Exist(int u, int v)const    //判断边是否存在
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v || a[u][v] == noEdge)
		return false;
	return true;
}
template<class T>   //结点类
class ENode
{
public:
	ENode() { nextArc = NULL; }
	ENode(int vertex, T weight, ENode *next)
	{
		adjVex = vertex;
		w = weight;
		nextArc = next;
	}
	int adjVex;
	T w;
	ENode * nextArc;
};
template <class T>
class LGraph :public Graph<T>   //邻接表类
{
public:
	LGraph(int mSize);
	~LGraph();
	ResultCode Insert(int u, int v, T&w);
	ResultCode Remove(int u, int v);
	bool Exist(int u, int v)const;
protected:
	ENode<T> **a;
};
template <class T>
LGraph<T>::LGraph(int mSize)   //构造函数
{
	n = mSize;
	e = 0;
	a = new ENode<T> *[n];
	for (int i = 0; i<n; i++)
		a[i] = NULL;
}
template <class T>
LGraph<T>::~LGraph()   //析构函数
{
	ENode<T> *p, *q;
	for (int i = 0; i<n; i++)
	{
		p = a[i];
		q = p;
		while (p)
		{
			p = p->nextArc;
			delete q;
			q = p;
		}
	}
	delete[]a;
}
template <class T>
bool LGraph<T>::Exist(int u, int v)const   //判断边是否存在
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v)
		return false;
	ENode<T>*p = a[u];
	while (p&&p->adjVex != v)
		p = p->nextArc;
	if (!p)
		return false;
	else return true;
}
template <class T>
ResultCode LGraph<T>::Insert(int u, int v, T&w)   //插入函数
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v)
		return Failure;
	if (Exist(u, v))
		return Duplicate;
	ENode<T>*p = new ENode<T>(v, w, a[u]);
	a[u] = p;
	e++;
	return Success;
}
template <class T>
ResultCode LGraph<T>::Remove(int u, int v)   //删除函数
{
	if (u<0 || v<0 || u>n - 1 || v>n - 1 || u == v)
		return Failure;
	ENode<T> *p = a[u], *q;
	q = NULL;
	while (p&&p->adjVex != v)
	{
		q = p;
		p = p->nextArc;
	}
	if (!p)
		return NotPresent;
	if (q)
		q->nextArc = p->nextArc;
	else
		a[u] = p->nextArc;
	delete p;
	e--;
	return Success;
}
int main()  //主函数，测试上述运算
{
	int m, n;    //m代表元素个数，n代表边的条数
	cout << "请按顺序依次输入元素的个数和边数" << endl;
	cin >> m >> n;
	MGraph<int> A(m, -1);
	LGraph<int> B(m);
	int a, b, c;
	for (int i = 0; i<n; i++)
	{
		cout << "按顺序输入边和权值（例如 1 2 3）" << endl;
		cin >> a >> b >> c;
		A.Insert(a, b, c);
		B.Insert(a, b, c);
	}
	cout << "深度优先遍历如下：" << endl;
	A.DFS();
	cout << "宽度优先遍历如下：" << endl;
	A.BFS();
	cout << endl;
	char mm;
	cout << "输入要进行的选项" << endl << "1.查找边" << endl << "2.删除边" << endl << "3.遍历" << endl << "0.退出" << endl;
	while (cin >> mm)
	{
		getchar();
		switch (mm)
		{
		case '1':
			cout << "请输入要搜索的边: ";
			int c, d;
			cin >> c >> d;
			if (A.Exist(c, d))
				cout << "邻接矩阵中该边存在!" << endl;
			else
				cout << "邻接矩阵中该边不存在!" << endl;
			if (B.Exist(c, d))
				cout << "邻接表中该边存在!" << endl;
			else
				cout << "邻接表中该边不存在!" << endl;
			break;
		case '2':
			cout << "请输入要删除的边: ";
			int e, f;
			cin >> e >> f;
			if (A.Remove(e, f) == Success)
				cout << "邻接矩阵中删除该边成功!" << endl;
			else if (A.Remove(e, f) == NotPresent)
				cout << "邻接矩阵中该边不存在!" << endl;
			else
				cout << "输入错误!" << endl;
			if (B.Remove(e, f) == Success)
				cout << "邻接表中删除该边成功!" << endl;
			else if (B.Remove(e, f) == NotPresent)
				cout << "邻接表中该边不存在!" << endl;
			else
				cout << "邻接表中输入错误!" << endl;
			break;
		case '3':
			cout << "深度优先遍历如下：" << endl;
			A.DFS();
			cout << "宽度优先遍历如下：" << endl;
			A.BFS();
			break;
		case '0':
			exit(0);
		default:
			continue;
		}
	}
	return 0;
}

飞机问题主要运用弗罗伊德算法然后改变了主函数部分代码如下：

template<class T>
void MGraph<T>::Floyd(T **d, int **path)		//弗罗伊德算法
{
	int i, k, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
		{
			d[i][j] = a[i][j];
			if (i != j&&a[i][j]<INFTY)
				path[i][j] = i;
			else
				path[i][j] = -1;
		}
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n;j++)
				if (d[i][k] + d[k][j] < d[i][j])
				{
					d[i][j] = d[i][k] + d[k][j];
					path[i][j] = path[k][j];
				}
}

相应的主函数

int main()
{
	int n, m;//n个城市，m条航线
	const int weight=1;
	cout << "输入城市个数n以及航线条数m" << endl;
	cin >> n >> m;
	int **d = new int*[n], **path = new int*[n];
	for (int k = 0; k < n; k++)
	{
		d[k] = new int[n];
		path[k] = new int[n];
	}
	MGraph<int> A(n, INFTY);
	for (int i = 0; i < m; i++)
	{
		int ss, qq;
		cout << "输入航线即两个城市" << endl;
		cin >> ss >> qq;
		A.Insert(ss, qq, weight);
	}
	A.Floyd(d, path);
	int x, y;
	cout << "请输入你要查询的起点城市和终点城市" << endl;
	cin >> x >> y;
	cout << "换乘次数最少的路线为：" << endl;
	int ans[1000],k=0;
	ans[k] = y;
	do
	{
		int temp = path[x][ans[k]];
		ans[++k] = temp;
	} while (path[x][ans[k-1]] != x);
	do
		cout << " " << ans[k] << endl;
	while (k--);
	for (int k = 0; k < n; k++)
	{
		delete[]d[k];
		delete[]path[k];
	}
	delete[]d;
	delete[]path;
	return 0;
}