邻接表 [路径判断][最短路径]
一、邻接表是什么？
图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。
在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。
在无向图中，描述每个点所有的边(点a-点b这种情况)
二、构建图的邻接表
1.构建 图的邻接表 函数
//构建图的邻接表 PtrToGNode BuildGraph() { PtrToGNode Graph;//指向邻接表的指针 int v,w; int Nv;//顶点个数 cin>>Nv; Graph = CreateGraph(Nv); cin>>Graph->Ne; if(Graph->Ne != 0){ for(int i=0;i<Graph->Ne;i++) { cin>>v>>w; InsertEdge(Graph,v,w); } } return Graph;//指针 返回建好的邻接表 }
2.主函数（全代码）
打印邻接表，各个顶点的邻居有谁 格式：顶点编号->邻居1的编号->邻居2的编号
输入格式
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。
随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式
顶点 边数
N,E
格式：顶点编号->邻居1的编号->邻居2的编号
输入样例
7 6 0 1 2 3 1 4 0 2 1 3 5 6
输出样例
顶点 边数 7 6 0->2->1 1->3->4->0 2->0->3 3->1->2 4->1 5->6 6->5
代码如下：
#include <bits/stdc++.h> using namespace std; typedef struct AdjVNode *PtrToAdjVNode; //邻居//邻接点 struct AdjVNode{ int AdjV; //邻居顶点编号 PtrToAdjVNode Next; //下一个邻居 }; typedef struct VNode { //指针里面的元素 PtrToAdjVNode FirstEdge; //指向邻居链表的指针 }AdjList[100]; typedef struct GNode *PtrToGNode; struct GNode{ int Nv;//顶点 int Ne;//边的数量 AdjList G;//邻接表//等同于struct VNode G[100]; }; //生成顶点数组 PtrToGNode CreateGraph(int Nv) { PtrToGNode Graph; Graph =new GNode(); Graph->Nv = Nv; Graph->Ne = 0; for(int v=0;v<Nv;v++) { Graph->G[v].FirstEdge = NULL; } return Graph; } //在无向图内加入一条边 (v, w) void InsertEdge(PtrToGNode Graph, int v, int w) { PtrToAdjVNode newNode; newNode = new AdjVNode(); newNode->AdjV = w;//记住v的邻居是w w是v的邻居 AdjV是记录值 Next是记录指针 //把newNode插入到顶点v的邻居（链表）内 newNode->Next = Graph->G[v].FirstEdge; Graph->G[v].FirstEdge = newNode; newNode = new AdjVNode(); newNode->AdjV = v;//记住w的邻居是v v是w的邻居 //把newNode插入到顶点w的邻居（链表）内 newNode->Next = Graph->G[w].FirstEdge; Graph->G[w].FirstEdge = newNode; } //构建图的邻接表 PtrToGNode BuildGraph() { PtrToGNode Graph;//指向邻接表的指针 int v,w; int Nv;//顶点个数 cin>>Nv; Graph = CreateGraph(Nv); cin>>Graph->Ne; if(Graph->Ne != 0){ for(int i=0;i<Graph->Ne;i++) { cin>>v>>w; InsertEdge(Graph,v,w); } } return Graph;//指针 返回建好的邻接表 } bool visited[100]={false};//visited数组记住哪些顶点已经被记住 void DFS(PtrToGNode graph,int start) { visited[start]= true; for(PtrToAdjVNode w=graph->G[start].FirstEdge;w!=NULL;w=w->Next) { if(!visited[w->AdjV]) DFS(graph,w->AdjV); } } int main() { PtrToGNode graph = BuildGraph(); cout<<"顶点 边数"<<endl; // cout<<graph->Nv<<","<<graph->Ne; printf("%4d %4d",graph->Nv,graph->Ne) ; // 打印邻接表，各个顶点的邻居有谁 //格式：顶点编号->邻居1的编号->邻居2的编号 cout<<endl; for(int i=0;i<graph->Nv;i++) { cout<<i; PtrToAdjVNode ptr = graph->G[i].FirstEdge; while(ptr != NULL) { cout<<"->"<<ptr->AdjV; ptr = ptr->Next; } cout<<endl; } }
三、可运用邻接表的题目
ag1：路径判断 (20 分)
给定一个有N个顶点和E条边的无向图，请判断给定的两个顶点之间是否有路径存在。 假设顶点从0到N−1编号。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。
随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
最后一行给出两个顶点编号i，j（0≤i,j<N）,i和j之间用空格分隔。
输出格式:
如果i和j之间存在路径，则输出"There is a path between i and j.“，
否则输出"There is no path between i and j.”。
输入样例1
7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 3
输出样例1
There is a path between 0 and 3.
输入样例2
7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 6
输出样例2
There is no path between 0 and 6.
代码：（用DFS）
#include <bits/stdc++.h> using namespace std; typedef struct AdjVNode *PtrToAdjVNode; //邻居//邻接点 struct AdjVNode{ int AdjV; //邻居顶点编号 PtrToAdjVNode Next; //下一个邻居 }; typedef struct VNode { //指针里面的元素 PtrToAdjVNode FirstEdge; //指向邻居链表的指针 }AdjList[100]; typedef struct GNode *PtrToGNode; struct GNode{ int Nv;//顶点 int Ne;//边的数量 AdjList G;//邻接表//等同于struct VNode G[100]; }; //生成顶点数组 PtrToGNode CreateGraph(int Nv) { PtrToGNode Graph; Graph =new GNode(); Graph->Nv = Nv; Graph->Ne = 0; for(int v=0;v<Nv;v++) { Graph->G[v].FirstEdge = NULL; } return Graph; } //在无向图内加入一条边 (v, w) void InsertEdge(PtrToGNode Graph, int v, int w) { PtrToAdjVNode newNode; newNode = new AdjVNode(); newNode->AdjV = w;//记住v的邻居是w w是v的邻居 AdjV是记录值 Next是记录指针 //把newNode插入到顶点v的邻居（链表）内 newNode->Next = Graph->G[v].FirstEdge; Graph->G[v].FirstEdge = newNode; newNode = new AdjVNode(); newNode->AdjV = v;//记住w的邻居是v v是w的邻居 //把newNode插入到顶点w的邻居（链表）内 newNode->Next = Graph->G[w].FirstEdge; Graph->G[w].FirstEdge = newNode; } //构建图的邻接表 PtrToGNode BuildGraph() { PtrToGNode Graph;//指向邻接表的指针 int v,w; int Nv;//顶点个数 cin>>Nv; Graph = CreateGraph(Nv); cin>>Graph->Ne; if(Graph->Ne != 0){ for(int i=0;i<Graph->Ne;i++) { cin>>v>>w; InsertEdge(Graph,v,w); } } return Graph;//指针 返回建好的邻接表 } bool visited[100]={false};//visited数组记住哪些顶点已经被记住 void DFS(PtrToGNode graph,int start) { visited[start]= true; for(PtrToAdjVNode w=graph->G[start].FirstEdge;w!=NULL;w=w->Next) { if(!visited[w->AdjV]) DFS(graph,w->AdjV); } } int main() { PtrToGNode graph = BuildGraph(); // cout<<"顶点 边数"<<endl; cout<<graph->Nv<<","<<graph->Ne; // printf("%4d %4d",graph->Nv,graph->Ne) ; // 打印邻接表，各个顶点的邻居有谁 //格式：顶点编号->邻居1的编号->邻居2的编号 // cout<<endl; // for(int i=0;i<graph->Nv;i++) // { // cout<<i; // PtrToAdjVNode ptr = graph->G[i].FirstEdge; // while(ptr != NULL) // { // cout<<"->"<<ptr->AdjV; // ptr = ptr->Next; // } // cout<<endl; // } int start, end; cin>>start>>end; DFS(graph, start); if(visited[end]) cout<<"There is a path between "<<start<<" and "<<end<<".\n"; else cout<<"There is no path between "<<start<<" and "<<end<<".\n"; }
其他方法解题
#include<stdio.h> #include<stdlib.h> #define MaxVertexNum 10 /* 最大顶点数设为10 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ int g[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */ int isvisited[20]; void DFS( MGraph Graph, int V) { isvisited[V] = 1; for(int j=0;j<Graph->Nv;j++) { int w = Graph->g[V][j]; if(w != 0 && !isvisited[j]) { DFS(Graph,j); } } } int main() { PtrToGNode G = (PtrToGNode)malloc(sizeof(struct GNode)); scanf("%d %d",&G->Nv,&G->Ne); int x,y; for(int i=0;i<G->Nv;i++) { isvisited[i] = 0; for(int j=0;j<G->Nv;j++) { G->g[i][j] = 0; } } for(int i=0;i<G->Ne;i++) { scanf("%d %d",&x,&y); G->g[x][y] = 1; G->g[y][x] = 1; } scanf("%d %d",&x,&y); DFS(G,x); if(isvisited[y] == 1) { printf("There is a path between %d and %d.",x,y); } else { printf("There is no path between %d and %d.",x,y); } return 0; }
ag2：最短路径 (20 分)
给定一个有N个顶点和E条边的无向图，顶点从0到N−1编号。请判断给定的两个顶点之间是否有路径存在。如果存在，给出最短路径长度。 这里定义顶点到自身的最短路径长度为0。 进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。
随后E行，每行给出一条边的两个顶点。每行中的数字之间用1空格分隔。
最后一行给出两个顶点编号i，j（0≤i,j<N）,i和j之间用空格分隔。
输出格式:
如果i和j之间存在路径，则输出"The length of the shortest path between i and j is X."
X为最短路径长度， 否则输出"There is no path between i and j."。
输入样例1:
7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 3
输出样例1:
There is no path between 0 and 6.
输入样例2:
7 6 0 1 2 3 1 4 0 2 1 3 5 6 0 6
输出样例2:
There is no path between 0 and 6.
代码：（用BFS）
#include <bits/stdc++.h> using namespace std; typedef struct AdjVNode * PtrToAdjVNode; //邻接点 struct AdjVNode{ int AdjV; //邻居顶点编号 PtrToAdjVNode Next; //下一个邻居 }; typedef struct VNode { PtrToAdjVNode FirstEdge; //指向邻居链表的指针 } AdjList[100]; //AdjList是struct VNode[]，是数组类型 typedef struct GNode * PtrToGNode; struct GNode { int Nv; int Ne; //边数 //AdjList G; //等同于struct VNode G[100] struct VNode G[100]; }; //生成0条边的邻接表 PtrToGNode CreateGraph(int Nv) { PtrToGNode Graph; Graph =new GNode(); Graph->Nv = Nv; Graph->Ne = 0; for(int v=0; v<Nv; v++) { Graph->G[v].FirstEdge = NULL; } return Graph; } //在无向图内加入一条边 (v, w) void InsertEdge(PtrToGNode Graph, int v, int w) { PtrToAdjVNode newNode; newNode = new AdjVNode(); //邻接点 newNode->AdjV = w; //记住w是v的邻居 //把newNode插入到顶点v的邻居（链表）内 newNode->Next = Graph->G[v].FirstEdge; Graph->G[v].FirstEdge = newNode; newNode = new AdjVNode(); newNode->AdjV = v; //记住v是w的邻居 //把newNode插入到顶点w的邻居（链表）内 newNode->Next = Graph->G[w].FirstEdge; Graph->G[w].FirstEdge = newNode; } //构建图的邻接表 PtrToGNode BuildGraph() { PtrToGNode Graph; //指向邻接表的指针 int v, w; int Nv; cin>>Nv; Graph = CreateGraph(Nv); cin>>Graph->Ne; if(Graph->Ne != 0) { for(int i=0; i<Graph->Ne; i++) { cin>>v>>w; InsertEdge(Graph, v, w); } } return Graph; } int distances[100] = {0}; void BFS(PtrToGNode graph, int start) { queue<int> vnodes; vnodes.push(start); distances[start] = 0; while(!vnodes.empty()) { int v = vnodes.front(); vnodes.pop(); for(PtrToAdjVNode w=graph->G[v].FirstEdge; w!=NULL; w=w->Next) { if(distances[w->AdjV] < 0) { distances[w->AdjV] = distances[v] + 1; vnodes.push(w->AdjV); } } } return; } int main() { PtrToGNode graph = BuildGraph(); int start, end; cin>>start>>end; for(int i=0; i<100; i++) { distances[i] = -1; } BFS(graph, start); if (start == end) cout<<"The length of the shortest path between "<<start<<" and "<<end<<" is 0.\n"; else if(distances[end] > 0) cout<<"The length of the shortest path between "<<start<<" and "<<end<<" is "<<distances[end]<<".\n"; else cout<<"There is no path between "<<start<<" and "<<end<<".\n"; }
