《数据结构》实验六-----邻接表

图的逻辑结构如下：

源代码：

头文件ALGraph.h：

#ifndef ALGraph_H
#define ALGraoh_H
#include<stdlib.h>
const int N = 10;
int visited[N] {0};
struct Arcnode
{
	int adjvex;
	Arcnode *next;
};
template<class T>
struct Vertexnode
{
	T vertex;
	Arcnode *firstedge;
};
template<typename T>
class ALGraph
{
public:
	ALGraph(T a[],int num,int edge);
	~ALGraph()
	{  
		system("pause");
	}
	void BFS(int v);
	void DFS(int v);
private:
	Vertexnode<T> adjlist[N];
	int vertexnum,arcnum;
};
template<class T>
ALGraph<T>::ALGraph(T a[],int edge)
{
	Arcnode *s;
	int i,j,k;
	vertexnum = num;
	arcnum = edge;
	for (i = 0; i < vertexnum; i++)
	{
		adjlist[i].vertex = a[i];
		adjlist[i].firstedge = NULL;
	}
	for (k = 0; k < arcnum; k++)
	{
		cout << "请输入两个相连顶点的编号:";
		cin >> i;
		cin >> j;
		s = new Arcnode;
		s->adjvex = j;
		s->next = adjlist[i].firstedge;
		adjlist[i].firstedge = s;
	}
}
template<class T>
void ALGraph<T>::BFS(int v)
{
	Arcnode *p = nullptr;
	int Q[N];
	int front,rear;
	front = -1; rear = -1;
	cout << adjlist[v].vertex;
	Q[++rear] = v;
	while (front!=rear)
	{
		v = Q[++front];
		p = adjlist[v].firstedge;
		while (p != nullptr)
		{
			int j;
			j = p->adjvex;
			if (visited[j] == 0)
			{
				cout << adjlist[j].vertex;
				visited[j] = 1;
				Q[++rear] = j;
			}
			p = p->next;
		}
	}
}
template<class T>
void ALGraph<T>::DFS(int v)
{
	Arcnode *p = nullptr;
	int j;
	cout << adjlist[v].vertex;
	visited[v] = 1;
	p = adjlist[v].firstedge;
	while (p != nullptr)
	{
		j = p->adjvex;
		if (visited[j] == 0)
			DFS(j);
		p = p->next;
	}
}

template<class T>
void showBFS(ALGraph<T> ALG)
{
	cout << "广度优先遍历结果为：";
	ALG.BFS(0);
	cout << endl;
}
template<class T>
void showDFS(ALGraph<T> ALG_0)
{
	cout << "深度优先遍历结果为：";
	ALG_0.DFS(0);
	cout << endl;
}
#endif

#include<iostream>
#include"ALGraph.h"
using namespace std;
int main()
{
	char S[] {'A','B','C','D','E','F'};
	int i;
	ALGraph<char> G(S,6,6);
	for (i = 0; i < N; i++)
		visited[i]=0;
	showBFS(G);
	for (i = 0; i < N; i++)
		visited[i] = 0;
	showDFS(G);
	cout << endl;
	return 0;
}

（编辑：李大同）

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