实验六 图的构建与遍历

邻接矩阵

#include <iostream>
using namespace std;

const int MaxSize = 10;
int visited[MaxSize] = { 0 };

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

template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e) {
    int i, j, k;
    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++)
            edge[i][j] = 0;
    for (k = 0; k < edgeNum; k++) {
        cout << "请输入边依附的两个顶点的编号：";
        cin >> i >> j;
        edge[i][j] = 1; edge[j][i] = 1;
    }
}

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

template <class DataType>
void MGraph<DataType>::BFTraverse(int v) {
    int w, j, Q[MaxSize];
    int front = -1, rear = -1;
    cout << vertex[v]; visited[v] = 1; Q[++rear] = v;
    while (front != rear) {
        w = Q[++front];
        for (j = 0; j < vertexNum; j++)
            if (edge[w][j] == 1 && visited[j] == 0) {
                cout << vertex[j]; visited[j] = 1; Q[++rear] = j;
            }
    }
}

int main() {
    int i;
    string ch[] = { "V1","V2","V3","V4","V5" };
    MGraph<string> MG{ ch, 5, 6 };
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "\n深度优先遍历序列是：" << endl;
    MG.DFTraverse(0);
    for (i = 0; i < MaxSize; i++)
        visited[i] = 0;
    cout << "\n广度优先遍历序列是：" << endl;
    MG.BFTraverse(0);
    return 0;
}

邻接表

#include <iostream>
using namespace std;

struct EdgeNode		//定义边表结点
{
	int adjvex;	//邻接点域
	EdgeNode* next;
};

template<class DataType>
struct VertexNode		//定义顶点表结点
{
	DataType vertex;
	EdgeNode* firstEdge;
};

const int MaxSize = 10;		//图的最多顶点数
int visited[MaxSize] = { 0 };

template <class DataType>
class ALGraph
{
public:
	ALGraph(DataType a[], int n, int e);			//构造函数
	~ALGraph();									//析构函数
	void DFTraverse(int v);					//深度
	void BEFraverse(int v);					//广度
private:
	VertexNode<DataType> adjlist[MaxSize];	//存放顶点表
	int vertexNum, edgeNum;					//图的顶点数和边数
};

template<class DataType>
ALGraph<DataType>::ALGraph(DataType a[], int n, int e)
{
	int i, j, k;
	EdgeNode* s = nullptr;
	vertexNum = m;
	edgeNum = e;
	for (int i = 0; i < vertexNum; i++)
	{
		adjlist[i].vertex = a[i];
		adjlist[i].firstEdge = NULL;
	}
	for (k = 0; k < edgeNum; k++)	//依次输入每一条边
	{
		cout << "输入边所依付的两个顶点的编号：";
		cin >> i >> j;
		s = new EdgeNode;
		s->adjvex = j;
		s->next = adjlist[i].firstEdge;
		adjlist[i].firstEdge = s;
	}
}

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

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


int main()
{
	//测试数据是图6-20(a)，边是(0 1)(0 3)(0 4)(1 2)(2 4)(3 2)(3 4)
	string ch[] = { 'V1','V2','V3','V4','V5' };
	int i;
	ALGraph<char> ALG(ch, 5, 7);               //建立具有5个顶点6条边的有向图
	for (i = 0; i < MaxSize; i++)
		visited[i] = 0;
	cout << "深度优先遍历序列是：";
	ALG.DFTraverse(0);                       //从顶点0出发进行深度优先遍历
	for (i = 0; i < MaxSize; i++)
		visited[i] = 0;
	cout << "广度优先遍历序列是：";
	ALG.BFTraverse(0);                      //从顶点0出发进行广度优先遍历
	return 0;
}