邻接表存储无向图

设无向图G有n个顶点，m条边。试编写用连接表存储该图的算法。

思想：对图中的每个顶点vi建立一个单链表。第i个单链表中的结点表示依附于顶点vi的边，这个单链表就称为顶点vi的边表，边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。

代码：

typedef char GElemType;
typedef struct ArcNode{
 int adjvex;  //该边所指向的顶点的位置 
 struct ArcNode *next;//指向下一条边的指针 
}ArcNode;

//顶点的结点结构 
typedef struct VNode{
 GElemType data;//顶点信息、
 ArcNode *first;//指向第一条依附该顶点的边的指针 
}VNode,AdjList[MVNum];//AdjList表示邻接表类型

//图的结构定义 
typedef struct{
 VNode *vertices; //定义一个数组vertices,是vertex的复数形式
 int vexNum,arcNum; //图的当前顶点数和弧数
}ALGraph;

typedef struct{
GElemType a,b;
}Edge;

//返回结点对应的数组下标
//V[]；结点数组，data：需要查询的结点值，n：数组长度 
int GraphLocateVertex(VNode v[],GElemType data,int n){
for(int i=0;i<n;i++){
if(v[i].data==data) return i;
}
return -1;
}

//numV:顶点数， numEdges：边数， nodes：顶点序列， edges：边序列 
ALGraph* buildAdjacencyList(int numV,int numEdges,GElemType *nodes,Edge *edges){
ALGraph *G=(ALGraph*)malloc(sizeof(ALGraph));//定义图

G->arcNum = numEdges; //边数
G->vexNum numV; //顶点数

G->vertices = (VNode*)malloc(sizeof(VNode));//初始化顶点
for(int i=0;i<numV,i++){//输入顶点信息 
G->vertices[i].data= nodes[i];//输入顶点值 
G->vertices[i].first= NULL ;//初始化表头结点的指针域
} 

for(int k=0;k<numEdges;k++){//处理边 
//获取顶点对应的数组下标
int i = GraphLocateVertex(G->vertices,edges[k].a,numV);
int j = GraphLocateVertex(G->vertices,edges[k].b,numV);

ArcNode* arcb = (ArcNode*)malloc(sizeof(ArcNode));//声明表顶点，存b
arcb->adjvex=j;//设置邻接顶点
arcb->next=G-vertices[i].first;//头插法插到表i中
G->vertices[i].first=arcb;

ArcNode* arca = (ArcNode*)malloc(sizeof(ArcNode));//声明表顶点，存a
arca->adjvex=i;//设置邻接顶点
arca->next=G-vertices[j].first;//头插法插到表i中
G->vertices[j].first=arca;
 
} 
return G;
}

原文地址：https://blog.csdn.net/m0_56332819/article/details/142790982

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！