namespace Graph
{
enum GraphKind { DG, DN, UDG, UDN }; //图的种类分别表示有向图，有向网，无向图，无向网（带权图称为网）
class MGraph
{
private:
static const int INF = 2147483647; //无穷大
static const int MAX_VERTEX_NUM = 500; //顶点最大个数
struct ArcCell//边/弧的结构
{
int adj; //如果是带权图则用来存储边权值，如果是不带权图，用1来表示两个顶点之间有边。
string info; //边的信息，一般可以舍去
explicit ArcCell(int ad = INF, const string& inf = "") :adj(ad), info(inf) //边默认为无穷大
{
}
};
string vexs[MAX_VERTEX_NUM]; //顶点信息
int vexnum;//顶点数
int arcnum;//边数
GraphKind kind;//图的种类
ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//边的集合，用二维数组表示
bool visited[MAX_VERTEX_NUM];//用于图的遍历，用来记录顶点是否被访问过
deque que;//用于图的广度遍历
public:
MGraph(int vn, int an, GraphKind k) :vexnum(vn), arcnum(an), kind(k)
{
} //构造函数，需要提供图的顶点数，边数，和种类
int locateVertex(string s)//用于确认图的顶点序号，如顶点A、B、C、D依次编号为0， 1， 2， 3，则C的编号为2
{
int ret = -1;
for (int i = 0; i < vexnum; i++)
{
if (s == vexs[i])
{
ret = i;
break;
}
}
return ret;
}
void createGraph()//用于初始化生成图
{
for (int i = 0; i < vexnum; i++) //顶点到自身的边adj默认为0
{
arcs[i][i].adj = 0;
}
cout << "Enter vertex information:n";
for (int i = 0; i < vexnum; i++) //输入顶点信息，如A、B、C、D
{
cout << "vertex " << i << ": ";
getline(cin, vexs[i]);
}
cout << endl;
int containInfo; //用于确认边/弧是否有需要记录的信息。
cout << "Whether contain information in arcs(yes 1, no 0) : ";
(cin >> containInfo).get();
cout << endl;
switch (kind)
{
case DG: createDG(containInfo); break;
case DN: createDN(containInfo); break;
case UDG: createUDG(containInfo); break;
case UDN: createUDN(containInfo); break;
}
}
void createDG(int containInfo)//生成有向图
{
for (int i = 0; i < arcnum; )
{
string v1, v2, arcInfo;
cout << "Enter " << "arc " << i << " :n";
cout << "v1: ";
getline(cin, v1);
cout << "v2: ";
getline(cin, v2);
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 != -1 && n2 != -1 && n1 != n2)
{
if (arcs[n1][n2].adj == INF) //防止重复添加边
{
i++;
arcs[n1][n2].adj = 1;
if (containInfo)
{
cout << "info: ";
getline(cin, arcs[n1][n2].info);
}
}
}
}
}
void createDN(int containInfo) //生成有向网
{
for (int i = 0; i < arcnum; )
{
string v1, v2, arcInfo;
int weight;
cout << "Enter " << "arc " << i << " , and its weight:n";
cout << "v1: ";
getline(cin, v1);
cout << "v2: ";
getline(cin, v2);
cout << "weight: ";
cin >> weight;
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 != -1 && n2 != -1 && n1 != n2)
{
if (arcs[n1][n2].adj == INF)
{
i++;
arcs[n1][n2].adj = weight;
if (containInfo)
{
cout << "info: ";
getline(cin, arcs[n1][n2].info);
}
}
}
}
}
void createUDG(int containInfo)
{
for (int i = 0; i < arcnum; )
{
string v1, v2, arcInfo;
cout << "Enter " << "arc " << i << " :n";
cout << "v1: ";
getline(cin, v1);
cout << "v2: ";
getline(cin, v2);
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 != -1 && n2 != -1 && n1 != n2)
{
if (arcs[n1][n2].adj == INF)
{
i++;
arcs[n1][n2].adj = 1;
if (containInfo)
{
cout << "info: ";
getline(cin, arcs[n1][n2].info);
}
arcs[n2][n1] = arcs[n1][n2];
}
}
}
}
void createUDN(int containInfo)
{
for (int i = 0; i < arcnum; )
{
string v1, v2, arcInfo;
int weight;
cout << "Enter " << "arc " << i << " , and its weight:n";
cout << "v1: ";
getline(cin, v1);
cout << "v2: ";
getline(cin, v2);
cout << "weight: ";
cin >> weight;
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 != -1 && n2 != -1 && n1 != n2)
{
if (arcs[n1][n2].adj == INF)
{
i++;
arcs[n1][n2].adj = weight;
if (containInfo)
{
cout << "info: ";
getline(cin, arcs[n1][n2].info);
}
arcs[n2][n1] = arcs[n1][n2];
}
}
}
}
void bfsTraverse()//广度优先遍历
{
cout << endl;
cout << "Breadth First Search:n";
for (int i = 0; i < vexnum; i++)
{
visited[i] = false;//用visited值为false表示顶点没有被访问到
}
que.clear();
for (int i = 0; i < vexnum; i++) //一次广度遍历可能不能遍历到所有顶点，所以需要检查每个顶点是否都被遍历到
{
if (!visited[i])
{
BFS(i);
}
}
}
void BFS(int v)
{
que.push_back(v);
visited[v] = true;//已经入队的顶点，后面一定会访问到，故修改visited值为false，防止后续多次入队
while (!que.empty())
{
v = que.front();
que.pop_front();
cout << vexs[v] << endl;
for (int w = 0; w < vexnum; w++)//如果当前访问结点的邻接顶点没有被访问到，则将其邻接顶点入队及将其visited值修改为false
{
if (!visited[w] && arcs[v][w].adj > 0 && arcs[v][w].adj < INF)
{
que.push_back(w);
visited[w] = true;
}
}
}
}
void dfsTraverse()//深度优先遍历
{
cout << endl;
cout << "Depth First Search:n";
for (int i = 0; i < vexnum; i++)
{
visited[i] = false;
}
for (int i = 0; i < vexnum; i++)
{
if (!visited[i])
{
DFS(i);
}
}
}
void DFS(int v) //深度优先遍历采用递归算法
{
cout << vexs[v] << endl;
visited[v] = true;
for (int w = 0; w < vexnum; w++)
{
if (!visited[w] && arcs[v][w].adj > 0 && arcs[v][w].adj < INF)
{
DFS(w);
}
}
}
const string& getVex(int n) const //顶点编号n对应的值
{
if (n < 0 || n >= vexnum)
{
throw UnderflowException{};
}
return vexs[n];
}
void putVex(int n, const string& value) //修改顶点编号n对应的值
{
if (n < 0 || n >= vexnum)
{
throw UnderflowException{};
}
vexs[n] = value;
}
void insertVex(const string& value) //插入顶点，将其编号为vexnum，vexnum自加1
{
if (vexnum + 1 > MAX_VERTEX_NUM)
{
throw UnderflowException{};
}
vexs[vexnum++] = value;
}
void deleteVex(const string& s)//删除顶点，将与顶点邻接的边剔除，并更新顶点信息，同时vexnum自减1
{
int k = locateVertex(s);
if (k < 0)
{
return;
}
for (int i = 0; i < vexnum; i++) //删除与顶点邻接的边
{
for (int j = 0; j < vexnum; j++)
{
if (i > k && j > k)
{
arcs[i - 1][j - 1] = arcs[i][j];
}
else if (i > k)
{
arcs[i - 1][j] = arcs[i][j];
}
else if (j > k)
{
arcs[i][j - 1] = arcs[i][j];
}
}
}
for (int i = k + 1; i < vexnum; i++)//更新顶点表
{
vexs[i - 1] = std::move(vexs[i]);
}
vexnum--;
}
void insertArc(const string& v1, const string& v2, int weight = 1, const string& inf = string{}) //插入边，将边值修改为1或者权值，同时边自加1
{
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 < 0 || n2 < 0)
{
throw UnderflowException{};
}
if (n1 != n2)
{
arcnum++;
arcs[n1][n2].adj = weight;
arcs[n1][n2].info = inf;
if (kind == UDG || kind == UDN)
{
arcs[n2][n1] = arcs[n1][n2];
}
}
}
void deleteArc(const string& v1, const string& v2)//删除边，将边值修改为INF, 同时边自减1
{
int n1 = locateVertex(v1), n2 = locateVertex(v2);
if (n1 < 0 || n2 < 0)
{
throw UnderflowException{};
}
if (n1 != n2)
{
arcnum--;
arcs[n1][n2].adj = INF;
if (kind == UDG || kind == UDN)
{
arcs[n2][n1] = arcs[n1][n2];
}
}
}
};
}
