1.定义图的邻接表存储表示（ALGraph）
2.采用邻接表表示法创建无向图（CreateUDG）
3.输出所建图的邻接表（PrintALGraph）
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; #define MaxInt 32767 //表示极大值，即∞ #define MVNum 100 //最大顶点数 typedef int VerTexType;//假设顶点的数据类型为整型 typedef int ArcType; //假设边的权值类型为整型 //---------------------图的邻接表存储表示----------------------------// typedef struct ArcNode{ //边结点 int adjvex; //该边所指向的顶点的位置 struct ArcNode * nextarc; //指向下一条边的指针 //OtherInfo info; //和边相关的信息 }ArcNode; typedef struct VNode{ // 顶点信息 VerTexType data; ArcNode *firstarc; //指向第一条依附该顶点的边的指针 }VNode,AdjList[MVNum]; //AdjList 表示邻接表类型 typedef struct{ //邻接表 AdjList vertices; int vexnum,arcnum; //图的当前顶点数，边数 }ALGraph; int LocateVex(ALGraph G,VerTexType v){ for(int i=0;i<G.vexnum;i++){ if(v==G.vertices[i].data){ return i; } } } int CreateUDG(ALGraph &G){ int v1,v2; ArcNode *p2; ArcNode *p1; cin>>G.vexnum>>G.arcnum; //输入总顶点数，边数 for(int i=0;i<G.vexnum;i++){ //输入各点，构造表头结点表 cin>>G.vertices[i].data; //输入顶点值 G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL } for(int k=0;k<G.arcnum;k++){ //输入各边，构造邻接表 cin>>v1>>v2; //输入一条边依附的两个顶点 int i=LocateVex(G,v1);int j=LocateVex(G,v2); p1=new ArcNode; //生成一个新边结点 *p1 p1->adjvex=j; //邻接点序号为 j p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1; p2=new ArcNode; //生成一个对称新边结点 *p2 p2->adjvex=i; //邻接点序号为 i p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2; } return OK; } int PrintAMGraph(ALGraph &G){ ArcNode *temp; if(G.vexnum==0){ cout<<"图为空"<<endl; return 0; } for(int i=0;i<G.vexnum;i++){ temp =G.vertices[i].firstarc; while(temp){ printf("%d->",temp->adjvex); temp=temp->nextarc; } cout<<"NULL"<<endl; } } int main(){ ALGraph G; CreateUDG(G); PrintAMGraph(G); }
