#include <iostream>
#include <string>
using namespace std;
//另外我定义结构体的方法存储无向网中边的两个顶点编号，我后面想建立一个修改或者增加删除无向网中结点的函数，应该怎么做
struct EdgeNode //定义边表结点
{
int adjvex; //邻接点域
EdgeNode *next;
};
struct VertexNode //定义顶点表结点
{
string vertex;
EdgeNode *firstEdge;
};
struct TwoPointsNum //定义一条边的两个顶点
{
int x, y;
};
const int num = 50;
const int MaxSize = 10; //图的最多顶点数
int visited [MaxSize] = { 0 };
class ALGraph
{
public:
ALGraph(string a[], int n, int e, TwoPointsNum b[]); //构造函数，建立n个顶点e条边的图
~ALGraph(); //析构函数，释放邻接表各边表结点的存储空间
void DFTraverse(int v); //深度优先遍历图
void BFTraverse(int v); //广度优先遍历图
private:
VertexNode adjlist[MaxSize]; //存放顶点表的数组
int vertexNum, edgeNum; //图的顶点数和边数
};
ALGraph::ALGraph(string a[], int n, int e, TwoPointsNum b[])
{
int i, j, k;
EdgeNode *s = nullptr;
vertexNum = n; edgeNum = e;
for (i = 0; i < vertexNum; i++) //输入顶点信息，初始化顶点表
{
adjlist[i].vertex = a[i];
adjlist[i].firstEdge = NULL;
}
for (k = 0; k < edgeNum; k++) //依次输入每一条边
{
i = b[k].x; j = b[k].y; //将边所依附的两个顶点的编号赋值给i,j。无向网图，i<j。
s = new EdgeNode; s->adjvex = j; //生成一个边表结点s
s->next = adjlist[i].firstEdge; //将结点s插入到第i个边表的表头
adjlist[i].firstEdge = s;
}
}
ALGraph :: ~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;
}
}
}
void ALGraph ::DFTraverse(int v)
{
int j;
EdgeNode *p = NULL;
cout << adjlist[v].vertex; visited[v] = 1;
p = adjlist[v].firstEdge; //工作指针p指向顶点v的边表
while (p != NULL) //依次搜索顶点v的邻接点
{
j = p->adjvex;
if (visited[j] == 0) DFTraverse(j);
p = p->next;
}
}
void ALGraph ::BFTraverse(int v)
{
int w, j, Q[MaxSize]; //采用顺序队列
int front = -1, rear = -1; //初始化队列
EdgeNode *p = nullptr;
cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v; //被访问顶点入队
while (front != rear) //当队列非空时
{
w = Q[++front];
p = adjlist[w].firstEdge; //工作指针p指向顶点v的边表
while (p != NULL)
{
j = p->adjvex;
if (visited[j] == 0) {
cout << adjlist[j].vertex; visited[j] = 1; Q[++rear] = j;
}
p = p->next;
}
}
}
int main()
{
string a[] = { "正门", "土木馆", "逸夫楼", "第一食堂", "图书馆", "校徽花坛", "1-2公寓"
, "实验楼", "行政楼", "篮球场", "第二食堂", "公共教学楼", "南门"
,"浴池", "商贸楼", "3-11公寓", "文体中心", "小篮球场", "足球场" };
struct TwoPointsNum n[28] = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }
, { 3 , 6 }, { 4 , 7 }, { 5 , 9 }, { 6 , 7 }, { 7 , 10 }, { 7 , 11 }, { 8, 11 }, { 8 , 12 }
, { 9 , 13 }, { 10, 11 }, { 10, 13 }, { 10, 14 }, { 11, 16 }, { 12, 17 }, { 13, 14 }, { 14, 15 }
, { 15, 16 }, { 15, 18 }, { 16, 17 }, { 16, 18 }, { 17, 18} };
ALGraph ALG(a, 19, 28, n); //建立具有19个顶点28条边的无向图
int i;
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出发进行广度优先遍历
system("pause");
return 0;
}
