邻接表，图的邻接表

本文目录一览

1，图的邻接表
2，有向图用邻接表如何表示不是程序表示求其详细的过程
3，如何建立邻接表
4，基于邻接表建图的几种方法
5，邻接表做深度优先遍历和广度优先遍历的代码

1，图的邻接表

1.可以。2.如果a->b和b->a均在邻接表里成对存在，则是无向图的邻接表，否则是有向图的邻接表。a和b是图中顶点。

图的邻接表

2，有向图用邻接表如何表示不是程序表示求其详细的过程

第一步：观察图有多少顶点，这里，ABCDE有5个，就划5个顶点的，数组，并在旁边编号01234。第二步：从上到下，依次观察ABCDE这5个结点，首先A结点，它发出2条边B,D，所以把它的指针首先随便指向一个B或者D的编号，这里指向D，因为D的编号是3，然后指向另外的没有指向的编号B,就是了。最后没有边的，指向就是空指针。第三步：依次按照A点的方法，写出BCDE点的指向的边的编号，没有就用空表示。理解的关键。邻接表数据的那个顶点和后面指向的编号的结点，这两个点的意思和写法不同，数组的表示的存储的具体的结点信息，后边的表示它发出的邻近结点的编号，没有其他的结点信息。

节点编号：A~E依次编为0~4：从A点（0）出发的箭头有2根，分别指向B（1）、D（3）节点，用节点号表示为一个链表；其他节点只有一个出边，也是用目标节点的编号表示。

1.可以。2.如果a->b和b->a均在邻接表里成对存在，则是无向图的邻接表，否则是有向图的邻接表。a和b是图中顶点。

有向图用邻接表如何表示不是程序表示求其详细的过程

3，如何建立邻接表

const n=10; e=20; type edge=^edgenode; edgenode=record adj:1..n; weight:integer; next:edge; end; vex=record data:integer; lind:edge; end;var s:edgenode; g=array [1..n] of vex;begin read(n,e); for i:=1 to n do begin read(g[i].data); g[i].link:=nil; end; for k:=1 to e do begin read(i,j,w); new(s); s^.adj:=j; s^.weight:=w; s^.next:=g[i].link; g[i].link:=s; end;end.

邻接表是一个指针数组，数组的每一个元素指向一个链表。比如，在某个图中，点2与点3、点6之间有边，则邻接表的元素a[2]指向一个链表，该链表有2个节点，其数据域分别为3，6

如何建立邻接表

4，基于邻接表建图的几种方法

数据结构书上表示邻接表比较复杂，一般形式如下： typedef struct NodeDataType data; //结点的一些数据，比如名字 int sorce; //邻接边的弧尾结点序号 Edge *adj; //邻接边头指针}AdjHeight; //数组的数据元素类型的结构体typedef structAdjHeight a[MaxVertices]; //邻接表数组 int numOfVerts; //结点个数 int numOfEdges; //边个数}AdjGraph; //邻接表结构体其实有种简洁且高效的表示形式： typedef structint pre[MAX];//初始化memset(pre,-1,sizeof(pre));//输入scanf("%d %d %d",&from,&to,&w1);e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i;i++; 上面这段代码中，边的结构体Edge由三个元素组成：弧头结点序号，边权值，下一条边的序号。e[i]指的是第i条边。pre[i]记录的是从当前输入的情况来看，序号为i的弧尾结点发出的第一条边的序号是pre[i]。这样，在操作某个结点发出的边时，可以像这么做： /*now为弧尾结点序号，i为now所发出的边序号，adj为弧头结点序号，w为now-->adj这条边的权值*/for(i = pre[now]; i != -1; i = edge[i].next)int w = edge[i].w;//do something...} 其实，对于哈希表这类的存储结构(链表法解决冲突)，与图的邻接表类似，也可以用类似的表示方法： typedef structchar e[11]; //value char f[11]; //key int next; //下一个结果(hash冲突)}Entry;Entry entry[M];int hashIndex[M]; //哈希值为M的结果集的第一个在entry中的序号。

5，邻接表做深度优先遍历和广度优先遍历的代码

