邻接表1（C语言）(图)（icoding）

本文链接：https://blog.csdn.net/Bello9/article/details/106375848

这篇博客介绍了如何使用C语言通过邻接表来表示图，并重点讲解了如何利用malloc函数动态添加节点进行‘加边’操作，适合于图论学习和调试。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

//试在邻接表存储结构上实现图的基本操作 insert_vertex 和 insert_arc，相关定义如下：

typedef int VertexType;

typedef enum{
   
    DG, UDG
}GraphType;

typedef struct ArcNode
{
   
    int adjvex;
    InfoPtr *info;
    struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode
{
   
    VertexType data;
    ArcNode *firstarc;
}VNode;
typedef struct
{
   
    VNode vertex[MAX_VERTEX_NUM];
    int vexnum, arcnum;
    GraphType type;
}ListGraph;

int locate_vertex(ListGraph* G, VertexType v); //返回顶点 v 在vertex数组中的下标，如果v不存在，返回-1
bool insert_vertex(ListGraph *G, VertexType v);
bool insert_arc(ListGraph *G, VertexType v, VertexType w);

//当成功插入顶点或边时，函数返回true，否则（如顶点或边已存在、插入边时顶点v或w不存在）返回false。

答案

bool insert_vertex(ListGraph* G, VertexType v) {
   
	if (G->vexnum == MAX_VERTEX_NUM)//判断边的数目是否已达最大数量
		return false;
	for (int i = 0;i<G->vexnum;i++) {
   
		if (G->vertex[i].data == v)//判断v是否已在表头结点表中
			return false;
	}
	G->vertex[G->vexnum].data = v;//添加结点
	G->vertex[G->vexnum].firstarc = NULL;
	G->vexnum++;
	return true;
}
bool insert_arc(ListGraph* G, VertexType v, VertexType w) {
   //假设v是弧尾，w是弧头
	int locv = locate_vertex(G, v), locw = locate_vertex(G, w);
	if (locv == -1 || locw == -1)//判断v或w是否不存在
		return false;
	ArcNode* p=G->vertex[locv].firstarc, * p_pre = NULL;
	if