首页 / 软件开发 / 数据结构与算法 / 图的存储形式：邻接表

图的存储形式：邻接表2015-09-16邻接表：邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点有三个域组成，其中邻接点域指示与顶点vi邻接的点在途中的位置，链域指示下一条边或者弧的结点；数据域存储和边或者弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设置链域指向链表第一个结点之外，还设置有存储顶点vi的名。如下所示：

实现：

/************************************** 图的存储之邻接表 by Rowandjj 2014/6/23 **************************************/#include<iostream>using namespace std;#define MAX_VERTEX_NUM 20//最大顶点数typedef enum{DG,DN,AG,AN}GraphKind;//有向图、有向网、无向图、无向网typedef struct _ARCNODE_//表节点（弧）{int adjvex;//邻接点序号struct _ARCNODE_ *nextarc;//指向下一条弧int info;//信息（权值）}ArcNode;typedef struct _VNODE_//头结点{char data;//顶点名ArcNode *firstarc;//指向第一条弧}VNode,AdjList[MAX_VERTEX_NUM];typedef struct _ALGRAPH_//邻接表{AdjList vertices;//邻接表int vexnum;//顶点数int arcnum;//弧数GraphKind kind;//图的种类}ALGraph;void （*VisitFunc）（char）;//全局函数指针 bool visited[MAX_VERTEX_NUM]; /* 访问标志数组（全局量） */void Visit（char p）{cout<<p<<" ";}//-----------------操作-------------------------------------//int LocateVex（ALGraph G,char u）;//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1bool CreateGraph（ALGraph* G）;//采用邻接表存储结构,构造没有相关信息的图G（用一个函数构造4种图）void DestroyGraph（ALGraph* G）;//销毁图Gchar GetVex（ALGraph G,int v）;//通过序号v得到顶点名bool PutVex（ALGraph* G,char v,char value）;//对v赋新值valueint FirstAdjVex（ALGraph G,char v）;//返回顶点v的第一个邻接顶点的序号int NextAdjVex（ALGraph G,char v,char w）;//返回v的（相对于w的）下一个邻接顶点的序号,若w是v的最后一个邻接点,则返回-1void InsertVex（ALGraph* G,char v）;//在图G中增添新顶点v（不增添与顶点相关的弧,留待InsertArc（）去做） bool DeleteVex（ALGraph* G,char v）;//删除G中顶点v及其相关的弧bool InsertArc（ALGraph* G,char v,char w）;//在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>bool DeleteArc（ALGraph* G,char v,char w）;//在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>void DFSTravel（ALGraph* G,void （*Visit）（char））;//深度优先void DFS（ALGraph G,int v）;void BFSTravel（ALGraph G,void （*Visit）（char））;//广度优先void Display（ALGraph G）;//打印图//----------------辅助队列------------------------------------------#define MAX_QUEUE_SIZE 20typedef struct _QUEUENODE_{int data;struct _QUEUENODE_ *next;}QueueNode;typedef struct _QUEUE_{QueueNode *pHead;QueueNode *pTail;int size;}Queue;bool InitQueue（Queue *Q）;bool DestroyQueue（Queue *Q）;bool DeQueue（Queue *Q,int* e）;bool EnQueue（Queue *Q, int e）;bool QueueEmpty（Queue Q）;//------------------------------------------------------------------bool InitQueue（Queue *Q）{Q->pHead = Q->pTail = （QueueNode *）malloc（sizeof（QueueNode））;if（！Q->pHead）{return false;}Q->pHead->next = NULL;Q->size = 0;return true;}bool EnQueue（Queue *Q, int e）{QueueNode *node = （QueueNode*）malloc（sizeof（QueueNode））;node->data = e;node->next = NULL;Q->pTail->next = node;Q->pTail = node;Q->size++;return true;}bool DeQueue（Queue *Q,int* e）{QueueNode *node = Q->pHead->next;if（node）{*e = node->data;Q->pHead->next = node->next;if（Q->pTail == node）{Q->pTail = Q->pHead;}free（node）;Q->size--;}return true;}bool QueueEmpty（Queue Q）{return Q.size == 0;}bool DestroyQueue（Queue *Q）{QueueNode *pTemp = Q->pHead->next;while（pTemp ！= NULL）{Q->pHead->next = pTemp->next;free（pTemp）;pTemp = Q->pHead->next;}free（Q->pHead）;Q->size = 0;return true;}//------------------------------------------------------------------int LocateVex（ALGraph G,char u）{int i;for（i = 0; i < G.vexnum; i++）{if（u == G.vertices[i].data）{return i;}}return -1;}bool CreateGraph（ALGraph* G）{int i,j,k;int w;//权值char va,vb;//弧尾、弧头ArcNode *p;//弧cout<<"请输入图的类型（有向图:0,有向网:1,无向图:2,无向网:3）: ";scanf（"%d",&（*G）.kind）;cout<<"请输入图的顶点数,边数: ";cin>>G->vexnum;cin>>G->arcnum;cout<<"请输入顶点值:"<<endl;//构造顶点for（i = 0; i < G->vexnum; i++）{cin>>G->vertices[i].data;G->vertices[i].firstarc = NULL;}if（G->kind == 1 || G->kind == 3）//网{cout<<"请顺序输入每条弧（边）的权值、弧尾和弧头:
";}else//图{cout<<"请顺序输入每条弧（边）的弧尾和弧头
";}//构造表节点链表for（k = 0; k < G->arcnum; k++）{if（G->kind == 1 || G->kind == 3）//网{cin>>w;cin>>va;cin>>vb;}else//图{cin>>va;cin>>vb;}//定位弧尾弧头的位置i = LocateVex（*G,va）;j = LocateVex（*G,vb）;p = （ArcNode *）malloc（sizeof（ArcNode））;p->adjvex = j;if（G->kind == 1 || G->kind == 3）//网{p->info = w;//权值}else{p->info = NULL;}//插入表p->nextarc = G->vertices[i].firstarc;//插在表头G->vertices[i].firstarc = p;//如果是无向图或者无向网，还需要增加对称结点if（G->kind == 2 || G->kind == 3）{p = （ArcNode *）malloc（sizeof（ArcNode））;p->adjvex = i;if（G->kind == 3）//若是无向网，还需要权值{p->info = w;}else{p->info = NULL;}//插入表p->nextarc = G->vertices[j].firstarc;G->vertices[j].firstarc = p;}}return true;}void Display（ALGraph G）{ArcNode *p;int i;switch（G.kind）{case DG:cout<<"有向图";break;case AG:cout<<"无向图";break;case DN:cout<<"有向网";break;case AN:cout<<"无向网";break;default:break;}cout<<endl;cout<<"顶点:"<<endl;for（i = 0; i < G.vexnum; i++）{cout<<G.vertices[i].data<<" ";}cout<<endl;//边cout<<"边:"<<endl;for（i = 0; i < G.vexnum; i++）{p = G.vertices[i].firstarc;while（p）{if（G.kind == 0 || G.kind == 1）//有向{cout<<G.vertices[i].data<<" "<<G.vertices[p->adjvex].data;if（G.kind == 1）//有向网{cout<<" "<<p->info;}}else//无向{if（i < p->adjvex）//不重复打印{cout<<G.vertices[i].data<<" "<<G.vertices[p->adjvex].data;if（G.kind == 3）//无向网{cout<<" "<<p->info;}}}cout<<endl;p = p->nextarc;}}}void DestroyGraph（ALGraph* G）{ArcNode *p,*q;int i;for（i = 0; i < G->vexnum; i++）{p = G->vertices[i].firstarc;while（p）{q = p->nextarc;free（p）;p = q;}}G->arcnum = 0;G->vexnum = 0;}char GetVex（ALGraph G,int v）{if（v>=G.vexnum || v<0）{exit（0）;}return G.vertices[v].data;}bool PutVex（ALGraph* G,char v,char value）{int i = LocateVex（*G,v）;if（i == -1）{return false;}G->vertices[i].data = value;return true;}int FirstAdjVex（ALGraph G,char v）{int i = LocateVex（G,v）;if（i < 0）{return -1;}ArcNode *arcNode = G.vertices[i].firstarc;if（arcNode == NULL）{return -1;}return arcNode->adjvex;}int NextAdjVex（ALGraph G,char v,char w）{int i,j;i = LocateVex（G,v）;j = LocateVex（G,w）;ArcNode *p = G.vertices[i].firstarc;while（p && p->adjvex ！= j）{p = p->nextarc;}if（！p || ！p->nextarc）//没找到w或w是最后一个邻接点{return -1;}else{return p->nextarc->adjvex;}}void InsertVex（ALGraph* G,char v）{G->vertices[G->vexnum].data = v;G->vertices[G->vexnum].firstarc = NULL;G->vexnum++;}bool DeleteVex（ALGraph* G,char v）{int i,j;ArcNode *p,*q;//1.删除邻接表中顶点为v的那一行所有数据，更改弧总数,顶点总数i = LocateVex（*G,v）;if（i < 0 || i >= G->vexnum）//不合法的位置{return false;}p = G->vertices[i].firstarc;while（p）//依次删除弧{q = p->nextarc;free（p）;p = q;G->arcnum--;}G->vexnum--;//2.更改顶点v之后的顶点在数组中的位置（前移一位）for（j = i; j < G->vexnum; j++）{G->vertices[j] = G->vertices[j+1];}//3.遍历剩下的邻接表,找到包含顶点v的弧或者边，删除之。另外需要注意，对遍历的每个弧/边，视情况更新序号for（j = 0; j < G->vexnum; j++）{p = G->vertices[j].firstarc;//p指向遍历的顶点的第一条弧或者边while（p）{if（p->adjvex == i）//如果找到指向已删除顶点的弧或者边{if（p == G->vertices[j].firstarc）//如果待删除的结点是第一个结点{G->vertices[j].firstarc = p->nextarc;free（p）;p = G->vertices[j].firstarc;if（G->kind <= 1）//如果是有向的，则还需更改弧数{G->arcnum--;}}else//不是第一个结点{q->nextarc = p->nextarc;free（p）;p = q->nextarc;if（G->kind <= 1）//如果是有向的，则还需更改弧数{G->arcnum--;}}}else//如果当前弧并不是要找的弧，那么继续向后遍历{if（p->adjvex > i）//（很关键）更新序号{p->adjvex--;}q = p;p = p->nextarc;//指向下一条弧}}}return true;}bool InsertArc（ALGraph* G,char v,char w）{int i,j,weight;ArcNode *arcNode;//1.得到v、w的在邻接表中的序号i = LocateVex（*G,v）;j = LocateVex（*G,w）;if（i<0 || j<0）{return false;}G->arcnum++;if（G->kind == 1 || G->kind == 3）{cout<<"输入权值:";cin>>weight;//输入权值}//2.生成一个弧结点，插入到顶点v的第一个邻接点的位置（如果是网的话，需要用户输入权值）arcNode = （ArcNode*）malloc（sizeof（ArcNode））;arcNode->adjvex = j;if（G->kind == 1 || G->kind == 3）{arcNode->info = weight;}else{arcNode->info = NULL;}arcNode->nextarc = G->vertices[i].firstarc;G->vertices[i].firstarc = arcNode;//3.如果是无向的，那么还需生成对称节点，并插到合适位置if（G->kind >= 2）{arcNode = （ArcNode *）malloc（sizeof（ArcNode））;arcNode->adjvex = i;if（G->kind == 3）//无向网{arcNode->info = weight;}else{arcNode->info = NULL;}arcNode->nextarc = G->vertices[j].firstarc;G->vertices[j].firstarc = arcNode;}return true;}bool DeleteArc（ALGraph* G,char v,char w）{int i,j;ArcNode *p,*q;//1.得到v、w的在邻接表中的序号i = LocateVex（*G,v）;j = LocateVex（*G,w）;if（i < 0 || j < 0）{return false;}//2.删除v-wp = G->vertices[i].firstarc;while（p && p->adjvex！=j）{q = p;p = p->nextarc;}if（p && p->adjvex==j）//找到弧<v-w>{if（p == G->vertices[i].firstarc）//p指的是第一条弧{G->vertices[i].firstarc = p->nextarc;}else{q->nextarc = p->nextarc;}free（p）;G->arcnum--;}//3.若是无向，则还删除w-vif（G->kind >= 2）{p = G->vertices[j].firstarc;while（p && p->adjvex！=i）{q = p;p = p->nextarc;}if（p && p->adjvex==i）//找到弧<w-v>{if（p == G->vertices[j].firstarc）//p指的是第一条弧{G->vertices[j].firstarc = p->nextarc;}else{q->nextarc = p->nextarc;}free（p）;}}return true;}void DFSTravel（ALGraph* G,void （*Visit）（char））{int i;VisitFunc = Visit;for（i = 0; i < G->vexnum; i++）{visited[i] = false;}for（i = 0; i < G->vexnum; i++）{if（！visited[i]）{DFS（*G,i）;}}cout<<endl;}void DFS（ALGraph G,int v）{int i;char v1,w1;v1 = GetVex（G,v）;visited[v] = true;VisitFunc（G.vertices[v].data）;for（i = FirstAdjVex（G,v1）;i>=0; i = NextAdjVex（G,v1,w1 = GetVex（G,i）））{if（！visited[i]）{DFS（G,i）;}}}void BFSTravel（ALGraph G,void （*Visit）（char））{Queue q;InitQueue（&q）;char w1,u1;int i,u,w;for（i = 0; i < G.vexnum; i++）{visited[i] = false;}for（i = 0; i < G.vexnum; i++）{if（！visited[i]）{visited[i] = true;Visit（G.vertices[i].data）;EnQueue（&q,i）;while（！QueueEmpty（q））{DeQueue（&q,&u）;u1 = GetVex（G,u）;for（w = FirstAdjVex（G,u1）;w>=0;w = NextAdjVex（G,u1,w1=GetVex（G,w）））{if（！visited[w]）{visited[w] = true;Visit（G.vertices[w].data）;EnQueue（&q,w）;}}}}}DestroyQueue（&q）;cout<<endl;}int main（）{ALGraph graph;CreateGraph（&graph）;Display（graph）;cout<<"深度优先:"<<endl;DFSTravel（&graph,Visit）;cout<<"广度优先:"<<endl;BFSTravel（graph,Visit）;DestroyGraph（&graph）;return 0;}