#pragma once
#include <iostream>
using namespace std;
// 定义边表结点
struct EdgeNode
{
int adjvex; // 邻接点域
EdgeNode* next;
};
// 定义顶点表结点
template<typename T>
struct VertexNode
{
T vertex;
int in;
EdgeNode* firstEdge;
};
// 基本操作
const int MaxSize = 10;
int visited[MaxSize] = { 0 }; // 全局数组变量 visited 初始化
template<typename T>
class ALGraph
{
public:
ALGraph(T a[], int n, int e); // 构造函数
~ALGraph(); // 析构函数
void AddVertex(T v); // 增加一个顶点
void AddEdge(int i, int j); // 增加一条弧
void DeleteEdge(int i, int j); // 删除一条弧
void DFTraverse(int v); // 深度优先遍历
void BFTraverse(int v); // 广度优先遍历
void TopSort(); // 拓扑排序
private:
VertexNode<T> adjlist[MaxSize]; // 存放顶点表的数组
int vertexNum; // 图的顶点数
int edgeNum; // 图的边数
};
// 构造函数
template<typename T>
ALGraph<T>::ALGraph(T a[], int n, int e)
{
vertexNum = n;
edgeNum = e;
// 输入顶点信息，初始化顶点表
for (int i = 0; i < vertexNum; i++) {
int ai;
cin >> ai;
adjlist[i].in = ai;
adjlist[i].vertex = a[i];
adjlist[i].firstEdge = nullptr;
}
// 依次输入每一条边
for (int k = 0; k < edgeNum; k++) {
int i, j;
// 输入边所依附的两个顶点的编号
cin >> i >> j;
// 生成一个边表结点s
EdgeNode* s = new EdgeNode;
s->adjvex = j;
// 将结点s插入表头
s->next = adjlist[i].firstEdge;
adjlist[i].firstEdge = s;
}
}
// 析构函数
template<typename T>
ALGraph<T>::~ALGraph()
{
// 释放边表结点的内存空间
for (int i = 0; i < vertexNum; i++) {
EdgeNode *p = adjlist[i].firstEdge;
while (p != nullptr) {
EdgeNode* q = p;
p = p->next;
delete q;
}
}
}
// 增加一个顶点
template<typename T>
void ALGraph<T>::AddVertex(T v)
{
if (vertexNum >= MaxSize) {
cout << "【图已满】";
return;
}
adjlist[vertexNum].vertex = v;
adjlist[vertexNum].in = 0;
adjlist[vertexNum].firstEdge = nullptr;
vertexNum++;
}
// 增加一条弧
template<typename T>
void ALGraph<T>::AddEdge(int i, int j)
{
if (i >= vertexNum || j >= vertexNum || i < 0 || j < 0) {
cout << "【顶点编号无效，无法添加】";
return;
}
EdgeNode* s = new EdgeNode;
s->adjvex = j;
s->next = adjlist[i].firstEdge;
adjlist[i].firstEdge = s;
edgeNum++;
}
// 删除一条弧
template<typename T>
void ALGraph<T>::DeleteEdge(int i, int j)
{
if (i >= vertexNum || j >= vertexNum || i < 0 || j < 0) {
cout << "【顶点编号无效，无法删除】";
return;
}
EdgeNode* p = adjlist[i].firstEdge;
EdgeNode* q = nullptr;
while (p != nullptr && p->adjvex != j) {
q = p;
p = p->next;
}
if (p == nullptr) {
cout << "【该弧不存在】";
return;
}
if (q == nullptr) {
adjlist[i].firstEdge = p->next;
}else {
q->next = p->next;
}
delete p;
edgeNum--;
}
// 深度优先遍历
template<typename T>
void ALGraph<T>::DFTraverse(int v)
{
EdgeNode* p = nullptr;
cout << adjlist[v].vertex<<" ";
visited[v] = 1;
// 工作指针 p 指向顶点 v 的边表
p = adjlist[v].firstEdge;
// 依次搜索顶点 v 的邻接点 j
while (p != nullptr) {
int j = p->adjvex;
if (visited[j] == 0) {
DFTraverse(j);
}
p = p->next;
}
}
// 广度优先遍历
template<typename T>
void ALGraph<T>::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 指向顶点 v 的边表
p = adjlist[w].firstEdge;
while (p != nullptr) {
j = p->adjvex;
if (visited[j] == 0) {
cout << adjlist[j].vertex<<" ";
visited[j] = 1;
Q[++rear] = j;
}
p = p->next;
}
}
}
// 拓扑排序
template<typename T>
void ALGraph<T>::TopSort()
{
// 累加器 count 初始化
int i, j, k, count = 0;
// 采用顺序栈并初始化
int S[MaxSize], top = -1;
EdgeNode* p = nullptr;
// 扫描顶点表
for (i = 0; i < vertexNum; i++) {
if (adjlist[i].in == 0) {
S[++top] = i;
}
}
// 当栈中还有入度为0的顶点时
while (top != -1) {
// 从栈中取出入度为0的顶点
j = S[top--];
cout << adjlist[j].vertex;
count++;
// 工作指针p初始化
p = adjlist[j].firstEdge;
// 扫描顶点表，找出顶点j的所有出边
while (p != nullptr) {
k = p->adjvex;
adjlist[k].in--;
// 将入度为0的顶点入栈
if (adjlist[k].in == 0) {
S[++top] = k;
}
p = p->next;
}
}
if (count < vertexNum) {
cout << "有回路";
}
}
