#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 添加头文件
#define MAX_VERTEX_NUM 100 //图中最大顶点数
//struct ArcNode* nextarc;
//ArcNode* firstarc;
//这两个是很有必要的，如果你没有这两个指针，你就无法判断当前的顶点是哪一个
// adj是邻接点，firstarc和nextarc分别代表当前和下一个点。
//图的邻接表存储结构定义
typedef struct ArcNode {
int adjvex; //邻接点在数组中的位置下标
struct ArcNode* nextarc; //指向下一个邻接点的指针
} ArcNode;
typedef struct VNode {
char data; //顶点信息
ArcNode* firstarc; //指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
//使用结构体嵌套的方式，把两个顶点还有边都给嵌套起来
typedef struct {
AdjList vertices; //邻接表，也就是顶点的意思
int vexnum, arcnum; //顶点数和弧数
bool is_directed; //是否是有向图
} ALGraph;
//查找顶点的第一个邻接点
int FirstAdjVex(ALGraph G, int v)
{
if (G.vertices[v].firstarc != NULL) {
return G.vertices[v].firstarc->adjvex;
}
else {
return -1; //返回“空”
}
}
//查找顶点的下一个邻接点
int NextAdjVex(ALGraph G, int v, int w)
{
ArcNode* p = G.vertices[v].firstarc;
while (p != NULL && p->adjvex != w) {
p = p->nextarc;
}
//先找到w先，题目说相对于w的下一个邻接点
if (p != NULL && p->nextarc != NULL) {
return p->nextarc->adjvex;
}
else {
return -1; //返回“空”
}
}
//v是图中的某个顶点也就是 ArcNode* p，即G.vertices[v].firstarc;
//而p->adjvex != w这是v当前的邻接点
//那下一个邻接点自然就是 p->nextarc->adjvex了
//一般节点的下一个节点就只有一个，
// 不是DFS不会一直往下面找，下一个就到空了，所以说是合理的循环。
//题目的意思就是说，w是v的临接节点。
//插入一个新顶点
void InsertVex(ALGraph* G, char v)
{
if (G->vexnum >= MAX_VERTEX_NUM) {
printf("Error: The graph is full!\n");
return;
}
G->vertices[G->vexnum].data = v;//存放点
G->vertices[G->vexnum].firstarc = NULL;//存放其邻接点
G->vexnum++;
}
//删除一个顶点及其相关的弧
void DeleteVex(ALGraph* G, char v)
{
int i, j;
ArcNode* p, * q;
i = LocateVex(*G, v);//找到顶点位置
if (i == -1) {
printf("Error: Vertex not found!\n");
return;
}
//删除与该顶点相关的弧
for (j = 0; j < G->vexnum; j++) {
p = G->vertices[j].firstarc;//寻找每个图中的所有的第一个邻接点。
while (p != NULL) {
if (p->adjvex == i) {
//如果邻接点是该下标的点
q = p->nextarc;
//因为是第一个邻接点，不存在有无前后的问题，所以直接接上下面一段就行了
free(p);
G->arcnum--;
p = q;
}
else {
//指针要动的只是邻接点为i的点
//在它后面的点，直接下标往前移一位就行了
if (p->adjvex > i) {
p->adjvex--;
//就是已经明确，我们要删除i点，
// 那么其他所有的邻接点下标位置都要往前移1位
//因为要删除i点了，那么所有的点的位置都要发生变化，就像数组那样
//删除一个元素，全部元素都要往前移动。
//至于前面的 if (p->adjvex == i)
//那是因为直接将p点直接删除了，自然就不需要再管它的位置在哪里了
}
p = p->nextarc;//继续往下找，重复当前操作。
}
// 在这段代码中，adjvex属性表示一个弧所指向的顶点在图中的索引位置。
// 当删除与指定顶点相关的弧时，如果不进行调整，
// 那些位于指定顶点之后的顶点索引将会发生变化。
//通过将p指向的弧的adjvex属性减1，可以确保顶点之间的编号连续性。
// 也就是说，删除一个顶点之后，
// 它之后的顶点的索引都需要减少1，以保持对应关系的正确性。
//
// 例如，假设原来顶点i之后的顶点分别为i + 1、i + 2、i + 3，
// 删除与顶点i相关的弧之后，i + 1变成了i，i + 2变成了i + 1，i + 3变成了i + 2，以此类推。
// 这样做的目的是为了在删除操作之后，
// 依然可以通过顶点的索引来正确访问和操作图的邻接信息。
}
}
//删除该顶点本身
//弧跟顶点是不一样的概念
for (j = i + 1; j < G->vexnum; j++) {
G->vertices[j - 1] = G->vertices[j];
}
for (j = 0; j < G->vexnum; j++) {
p = G->vertices[j].firstarc;
while (p != NULL) {
if (p->adjvex > i) {
p->adjvex--;
}
p = p->nextarc;
}
}
G->vexnum--;
// 第一次循环是在删除与指定顶点相关的弧时进行的。
//当找到邻接点的索引大于被删除顶点的索引时，将其减1，以保持顶点之间的编号连续性。
// 第二次循环是在删除顶点本身后进行的。对于每个顶点，
// 遍历其邻接链表，如果邻接点的索引大于被删除顶点的索引，
// 则将其减1，同样是为了保持邻接信息的正确性。
// 这两次循环的目的都是使得删除一个顶点后，
// 其他顶点的索引发生相应变化，以确保后续的访问和操作仍然有效。
}
//邻接表表示当前顶点中
//分支到的任何一个下一个的顶点。
//
//而每一次都指针指向下一个然后删除原先的p节点。
//也就等于断开了所有与当前节点的链接，
//也就成功消除了它的所有弧了。
//插入一条新弧
void InsertArc(ALGraph* G, char v, char w)
{
int i, j;
ArcNode* p, * q;
i = LocateVex(*G, v);
j = LocateVex(*G, w);
if (i == -1 || j == -1) {
printf("Error: Vertex not found!\n");
return;
}
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;//邻接点是j
p->nextarc = G->vertices[i].firstarc;//因为是插入，所以用next而非first
G->vertices[i].firstarc = p;
//p代替了 G->vertices[i].firstarc
//就是因为p中还有adj这个j的值，
/*就是为了插入新弧才代替 G->vertices[i].firstarc的*/
//所以说原地址的 G->vertices[i].firstarc把它换成p就成功插入了。
//p是新的头结点，所以原来的地址改成p的指针没毛病
/* 首先，p->nextarc = G->vertices[i].firstarc;
将p的下一个指针指向顶点i的原第一个邻接边，这样p就成为了新的第一个邻接边。
然后，G->vertices[i].firstarc = p;
将顶点i的第一个邻接边指针指向p，即p成为了顶点i邻接表的新的第一个节点。*/
/* 又忘了指针偏移了，你记住，变动链表以后一定要把指针的头指向新的头结点，不然全部都错了！*/
G->arcnum++;
if (!G->is_directed) {
q = (ArcNode*)malloc(sizeof(ArcNode));
q->adjvex = i;
q->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = q;
G->arcnum++;
}
}
//p->adjvex 放置末端的点
//G->vertices[i].firstarc; 放置前端的点
//问：p->nextarc = G->vertices[i].firstarc; 为什么不直接写成p = G->vertices[i].firstarc;?
//这是因为G->vertices[i].firstarc是一个指向边表结构体的指针，
//而p是一个指向边表结构体的指针变量。
//如果将两者直接赋值，会导致p与G->vertices[i].firstarc指向同一块内存区域，
//任何一方对该内存区域的修改都会影响另一方。这可能不是我们期望的结果。
//
//正确的做法是让p指向与G->vertices[i].firstarc相同的内存地址，
//但是它们是两个不同的指针变量，互相独立，对其中一个指针变量的修改不会影响另一个。
//所以应该写成p->nextarc = G->vertices[i].firstarc，
//这样可以保证p指向与G->vertices[i].firstarc相同的内存地址，
//但是它们是两个不同的指针变量，互相独立，对其中一个指针变量的修改不会影响另一个。
//总结:指针的特殊性问题，直接赋值就表示指向同一个地点，p指针就等于所指向的目标的地址。
//不独立，修改p也就等于修改了原地址的值。所以必须要用next才能成为独立的指针。
//相当于我只是使用了原地址的值，但我是作为独立的一个变量
//删除一条弧
void DeleteArc(ALGraph* G, char v, char w)
{
int i, j;
ArcNode* p, * q;
i = LocateVex(*G, v);
j = LocateVex(*G, w);
if (i == -1 || j == -1) {
printf("Error: Vertex not found!\n");
return;
}
p = G->vertices[i].firstarc;//从起点开始找
q = NULL;
while (p != NULL && p->adjvex != j) {
q = p;
//为什么要保存前面的顶点？
//为了储存前面表的数据,方便后面衔接。
p = p->nextarc;
}
if (p != NULL) {
if (q == NULL) {
G->vertices[i].firstarc = p->nextarc;
//只有一个点的情况
}
else {
q->nextarc = p->nextarc;
}
free(p);
G->arcnum--;
}
if (!G->is_directed) {
p = G->vertices[j].firstarc;
q = NULL;
while (p != NULL && p->adjvex != i) {
q = p;
p = p->nextarc;
}
if (p != NULL) {
if (q == NULL) {
G->vertices[j].firstarc = p->nextarc;
}
else {
q->nextarc = p->nextarc;
}
free(p);
G->arcnum--;
}
}
}
//定位某个顶点的位置
int LocateVex(ALGraph G, char v)
{
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v) {
return i;
}
}
return -1; //未找到
}
int main()
{
ALGraph G;
G.is_directed = false; // 设置图为无向图
G.vexnum = 0;
G.arcnum = 0;
InsertVex(&G, 'A');
InsertVex(&G, 'B');
InsertVex(&G, 'C');
InsertVex(&G, 'D');
InsertArc(&G, 'A', 'B');
InsertArc(&G, 'A', 'C');
InsertArc(&G, 'B', 'D');
InsertArc(&G, 'C', 'D');
printf("The first adjacent vertex of A is %c\n", G.vertices[0].firstarc->adjvex + 'A');
printf("The next adjacent vertex of A after B is %c\n", NextAdjVex(G, 0, LocateVex(G, 'B')) + 'A');
DeleteArc(&G, 'B', 'D');
DeleteVex(&G, 'C');
return 0;
}