鄰接表 [路徑判斷][最短路徑]
文章目錄
- 鄰接表 [路徑判斷][最短路徑]
- 一、鄰接表是什麼？
- 二、建構圖的鄰接表
-
- 1.建構 圖的鄰接表 函數
- 2.主函數（全代碼）
-
- 輸入格式
- 輸入格式
- 輸入樣例
- 輸出樣例
- 三、可運用鄰接表的題目
-
- ag1：路徑判斷 (20 分)
-
- 輸入格式:
- 輸出格式:
- 輸入樣例1
- 輸出樣例1
- 輸入樣例2
- 輸出樣例2
- 代碼：（用DFS）
- ag2：最短路徑 (20 分)
-
- 輸入格式:
- 輸出格式:
- 輸入樣例1:
- 輸出樣例1:
- 輸入樣例2:
- 輸出樣例2:
- 代碼：（用BFS）
一、鄰接表是什麼？
圖的鄰接表存儲方法跟樹的孩子連結清單示法相類似，是一種順序配置設定和鍊式配置設定相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放于表頭結點所指向的單向連結清單中。
對于無向圖來說，使用鄰接表進行存儲也會出現資料備援，表頭結點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
輸入樣例2
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6
輸出樣例2
代碼：（用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:
輸入樣例2:
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6
輸出樣例2:
代碼：（用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";
}
![[轉]ISUP信令的IAM消息詳細内容[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)