用c语言编写一个函数查找顶点u的第一邻接点,int FirstAdjVex(ALGraph G,KeyType u),u是和G中顶点关键字类型相同的给定值;返回关键字为u的顶点第一个邻接顶点位置序号(简称位序),否则返回-1。
时间: 2024-05-04 18:19:16 浏览: 67
ALGraph是一个邻接表表示的图结构,包含以下定义:
```
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef int KeyType; // 顶点关键字类型
typedef struct ArcNode { // 边结点
int adjvex; // 该边所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条边的指针
// OtherInfo info; // 和边相关的其他信息
} ArcNode;
typedef struct VNode { // 顶点结点
KeyType data; // 顶点关键字信息
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图结构
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
```
函数实现如下:
```
int FirstAdjVex(ALGraph G, KeyType u) {
int i, j;
for (i = 0; i < G.vexnum; i++) { // 查找顶点u的位置序号i
if (G.vertices[i].data == u) {
break;
}
}
if (i == G.vexnum) { // 如果没找到,返回-1
return -1;
}
ArcNode *p = G.vertices[i].firstarc;
if (p != NULL) { // 如果有邻接顶点,返回第一个邻接顶点的位置序号j
j = p->adjvex;
return j;
} else { // 如果没有邻接顶点,返回-1
return -1;
}
}
```
该函数首先查找顶点u的位置序号i,如果没找到返回-1;否则访问顶点i的第一个邻接顶点,返回其位置序号j,如果没有邻接顶点返回-1。
阅读全文