【数据结构】邻接表链式存储
作者:
也许
,
2021-06-24 17:40:07
,
所有人可见
,
阅读 563
//邻接表
//边表节点
typedef struct ArcNode
{
int adjvex; //节点编号
int weight; //边的权重
struct ArcNode* next; //下一个节点指针
}ArcNode;
//顶点表节点
typedef struct VNode
{
VertexType data;
ArcNode* first;
}VNode, AdjList[maxVertexNum];
//图
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
/*
邻接矩阵:空间复杂度高
邻接表:找某一个顶点的入度必须遍历每个顶点的邻接表,时间复杂度高
*/
//从节点a连向节点b的权值为c的边
void add(ALGraph& G, int a, int b, int c)
{
//初始化边节点p
ArcNode* p = (ArcNode*)malloc(sizeof ArcNode);
p->adjvex = b;
p->weight = c;
//将边节点插入到图中
p->next = G.vertices[a].first;
G.vertices[a].first = p;
}
//遍历某个节点的临接点
void travel(ALGraph& G, int u)
{
for (ArcNode* p = G.vertices[u].first; p != NULL; p = p->next)
{
cout << p->adjvex << endl;
}
}