1.实验题目
1.【功能1】建立一个无向图。
2.【功能2】按深度优先遍历该无向图，输出遍历序列。
3.【功能3】按广度优先遍历该无向图，输出遍历序列。
2.实验要求
1、无向图以邻接矩阵或邻接表作为存储结构
2、主程序测试数据
3.算法思路
1.类的设计
这次实验可以设计出一个邻接表作为图的存储结构。因为题目要求图的边没有权值，所以，我们可以对课本上的邻接表作一些适当简化。在设计图的边类adjlistnetworkarc类时，可以去掉边权域，仅保留顶点域和指针域。在设计图类adjlistdirnetwork时，可以去掉对无穷大的值的定义。定义这两个类模板时，少了权值这一参数，仅保留数据域元素类型这一参数。但是，定义顶点结点adjlistnetwokvex时，无向图与带权有向图在形式上没有区别。
2.输入图
输入图分为3步：输入顶点个数，输入各个顶点的数据域，输入边。
输入顶点的个数后，完成了对图、顶点、边的初始化和构造。
输入边的同时，调用adjlistdirnetwork中添加边的函数，对V1结点添加(V1,V2)的边，对V2结点添加(V2,V1)的边。
可利用#键，提示输入已完成。在输入过程中，适当利用cin语句读取掉不需要的左括号、右括号、逗号等，并将数字按字符读取完成后转换回对应数字。
输入边完成后，可以自行定义一个输出功能，显示各个结点自己的数据域，并显示出与其邻接的所有结点。这一过程封装在adjlistdirnetwork类的函数中。
3.深度优先遍历
对于非连通图，先对每个顶点设置未访问标志，再从每一个未被访问的顶点出发进行深度优先搜索。深度优先搜索时，访问结点v，标记该结点已经被访问。再取邻接表上v的第一个邻接结点w。若顶点w不存在，退回到点v，结束。若顶点w存在且未被访问，则访问该结点。访问v在邻接表上下一个未被访问的结点。
4.广度优先遍历
对于非连通图，先对每个顶点设置未访问标志，再从每一个未被访问的顶点开始进行广度优先搜索。广度优先搜索时，先访问结点v，标记v已经被访问。将v入队列。当队列为空时结束。否则，队头顶点出队列v，取顶点v的第一个邻接顶点w，若w不存在，则将队头顶点出队列v。否则，若顶点w未被访问，则访问顶点w，标记w已被访问，将w入队列。否则，访问顶点v在邻接表上下一个未被访问的结点。
4.输出演示
1.先输入结点个数。
2.在结点个数输入完成后，根据提示可输入各个结点的数据域
3.在将各个结点数据域输入后，可以(a,b)的形式输入弧，将顶点a与顶点b连结在一起。
4.以#表示输入终止。此时，我们可以将这张图以邻接表的形式存储，看到其结点与结点之间的逻辑结构。
5.我们可以看到图的深度优先遍历序列与广度优先遍历序列
5.源代码
adjlistdirnetwork.h
#pragma once #define DEFAULT_SIZE 100 #define DEFAULT_INFI 32767 #define status int #define UNVISITED 0 #define VISITED 1 #include"adjlistnetworkvex.h" #include"adjlistnetworkarc.h" #include<iostream> #include"seqqueue.h" #include<stdio.h> using namespace std; template<class ElemType> class adjlistdirnetwork { protected: mutable status* tag; int vexnum, vexmaxnum, arcnum; adjlistnetworkvex<ElemType>* vextable; public: /* adjlistdirnetwork(ElemType es[], int vertexNum, int vertexMaxNum = DEFAULT_SIZE) { if (vertexMaxNum < 0) cerr<<"允许的顶点的最大数目不能为负！"; if (vertexMaxNum < vertexNum) cerr<<"顶点数目不能大于允许的顶点的最大数目！"; vexnum = vertexNum; vexmaxnum = vertexMaxNum; arcnum = 0; tag = new status[vexmaxnum]; vextable = new adjlistnetworkvex<ElemType>[vexmaxnum]; for (int v = 0; v < vexnum; v++) { tag[v] = UNVISITED; vextable[v].data = es[v]; vextable[v].firstarc = NULL; } } */ ~adjlistdirnetwork() {//析构函数 delete [] vextable; delete []tag; } adjlistdirnetwork(int vertexMaxNum=DEFAULT_SIZE) {//默认构造函数 if (vertexMaxNum < 0)//抛出异常 cerr<<"允许顶点的最大数目不能为负！"; vexnum = 0; vexmaxnum = vertexMaxNum; arcnum = 0; tag = new status[vexmaxnum]; vextable = new adjlistnetworkvex<ElemType>[vexmaxnum];//构造顶点 for (int v = 0; v < vexmaxnum; v++) tag[v] = UNVISITED;//将是否访问的标志初始化 } void setvexnum(int val) { vexnum = val; } void insertarc(int v1, int v2) { if (v1 < 0 || v1 >= vexnum) cerr << "v1不合法！"; if (v2 < 0 || v2 >= vexnum) cerr << "v2不合法！"; if (v1 == v2) cerr << "v1不能等于v2！";//判断不合法情况 adjlistnetworkarc* p, * q; p = vextable[v1].getfirstarc(); vextable[v1].setfirstarc(v2,p);//v1顶点的邻接表里连一条(v1,v2)的边 arcnum++; q = vextable[v2].getfirstarc(); vextable[v2].setfirstarc(v1,q);//v2顶点的邻接表里连一条(v2,v1)的边 arcnum++; } adjlistnetworkvex<ElemType>* getvex(int i) { return &vextable[i];//因为类被封装了找到这个图对应的顶点表 } void show() {//将图以邻接表的形式展示 adjlistnetworkarc* p; for (int i = 0; i < vexnum; i++) { cout << vextable[i].getdata(); p = vextable[i].getfirstarc(); while (p != NULL) { cout<<"("<<vextable[i].getdata()<<"," <<vextable[p->getadjvex()].getdata()<<")"; p = p->getnextarc(); } cout << endl; } } void settag(int v, status _tag) { tag[v] = _tag;//改变v顶点的标志 } void DFS(int v) {//深度优先搜索 ElemType e; settag(v, VISITED); cout<<vextable[v].getdata(); adjlistnetworkarc* w=vextable[v].getfirstarc(); while(w!=NULL){ if (tag[w->getadjvex()] == UNVISITED) DFS(w->getadjvex()); w = w->getnextarc(); } } void DFSTraverse() {//完整的深度优先遍历过程 int v; for (v = 0; v < vexnum; v++) settag(v, UNVISITED); for (v = 0; v < vexnum; v++) if (tag[v] == UNVISITED) DFS(v); } void resettag() {//在进行另一次遍历之前，先把是否访问的标记重置 for (int i = 0; i < vexnum; i++) tag[i] = UNVISITED; } void BFS(int v) {//广度优先搜索 seqqueue<int> q; int u; adjlistnetworkarc* w=NULL; settag(v, VISITED); cout << vextable[v].getdata(); q.enqueue(v); while (!q.isempty()) { q.delqueue(u); w = vextable[u].getfirstarc(); while (w != NULL) { if (tag[w->getadjvex()] == UNVISITED) { cout << vextable[w->getadjvex()].getdata(); settag(w->getadjvex(), VISITED); q.enqueue(w->getadjvex()); } w = w->getnextarc(); } } } void BFSTraverse() {//完整的广度优先遍历 int v; for (v = 0; v < vexnum; v++) settag(v, UNVISITED); for (v = 0; v < vexnum; v++) if (tag[v] == UNVISITED) BFS(v); } };
adjlistnetworkarc.h
#pragma once #include"Windows.h" struct adjlistnetworkarc { protected: int adjvex; adjlistnetworkarc* nextarc; public: int getadjvex() { return adjvex; } adjlistnetworkarc* getnextarc() { return nextarc; } void setnextarc(adjlistnetworkarc* _nextarc) { nextarc = _nextarc; } //因为边类被封装了，所以要写getter/setter adjlistnetworkarc() {//默认的无参构造函数 adjvex = -1; nextarc = NULL; } adjlistnetworkarc(int v, adjlistnetworkarc* next = NULL) { adjvex = v;//边的一段指向顶点v nextarc = next; } };
adjlistnetworkvex.h
#pragma once #define DEFAULT_SIZE 100 #define status int #include"adjlistnetworkarc.h" #include<iostream> using namespace std; template<typename ElemType> class adjlistnetworkvex { protected: ElemType data; adjlistnetworkarc* firstarc; public: adjlistnetworkvex() { firstarc = NULL;//默认的无参构造函数 } /* ~adjlistnetworkvex() { if (firstarc != NULL) { adjlistnetworkarc* p = firstarc; while (p ->getnextarc()!= NULL) { firstarc->setnextarc(p->getnextarc()); delete p; p = firstarc; } } }*/ adjlistnetworkvex(ElemType val, adjlistnetworkarc* adj=NULL) {//构造函数 data = val; firstarc = adj; } void setfirstarc(int v, adjlistnetworkarc* next = NULL) { firstarc = new adjlistnetworkarc(v, next); } void setdata(ElemType val) { data = val; } adjlistnetworkarc* getfirstarc() { return firstarc; } ElemType getdata() { return data; } //因为类被封装了，所以要写getter/setter };
sequeue.h
#pragma once #define DEFAULT_SIZE 100 #define OVER_FLOW 0 #define SUCCESS 1 #define UNDER_FLOW 0 #define status int template<class ElemType> class seqqueue { protected: int front, rear; int maxSize; ElemType* elems; public: seqqueue(int size = DEFAULT_SIZE) { maxSize = size; if (elems != NULL) delete []elems; elems = new ElemType[maxSize]; rear = front = 0; } virtual ~seqqueue() { delete[]elems; } bool isempty() { return rear == front; } status enqueue(const ElemType e) { if ((rear + 1) % maxSize == front) return OVER_FLOW; else { elems[rear] = e; rear = (rear + 1) % maxSize; return SUCCESS; } } status delqueue(ElemType& e) { if (!isempty()) { e = elems[front]; front = (front + 1) % maxSize; return SUCCESS; } else return UNDER_FLOW; } status gethead(ElemType& e) const { if (!isempty()) { e = elems[front]; return SUCCESS; } else return UNDER_FLOW; } };
main.cpp
#include<iostream> #include<cstring> #include<stdio.h> #include"adjlistdirnetwork.h" #define DEFAULT_SIZE 100 using namespace std; int main() { adjlistdirnetwork<string> adj(DEFAULT_SIZE); cout << "请输入结点个数:"; int vexcount; int v1, v2; string vexname; char ch=' '; cin >> vexcount; adj.setvexnum(vexcount); for (int i = 0; i < vexcount; i++) { printf_s("\n请输入第%d个结点的数据域\n", i+1); cin >> vexname; adj.getvex(i)->setdata(vexname); } cout << "请输入弧(a,b),以#表示输入终止" << endl; cin >> ch;//读取左括号( while (ch != '#') { cin >> ch;//以字符的形式读取顶点结点 v1 = int(ch - '0')-1;//将字符转换成数字。 //因为人从1开始数数，电脑从0开始数数，所以-1 cin >> ch;//读取逗号, cin >> ch;//以字符的形式读取另一个顶点结点 v2 = int(ch - '0')-1; cin >> ch;//读取右括号) cout << "请输入弧(a,b),以#表示输入终止" << endl; cin >> ch;//读取下一个左括号(或终止符号# adj.insertarc(v1, v2);//插入从v1到v2的边和从v2到v1的边 } cout << "\n输出该图：\n"; adj.show(); cout << "\n深度优先遍历序列为："; adj.DFSTraverse(); cout << "\n广度优先遍历序列为："; adj.BFSTraverse(); cout << "\n运行完成"; }