3、广度优先搜索算法 (1)邻接表表示图的广度优先搜索算法 void BFS(ALGraph*G，int k) int i； CirQueue Q； //须将队列定义中DataType改为int EdgeNode *p； InitQueue(&Q)；//队列初始化 //访问源点vk printf("visit vertex：％e"，G->adjlist[k].vertex)； visited[k]=TRUE； EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q))i=DeQueue(&Q)； //相当于vi出队 p=G->adjlist[i].firstedge； //取vi的边表头指针 while(p)if(!visited[p->adivex])printf("visitvertex：％c"，C->adjlistlp->adjvex].vertex)； //访问vj visited[p->adjvex]=TRUE； EnQueue(&Q，p->adjvex)；//访问过的vj人队 }//endif p=p->next；//找vi的下一邻接点 }//endwhile }//endwhile }//end of BFS （2）邻接矩阵表示的图的广度优先搜索算法 void BFSM(MGraph *G，int k) int i，j； CirQueue Q； InitQueue(&Q)； printf("visit vertex：％c"，G->vexs[k])； //访问源点vk visited[k]=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q))i=DeQueue(&Q)； //vi出队 for(j=0;j<G->n;j++)//依次搜索vi的邻接点vj if(G->edges[i][j]==1&&!visited[j])printf("visit vertex：％c"，G->vexs[j])；//访问vi visited[j]=TRUE； EnQueue(&Q，j)；//访问过的vi人队 } }//endwhile }//BFSM

（1）图的建立，按采用邻接表作为存储结构。（2）从指定顶点出发进行深度优先搜索遍历。（3）从指定顶点出发进行广度优先搜索遍历。#include"stdio.h"#include"string.h"#include"stdlib.h"#include"math.h"#define max_int 1000#define max_vertex_num 20#define max_queue_number 20typedef struct arcnode int adjvex; double adj; struct arcnode *nextarc;}arcnode;typedef struct vexnode char szname[40]; arcnode *firstarc;}vexnode,adjlist[max_vertex_num];typedef struct adjlist vexs; int vexnum,arcnum;}net;//定义队列typedef struct int *elem; int front, rear;}queue;void initqueue(queue &q) q.elem = new int[max_queue_number]; q.front = q.rear = 0;}int emptyqueue(queue q) if(q.front==q.rear) return 0; else return 1;}void destroyqueue(queue &q) delete []q.elem; q.front = q.rear = 0;}void enterqueue(queue &q, int e) if((q.rear + 1)%max_queue_number != q.front) q.elem[q.rear ] = e; else printf("队列满!\n"); q.rear = (q.rear + 1)%max_queue_number;}void leavequeue(queue &q, int &e) if(q.rear != q.front) e = q.elem[q.front]; else printf("队列空!\n"); q.front = (q.front+1)%max_queue_number;}int locatevex(net ga,char *name) int i; for(i=0;i if(strcmp(name,ga.vexs[i].szname)==0) return i; return -1;}void crt_net(net &ga) arcnode *p; char name1[40],name2[40]; int i,j,k; double w; printf("请输入顶点数和弧数："); scanf("%d%d",&ga.vexnum,&ga.arcnum); printf("请依次输入顶点名：\n"); for(i=0;i scanf("%s",ga.vexs[i].szname); ga.vexs[i].firstarc=null; } for(k=0;k printf("请输入相邻的两个定点和权值："); scanf("%s%s%lf",name1,name2,&w); i=locatevex(ga,name1); j=locatevex(ga,name2); p=new arcnode; p->adjvex=j; p->adj=w; p->nextarc=ga.vexs[i].firstarc; ga.vexs[i].firstarc=p; }}void dfs(net ga,char *name,int *visited) int v,w; arcnode *p; v=locatevex(ga,name); visited[v]=1; printf("%s ",ga.vexs[v].szname); p=ga.vexs[v].firstarc; while(p!=null) w=p->adjvex; if(visited[w]==0) dfs(ga,ga.vexs[w].szname,visited); p=p->nextarc; }}void dfstravel(net ga,char *name) int v,k=0; int visited[20]; for(v=0;v visited[v]=0; for(v=locatevex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1)) if(v+1==locatevex(ga,name)) k++; if(visited[v]==0) dfs(ga,ga.vexs[v].szname,visited); }}void bfstravel(net ga,char *name) arcnode *p; int v,w,u,k=0; queue q; int visited[20]; for(v=0;v visited[v]=0; initqueue(q); for(v=locatevex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1)) if(v+1==locatevex(ga,name)) k++; if(visited[v]==0) visited[v]=1; printf("%s ",ga.vexs[v].szname); enterqueue(q,v); while(emptyqueue(q)!=0) leavequeue(q,u); p=ga.vexs[u].firstarc; while(p!=null) w=p->adjvex; if(visited[w]==0) printf("%s ",ga.vexs[w].szname); visited[w]=1; enterqueue(q,w); } p=p->nextarc; } } } }}void main() char name[40]; net ga; crt_net(ga); printf("请输入深度优先遍历开始点的名："); scanf("%s",name); printf("深度优先遍历："); dfstravel(ga,name); printf("\n"); printf("请输入广度优先遍历开始点的名："); scanf("%s",name); printf("广度优先遍历："); bfstravel(ga,name); printf("\n");}