Ⅰ.功能：
1.创建图
2.展示全图
3.添加顶点
4.添加边
5.删除顶点
6.删除边
7.查看指定边权值
8.修改指定边权值
9.输出两点间的所有简单路及路径对应权值
10.销毁图
ps:关于9，如果不存在任何简单路，输出“不存在任何简单路”。简单路：不含重复顶点的路。如
1 2 3 4 5是简单路，1 2 3 1 4 5不是简单路。可以想见，对于大多数问题，非简单路是没有
研究意义的。如从北京到上海的路线，多次经过同一地点的路线是没有研究价值的。
Ⅱ.不足:
1.代码冗长，复用率低。原因是有些操作基本相同但又有细微不同（如goto mark6;goto
mark7;）,难以封装成一个函数。在此请求大神给出好的解决办法。
2.类的成员函数的实现也写在了头文件中，使头文件过长。原因是前几次代码使用了模板，（看
过在下前几篇博文的读者应该知道）而用模板的话，就要求要么将类的成员函数的实现和类放
在一起，要么放在main函数中（尽管听有人说《C++Primer》中说不这样也行，但在下实测的
结果是——必须这样）。在下写习惯了，写完后才发现对于此次代码，将类的成员函数的实现
另放一个文件好。但代码已经写完，就暂时不改了，万一再改出bug来，没准又得调半天，这里
和大家说一声，求原谅。
3.使用了goto语句（前几次也一样），有人对goto严格禁止，但依在下愚见，小范围内使用还是
可以的，再说，在下也是迫不得已，实在没有更好的办法了。还是那句话，求大神指教。
4.时空复杂性较高，特别是时间复杂性，懂这方面的读者一看在下的代码便知。主要是顶点和边
都是用链表实现的，动不动就要遍历，但话说回来，至今在下还没找到比用链表实现更好的方
法，还请高人指教。
Ⅲ.优点：
1.程序在多处用了控制，保证了程序的健壮性和友好，可重复操作，体验良好。
2.仅提供Operate()函数一个接口，较大限度地实现了封装。
Ⅳ.博主推荐
1.找两点间所有简单路并输出路径总权值有一定思维量和技巧性，有兴趣的读者可自行分析相
关代码，体会其思想。此代码为本人原创（当然不排除读者在其它地方见到相似代码，尽管在
下未参考任何书籍或网络资源）。
Ⅴ.代码：
//.h文件
#ifndef GRAPH_H
#define GRAPH_H
#include<iostream>
#include<iomanip>
using namespace std;
struct Edge //边结构体
{
int egnum; //结点编号
int weight; //权值
Edge* enext; //下一边结点
Edge(int enm, int wgt, Edge* enxt);
};
Edge::Edge(int enm, int wgt, Edge* enxt) //边结构体构造函数
{
egnum = enm;
weight = wgt;
enext = enxt;
}
struct Vertices //顶点结构体
{
int number; //结点编号
Edge* state; //顶点状态，用于标记顶点是否被遍历
Edge* eghead; //边链表头结点
Vertices* vnext; //下一顶点结点
Vertices(int num,Edge* sta, Edge* eghed, Vertices* vnxt);
};
Vertices::Vertices(int num,Edge* sta,Edge* eghed, struct Vertices* vnxt) //顶点结构体构造函数
{
number = num;
state = sta;
eghead = eghed;
vnext = vnxt;
}
class Graph //图类
{
private:
int vsize; //记录顶点个数
int esize; //记录边个数
Vertices* vhead; //顶点链表头指针
Vertices* vtail; //顶点链表尾指针
public:
Graph();
~Graph();
void Operate(); //封装操作
private:
Vertices* Revads(const int num); //返回某顶点地址，同时用于检测某顶点是否存在
int Creat(); //创建图
Edge* IfEdge(const int vfrom, const int vto); //查看两顶点间是否存在边
bool Addvt(); //添加顶点
int Addeg(); //添加边
void ShowAll(); //展示全图
int Getweit(const int vfrom, const int vto); //查看指定边权值
bool FinRoad(const int vfrom, const int vto); //查找两点间所有简单路
void Destory(); //销毁图
};
Graph::Graph() //图类构造函数
{
vsize = 0;
esize = 0;
vhead = NULL;
vtail = NULL;
}
Graph::~Graph() //图类析构函数
{
Destory();
}
Vertices* Graph::Revads(const int num) //返回某顶点地址，同时用于检测某顶点是否存在
{
Vertices* pt = vhead; bool flag = false;
while (pt)
{
if (pt->number == num){ flag = true; break; }
pt = pt->vnext;
}
if (flag)return pt;
else return NULL;
}
Edge* Graph::IfEdge(const int vfrom, const int vto) //查看两顶点间是否存在边
{
Vertices* pt = Revads(vfrom);
Edge* pte = pt->eghead;
while (pte)
{
if (pte->egnum == vto)
{
return pte;
}
pte = pte->enext;
}
return NULL;
}
bool Graph::Addvt() //添加顶点
{
cout << "请您输入要添加顶点的个数，程序将自动从当前图中顶点的最大编号往下顺次为新添加顶点编号：" << endl;
int sum; cin >> sum;
int itnum = vtail->number + 1;
int begin = itnum;
for (int i = 0; i < sum;i++)
{
vtail->vnext = new Vertices(itnum, NULL, NULL, NULL);
if (!vtail->vnext){ cout << "申请空间失败！" << endl; return false; }
vtail = vtail->vnext;
itnum++;
vsize++;
}
cout << "顶点添加成功！" << endl;
cout << "新顶点编号从" << begin << "到" << itnum-1 << ",目前图中共有顶点" << vsize << "个。" << endl;
cout << "当前新顶点为孤立顶点，建议您通过选项4添加指向新顶点的边和由新顶点发出的边。" << endl;
return true;
}
int Graph::Addeg() //添加边
{
cout << "提示：" << endl;
cout << "输入时，请您依次输入边的起点编号、终点编号和边的权值，中间以空格相隔，例如：1 2 20。并且，请您务必输入正整数，";
cout << "如果您未按规定输入，由此造成的一切后果，将由您个人承担，程序开发者概不负责！" << endl;
bool sign = true, flag = true;
int from, to, weit, choice, abandon,abandon1,abandon2; //标签
Vertices* pt=NULL;
while (sign)
{
while (flag)
{
abandon = 0; abandon1 = 0; abandon2 = 0; //只要重新输入，就要进行一次初始化
cout << "请您依次输入边的起点、终点和权值：" << endl;
cin>> from >> to >> weit;
if (from == to) //如果起、止点相同，不进行进一步检查，直接进行选择
{
cout << "起点编号与终点编号不得相同！重新输入请按1，放弃本次输入请按0：" << endl;
cin >> choice;
if (choice == 0){ abandon1 = 1; abandon = 1; }
else { abandon1 = 1; flag = false; }
}
if (!abandon1) //如果起、止点不同，检查起、止点是否正确及两点间是否有边
{
pt = Revads(from);
if (!pt) //如果起点不存在，不进行进一步检查，直接进行选择
{
cout << "您输入的起点不存在！重新输入请按1，放弃本次输入请按0：" << endl;
cin >> choice;
if (choice == 0){ abandon2 = 1; abandon = 1; }
else { abandon2 = 1; flag = false; }
}
else //如果起点存在，检查终点，若果终点不存在，不进行进一步检查，直接进行选择
{
if (!Revads(to))
{
cout << "您输入的终点不存在！重新输入请按1，放弃本次输入请按0：" << endl;
cin >> choice;
if (choice == 0){ abandon2 = 1; abandon = 1; }
else { abandon2 = 1; flag = false; }
}
}
if (!abandon2)//如果两点输入正确且都存在，检查两点间是否有边，若无，进行选择
{
Edge* ifedge = IfEdge(from, to);
if (ifedge)
{
cout << "从顶点" << from << "到顶点" << to << "的边已经存在，本程序部允许重复添加！重新输入请按1，放弃本次输入请按0：" << endl;
cin >> choice;
if (choice == 0)abandon = 1;
else flag = false;
}
}
}
if (flag)flag = false;
else flag = true;
} //控制输入正确的起点和终点
//插入边
if (!abandon) //如果起点和终点输入正确，开始插入边
{
Edge* pte = new Edge(to, weit, NULL);
if (!pte){ cout << "申请空间失败！" << endl; goto marka; }
if (!pt->eghead)
{
pt->eghead = pte;
}
else
{
Edge* pter = pt->eghead;
while (pter->enext)
pter = pter->enext;
pter->enext = pte;
}
esize++;
cout << "添加成功！目前图中有边" <<esize<< "条。" << endl;
}
cout << "是否继续添加边？是请按1，否则请按0：" << endl;
cin >> choice;
if (choice == 1)flag = true;
else sign = false;
}
cout << "边添加完毕！目前图中共有边" <<esize<< "条。"<<endl;
marka:
return 0;
}
int Graph::Creat() //创建图
{
bool sign = false, flag = true;
int choice1;
cout << "请您输入欲创建图的顶点的个数，程序将为您创建顶点并为顶点从1开始顺序编号：" << endl;
cout << "（注意：请您务必输入正整数，否则后果自负！）" << endl;
int numofv; cin >> numofv;
int i;
for (i = 1; i <= numofv;i++)
{
if (!vhead)
{
vhead = vtail = new Vertices(i, NULL,NULL, NULL);
if (!vhead){ cout << "申请空间失败！" << endl; goto markc;}
}
else
{
vtail->vnext = new Vertices(i,NULL, NULL, NULL);
if (!vtail->vnext){ cout << "申请空间失败！" << endl; goto markc; }
vtail = vtail->vnext;
}
}
vsize = i - 1;
cout << "顶点创建成功！编号从1到" <<vsize<<"。"<< endl;
cout << "是否添加边？是请按1，否则请按0：" << endl;
cin >> choice1;
if (choice1 == 1)Addeg();
if (choice1 == 0)cout << "图创建成功，但图中无边！" << endl;
else cout << "图创建成功！" << endl;
markc:
return 0;
}
void Graph::ShowAll() //展示全图
{
cout << "<>内为顶点编号，[]内为权值：" << endl;
cout << "顶点 " << "相邻顶点及边的权值" << endl;
Vertices* pt = vhead;
while (pt)
{
cout << setiosflags(ios::left);
cout << "<"<<setw(2)<<pt->number <<">"<< " ";
Edge* pte = pt->eghead;
while (pte)
{
cout << "<" << setw(2)<<pte->egnum << ">" << "[" <<setw(3)<< pte->weight << "]" << " ";
pte = pte->enext;
}
cout << endl;
pt = pt->vnext;
}
}
int Graph::Getweit(const int vfrom, const int vto) //查看指定边权值
{
Vertices* pt = Revads(vfrom);
Edge* pte = pt->eghead;
while (pte)
{
if (pte->egnum == vto)
return pte->weight;
pte = pte->enext;
}
return 0;
}
bool Graph::FinRoad(const int vfrom, const int vto) //查找两点间所有简单路
{
bool road = false, right, repeat, goon1, goon2;
Vertices* pt = NULL;
Edge* pte = NULL;
int* array = new int[vsize];
array[0] = vfrom;
int top = 0;
while (top>=0)
{
right = false; repeat = false; goon1 = true; goon2 = true;
pt = Revads(array[top]);
pte = pt->state;
if (!pte)
{
pt->state = pt->eghead; top--; goon1 = false;
}
if (goon1)
{
while (!right&&pte)
{
int item = pte->egnum;
for (int i = 0; i <= top;i++)
{
if (array[i] == item)
{
repeat = true;
break;
}
}
if (repeat)
{
repeat = false;
pte = pte->enext;
}
else right = true;
}//内层while结束
if (!pte)
{
pt->state = pt->eghead; top--; goon2 = false;
}
if (goon2)
{
array[++top] = pte->egnum;
pt->state = pte->enext;
if (pte->egnum == vto)
{
road = true;
int sum = 0;
for (int i = 0, j = 1; j <= top;i++,j++)
{
sum = sum + Getweit(array[i], array[j]);
}
for (int i = 0; i <= top; i++)
{
cout << array[i] << " ";
}
cout << "权值：" << sum;
cout << endl;
top--;
}
}//goon2结束
}//goon1结束
}//外层while结束
delete[]array;
return road;
}
void Graph::Destory() //销毁图
{
while (vhead)
{
Edge* pte = vhead->eghead;
while (pte)
{
Edge* iteme = pte;
pte = pte->enext;
delete iteme;
}
Vertices* itemv = vhead;
vhead = vhead->vnext;
delete itemv;
}
vhead = NULL;
vtail = NULL;
vsize = 0;
esize = 0;
}
void Graph::Operate() //封装操作
{
bool flager = true;
while (flager)
{
cout << "请您选择操作（输入操作前的数字进行选择）：" << endl;
cout << "1.创建图" << endl;
cout << "2.展示全图" << endl;
cout << "3.添加顶点" << endl;
cout << "4.添加边" << endl;
cout << "5.删除顶点" << endl;
cout << "6.删除边" << endl;
cout << "7.查看指定边权值" << endl;
cout << "8.修改指定边权值" << endl;
cout << "9.查找两点间所有简单路" << endl;
cout << "10.销毁图" << endl;
int chonum; //choice number
cin >> chonum;
switch (chonum)
{
//创建图
case 1:
{
if (vhead){ cout << "图已经创建，无需再建！若想新建，请您先销毁旧图！" << endl; break; }
Creat();
break;
}
//展示全图
case 2:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法执行展示全图操作！" << endl; break; }
ShowAll();
break;
}
//添加顶点
case 3:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法在此处执行添加顶点操作！您可通过选项1来添加顶点。" << endl; break; }
Addvt();
break;
}
//添加边
case 4:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法执行添加边操作！" << endl; break; }
Addeg();
break;
}
//删除顶点
case 5:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法执行删除顶点操作！" << endl; break; }
int choice5,ver;
Vertices* pt = NULL;
cout << "警告：" << endl;
cout << "删除顶点操作存在风险！本程序在删除顶点的同时，将自动删除与该顶点直接相连的所有边（包括指向该顶点的和由该顶点发出的），";
cout << "因此，删除顶点操作可能产生较为严重的后果（如使连通的图一分为二或产生孤立点等）。请您慎重考虑！";
cout << "为安全起见，本操作一次只允许删除一个顶点，若您想删除多个顶点，可重复执行本操作。" << endl;
cout << "您确定要删除顶点吗？确定请按1，取消请按0：" << endl;
cin >> choice5;
if (choice5 == 0)break;
cout << "提示：" << endl;
cout << "输入顶点编号时，请您务必输入正整数，如果您未按规定输入，由此造成的一切后果，将全部由您个人承担，程序开发者概不负责！" << endl;
bool sign5 = true;
while (sign5) //控制输入正确的顶点编号
{
cout << "请您输入顶点编号：" << endl;
cin >> ver;
pt = Revads(ver);
if (!pt)
{
cout << "您输入的顶点在当前图中不存在！重新输入请按1，退出删除顶点操作请按0：" << endl;
cin >> choice5;
if (choice5 == 0)goto mark5;
else sign5 = false;
}
if (sign5)sign5 = false;
else sign5 = true;
}//while(sign5)结束
//删除
//将欲删除顶点及其边单拿出来
if (pt == vhead)
vhead = vhead->vnext;
else
{
Vertices* ptv = vhead;
while (ptv) //找到pt的前驱
{
if (ptv->vnext == pt)
break;
ptv = ptv->vnext;
}
ptv->vnext = pt->vnext;
}
//删除顶点指向的边
Edge* pte = pt->eghead;
while (pte)
{
Edge* iteme = pte;
pte = pte->enext;
delete iteme;
esize--;
}
//删除顶点
delete pt;
vsize--;
//删除指向该顶点的边
Vertices* ptrv = vhead;
while (ptrv)
{
int item = ptrv->number;
Edge* ptre = IfEdge(item, ver);
if (ptre)
{
if (ptre==ptrv->eghead)
{
ptrv->eghead = ptre->enext;
delete ptre;
esize--;
}
else
{
Edge* pre = ptrv->eghead;
while (pre)
{
if (pre->enext == ptre)
break;
pre = pre->enext;
}
pre->enext = ptre->enext;
delete ptre;
esize--;
}
}
ptrv = ptrv->vnext;
}//while(ptrv)结束
cout << "删除成功！目前图中共有顶点" << vsize << "个，边" << esize << "条。" << endl;
mark5:
break;
}
//删除边
case 6:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法执行删除边操作！" << endl; break; }
int choice6,from,to;
Vertices* pt=NULL;
Edge* ifedge=NULL;
cout << "警告：" << endl;
cout << "删除边操作存在风险！（如使连通的图一分为二或产生孤立点等）请您慎重考虑！为安全起见，本操作一次只允许删除一条边，";
cout << "若您想删除多条边，可重复执行本操作。" << endl;
cout << "您确定要删除边吗？确定请按1，取消请按0：" << endl;
cin >> choice6;
if (choice6 == 0)break;
cout << "提示：" << endl;
cout << "输入时，请您依次输入起点编号和终点编号，务必输入正整数，并以空格相隔，例如：1 2。如果您未按规定输入，";
cout << "由此造成的一切后果，将全部由您个人承担，程序开发者概不负责！" << endl;
bool flag6=true,control6,control61;
while (flag6)
{
control6 = true; control61 = true;
cout << "请您依次输入边的起点编号和终点编号：" << endl;
cin >> from >> to;
if (from == to)
{
cout << "起点编号与终点编号不得相同！重新输入请按1，退出删除操作请按0：" << endl;
cin >> choice6;
if (choice6 == 0)goto mark6;
else { control6 = false; flag6 = false; }
}
if (control6)
{
pt = Revads(from);
if (!pt)
{
cout << "您输入的起点不存在！重新输入请按1，退出删除操作请按0：" << endl;
cin >> choice6;
if (choice6 == 0)goto mark6;
else { control61 = false; flag6 = false; }
}
else
{
if (!Revads(to))
{
cout << "您输入的终点不存在！重新输入请按1，退出删除操作请按0：" << endl;
cin >> choice6;
if (choice6 == 0)goto mark6;
else { control61 = false; flag6 = false; }
}
}
if (control61)
{
ifedge = IfEdge(from, to);
if (!ifedge)
{
cout << "不存在从顶点" << from << "到顶点" << to << "的边，无法执行删除操作！重新输入请按1，退出删除操作请按0：" << endl;
cin >> choice6;
if (choice6 == 0)goto mark6;
else flag6 = false;
}
}
}
if (flag6)flag6 = false;
else flag6 = true;
} //控制输入正确的起点和终点
//删除
if (ifedge==pt->eghead)
{
Edge* item = ifedge;
ifedge = ifedge->enext;
pt->eghead = ifedge;
delete item;
}
else
{
Edge* pter = pt->eghead;
while (pter)
{
if (pter->enext = ifedge)
break;
}
pter->enext = ifedge->enext;
delete ifedge;
}
esize--; //边数减1
cout << "从顶点" << from << "到顶点" << to << "的边已成功删除！目前图中共有边" <<esize<<"条。"<< endl;
mark6:
break;
}
//查看指定边权值
case 7:
{
if (!vhead){ cout << "图还未创建或已被销毁！无法执行查询操作！" << endl; break; }
cout << "提示：" << endl;
cout << "输入时，请您依次输入起点编号和终点编号，务必输入正整数，并以空格相隔，例如：1 2。如果您未按规定输入，";
cout << "由此造成的一切后果，将全部由您个人承担，程序开发者概不负责！" << endl;
bool control = true,sign7=true,flag7,flag71;
int vf, vt, choice7;
Vertices* ptv = NULL;
Edge* ifedge = NULL;
while (sign7)
{
while (control) //控制输入正确的起点编号和终点编号
{
flag7 = true; flag71 = true;
cout << "请您依次输入起点编号和终点编号：" << endl;
cin >> vf >> vt;
if (vf == vt)
{
cout << "起点编号与终点编号不得相同！重新输入请按1，退出查找操作请按0：" << endl;
cin >> choice7;
if (choice7 == 0)goto mark7;
else { flag7 = false; control = false; }
}