//graph.h
#include
#include
#include"queue.h"
#include
using namespace std;
const int maxValue = 99;
const int size = 10;


struct Sight{
string name;
int id;
string brief;
};


class Graph{
private:
int info[size][size];//存放边的信息
Sight sight[size*size];//存放景点信息，名称、代号
int vexnum;//顶点个数
int arcnum;//边或弧数
bool visited[size*size];
public:
Graph();
void createGraph();
void Tranverse();
void search(string name);
void addEdge(int start, int end, int len);
void removeEdge(int start, int end);
int  getVexnum();
int  getArcnum();
void DFSTraverse();//深度优先遍历广度优先遍立
void DFS(int v); //遍历函数
void visitfun(int v);//访问函数
int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
void BFSTraverse();//广度优先遍立
void BFS(int v);
int Next(int u, int w);
};

void Graph::BFSTraverse()
{
for (int v = 0; v
for ( v = 0; v < vexnum; ++v)
if (!visited[v])  BFS(v);
}

void Graph::BFS(int v)
{
int u=-1;
Queue Q; Q.EnQueue(v); visited[v] = true;
while (!Q.isEmpty())
{
Q.DeQueue(u); visitfun(u);
for (int w = FirstAdjVex(u); w; w = Next(u, w))
if (!visited[w])
{
Q.EnQueue(w); visited[w] = true;
}
}
}


void Graph::DFSTraverse()//深度优先遍历
{
int v;
for (v = 0; v
visited[v] = false;
for (v = 0; v < vexnum; ++v)
if (!visited[v]) DFS(v);
}

void Graph::DFS(int v)
{
visited[v] = true;  visitfun(v);
for (int w = FirstAdjVex(v); w; w = NextAdjVex(v, w))
if (!visited[w])  DFS(w);
}

void Graph::visitfun(int v)
{
cout << "景点信息:" << endl;
cout << "名称:" << sight[v].name << endl;
cout << "编号:" << sight[v].id << endl;
cout << "简介:" << sight[v].brief << endl;
cout << "********************************" << endl;
}

int Graph::FirstAdjVex(int v)
{
for (int i = 0; i
if (info[v][i] != maxValue)
{
if (visited[i] != true) return i;
}


return 0;//返回-1表示该结点没有邻接结点
}

int Graph::Next(int v, int w)//广度优先遍历寻找顶点的下一个邻接点
{
for (int i = 0; i
if (info[v][i] != maxValue)
{
if (visited[i] != true) return i;
}
return 0;
}

int Graph::NextAdjVex(int v, int w)
{
for (int j = 0; j
if (info[w][j] != maxValue)
{
if (visited[j] != true) return j;
}
for (int i = 0; i
if (info[v][i] != maxValue)
{
if (visited[i] != true) return i;
}
return 0;
}

Graph::Graph()
{
vexnum = 0;
arcnum = 0;
for (int i = 0; i
for (int j = 0; j
info[i][j] = maxValue;
}

int Graph::getVexnum()
{
return vexnum;
}

int Graph::getArcnum()
{
return arcnum;
}

void Graph::search(string name)
{

for (int k = 0; k
if (name == sight[k].name)
{
cout << "名称:" << sight[k].name << endl;
cout << "编号:" << sight[k].id << endl;
cout << "简介:" << sight[k].brief << endl;
}
}

void Graph::addEdge(int start, int end, int len){ //在两个指定下标的节点之间添加一条边
if (start>size || end > size)return;
info[start][end] = len;
info[end][start] = len;
arcnum++;
}

void Graph::removeEdge(int start, int end){    //删除两个指定下标顶点之间的边
if (info[start][end] == maxValue || info[end][start] == maxValue)return;
//cout << "顶点" << start << "与" << "顶点" << end << "之间不存在边!" << endl;
info[start][end] = maxValue;
info[end][start] = maxValue;
arcnum--;
}

void Graph::createGraph()
{

cout << "请输入景点数目:";
cin >> vexnum;
for (int i = 0; i
{
cout << "请输入第" << i + 1 << "个景点的信息" << endl;
cout << "名称:";
cin >> sight[i].name;
cout << "编号:";
cin >> sight[i].id;
cout << "简介:";
cin >> sight[i].brief;
}
}

void Graph::Tranverse()
{
for (int k = 0; k
{
cout << "名称:" << sight[k].name << endl;
cout << "编号:" << sight[k].id << endl;
cout << "简介:" << sight[k].brief << endl;
}

cout << "***************************************" << endl;
for (int i = 0; i
{
for (int j = 0; j
{
cout <<setiosflags(ios::left)<<info[i][j] << "   ";
}
cout << endl;
}
}


//queue.h
typedef int ElemType;
const int Max_Size = 100;

class Queue{
private:
int rear;
int front;
bool flag;
ElemType elem[Max_Size];
public:
Queue();
bool EnQueue(ElemType e);
bool DeQueue(ElemType &e);
bool setEmpty();
bool isEmpty();//是否为空，为空返回true否则返回false
bool isFull();//队列满返回true否则返回false
void get(int index, ElemType &e);
int getLength();
void Tranverse();
};

Queue::Queue()
{
flag = true;//初始化为空队列
rear = 0;
front = 0;
}

int Queue::getLength()
{
return (rear + Max_Size - front) % Max_Size;
}


void Queue::get(int index, ElemType &e)
{
if (isEmpty())exit(1);

e = elem[index];
}


bool Queue::isFull()
{
if (flag == false)//false是非空，队列满的前提
return rear == front ? true : false;
else return false;//队列不满返回false

}

bool Queue::isEmpty()
{
if (flag)//flag为true
return rear == front ? true : false;
else return false;
}


bool Queue::EnQueue(ElemType e)
{
if (isFull()) return false;
elem[rear] = e;
rear = (rear + 1) % Max_Size;
return true;
}

bool Queue::DeQueue(ElemType &e)
{
if (isEmpty()) return false;
e = elem[front];
front = (front + 1) % Max_Size;
return true;
}


//main.cpp
#include
#include"graph.h"
using namespace std;


void order()
{
cout << "1.创建图(景点)" << endl;
cout << "2.查看图(景点)的信息" << endl;
cout << "3.查找景点" << endl;
cout << "4.删除两个顶点之间的边" << endl;
cout << "5.深度优先遍历" << endl;
cout << "6.广度优先遍历" << endl;
cout << "7.退出" << endl;
cout << "请输入指令:" << endl;
}

void operation()
{
Graph g1;
int s, e, l, edgeNum;
int index;
order();
while (cin >> index)
{
switch (index)
{
case 1:{
  g1.createGraph();
  cout << "请输入边的数目:";
  cin >> edgeNum;
  for (int i = 0; i
  {
  cout << "请输入第" << i + 1 << "条边的信息:";
  cin >> s >> e >> l;
  g1.addEdge(s, e, l);
  }
  order();
}; break;
case 2:{g1.Tranverse(); order(); }break;
case 3:{
  string name;
  cout << "请输入要查找的名称:";
  cin >> name;
  g1.search(name);
  order();
}; break;
case 4:{
  cout << "请输入两个顶点:";
  cin >> s >> e;
  g1.removeEdge(s, e);
  order();
}; break;
case 5:{g1.DFSTraverse(); order(); }; break;
case 6:{g1.BFSTraverse(); order(); }; break;
case 7:exit(1); break;
default: cout << "错误的指令!"; break;
}
}
}

int main()
{
operation();
system("pause");
return 0;
}