一個不知名大學生，江湖人稱菜狗
original author: jacky Li
Email : 3435673055@qq.com
Time of completion：2022.12.6
Last edited: 2022.12.6
算法6.1-6.2創(chuàng)建無向網(wǎng)
第1關(guān)：算法6.1鄰接矩陣
任務(wù)描述
本關(guān)任務(wù)：編寫一個能輸出無向圖鄰接矩陣的小程序。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：1.創(chuàng)建鄰接矩陣
編程要求
根據(jù)提示，在右側(cè)編輯器補充代碼，輸出鄰接矩陣。
輸入說明
第一行是頂點數(shù)目n和邊數(shù)目e，中間以空格分開 第二行是n個字符型的頂點數(shù)目名稱，中間以空格分開 接下來e行分別是對應(yīng)的邊 比如說 A B 400 表示頂點A和B之間有邊，權(quán)值為400
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
4 5
A B C D
A B 100
A C 200
B C 300
B D 400
C D 500
預(yù)期輸出：
∞ 100 200 ∞
100 ∞ 300 400
200 300 ∞ 500
∞ 400 500 ∞
參考代碼
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "1"
//#define NO cout << "0"
#define MaxInt 0x3f
#define MVNum 100
#define OK 1
#define ERROR 0
const int N = 1003;
using namespace std;
typedef long long LL;
typedef struct
{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum, arcnum;
}AMGraph;
int LocateVex(AMGraph G , char v) //確定點v在G中的位置
{
for(int i = 1; i <= G.vexnum; i ++)
if(G.vexs[i] == v)
return i;
return -1;
}
int CreateUDN(AMGraph &G)
{
cin >> G.vexnum >> G.arcnum;
for(int i = 1; i <= G.vexnum; i ++)
cin >> G.vexs[i];
for(int i = 1; i <= G.vexnum; i ++)
for(int j = 1; j <= G.vexnum; j ++)
G.arcs[i][j] = MaxInt;
char v1, v2; int w;
for(int k = 1; k <= G.arcnum; k ++)
{
cin >> v1 >> v2 >> w;
int i = LocateVex(G, v1), j = LocateVex(G, v2);
G.arcs[i][j] = w, G.arcs[j][i] = w;
}
for(int i = 1; i <= G.vexnum; i ++)
{
for(int j = 1; j <= G.vexnum; j ++)
if(G.arcs[i][j] == MaxInt) cout << "∞" << " ";
else cout << G.arcs[i][j] << " ";
cout << endl;
}
return OK;
}
signed main()
{
IOS;
AMGraph G;
CreateUDN(G);
return 0;
}第2關(guān)：算法6.2建立鄰接表
任務(wù)描述
本關(guān)任務(wù)：編寫一個能輸出無向網(wǎng)鄰接表的小程序。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：1.創(chuàng)建鄰接表
編程要求
根據(jù)提示，在右側(cè)編輯器補充代碼，輸出鄰接表。
輸入說明
第一行是頂點數(shù)目n和邊數(shù)目e，中間以空格分開 第二行是n個字符型的頂點數(shù)目名稱，中間以空格分開 接下來e行分別是對應(yīng)的邊 比如說 A B表示頂點A和B之間有邊
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
4 5
A B C D
A B
A C
B C
B D
C D
預(yù)期輸出：
A->2->1
B->3->2->0
C->3->1->0
D->2->1
參考代碼
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "1"
//#define NO cout << "0"
#define MaxInt 0x3f
#define MVNum 100
#define OK 1
#define ERROR -1
const int N = 1003;
using namespace std;
typedef long long LL;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}AMGraph;
typedef struct VNode
{
char data;
ArcNode *firstarc;
}VNode, AdjList[MVNum];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
int LocateVex(ALGraph G , char v)
{
for(int i = 1; i <= G.vexnum; i ++)
if(G.vertices[i].data == v)
return i;
return ERROR;
}
int CreateUDG(ALGraph &G)
{
cin >> G.vexnum >> G.arcnum;
for(int i = 1; i <= G.vexnum; i ++)
{
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;
}
char v1, v2;
for(int k = 1; k <= G.arcnum; k ++)
{
cin >> v1 >> v2;
int i = LocateVex(G, v1), j = LocateVex(G, v2);
ArcNode *p1 = new ArcNode;
p1 -> adjvex = j, p1 -> nextarc = G.vertices[i].firstarc, G.vertices[i].firstarc = p1;
ArcNode *p2 = new ArcNode;
p2 -> adjvex = i, p2 -> nextarc = G.vertices[j].firstarc, G.vertices[j].firstarc = p2;
}
return OK;
}
signed main()
{
IOS; int i;
ALGraph G;
CreateUDG(G);
for(i = 1 ; i <= G.vexnum ; i ++)
{
VNode temp = G.vertices[i];
ArcNode *p = temp.firstarc;
if(p == NULL)
{
cout << G.vertices[i].data;
cout << endl;
}
else
{
cout << temp.data;
while(p)
{
cout << "->";
cout << p->adjvex - 1;
p = p->nextarc;
}
}
cout << endl;
}
return 0;
}算法6.4-6.6DFS
第1關(guān)：算法6.5采用鄰接矩陣表示圖的深搜
任務(wù)描述
本關(guān)任務(wù)：編寫一個采用鄰接矩陣表示圖的深搜程序。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：1.如何創(chuàng)建鄰接矩陣2.如何對圖進行深搜。
編程要求
根據(jù)提示，在右側(cè)編輯器補充代碼，輸出由一個頂點出發(fā)的深搜路徑，頂點之間間隔四個空格。
輸入輸出說明
輸入說明： 第一行為頂點數(shù)n和邊數(shù)e 第二行為n個頂點符號 接下來e行為e條邊，每行兩個字符代表無向圖的一條邊 最后一行僅包含一個字符，代表深搜開始頂點 輸出說明： 一條路徑，頂點之間相隔四個空格
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
4 5
a b c d
a b
a c
a d
b c
c d
c
測試輸出：
c a b d
參考代碼
//算法6.5 采用鄰接矩陣表示圖的深度優(yōu)先搜索遍歷
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "1"
//#define NO cout << "0"
#define MaxInt 0x3f
#define MVNum 100
#define OK 1
#define ERROR 0
const int N = 1003;
using namespace std;
typedef long long LL;
typedef char VerTexType; //假設(shè)頂點的數(shù)據(jù)類型為字符型
typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型
//------------圖的鄰接矩陣------------------
typedef struct
{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum, arcnum; //圖的當前點數(shù)和邊數(shù)
}Graph;
bool visited[MVNum]; //訪問標志數(shù)組，其初值為"false"
int FirstAdjVex(Graph G , int v); //返回v的第一個鄰接點
int NextAdjVex(Graph G , int v , int w); //返回v相對于w的下一個鄰接點
int LocateVex(Graph G , VerTexType v){
//確定點v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vexs[i] == v)
return i;
return -1;
}//LocateVex
void CreateUDN(Graph &G){
//采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)G
int i , j , k;
cin >> G.vexnum >> G.arcnum; //輸入總頂點數(shù)，總邊數(shù)
for(i = 0; i < G.vexnum; ++i){
cin >> G.vexs[i]; //依次輸入點的信息
}
for(i = 0; i < G.vexnum; ++i) //初始化鄰接矩陣，邊的權(quán)值均置為極大值MaxInt
for(j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = 0;
for(k = 0; k < G.arcnum;++k){ //構(gòu)造鄰接矩陣
VerTexType v1 , v2;
cin >> v1 >> v2; //輸入一條邊依附的頂點及權(quán)值
i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置，即頂點數(shù)組的下標
G.arcs[j][i] = G.arcs[i][j] = 1; //置<v1, v2>的對稱邊<v2, v1>的權(quán)值為w
}//for
}//CreateUDN
void DFS(Graph G, int v)
{
cout << G.vexs[v] <<" ";
visited[v] = true;
for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
if(!visited[w]) DFS(G, w);
}//DFS
int FirstAdjVex(Graph G, int v)
{
for(int i = 0; i < G.vexnum; ++ i)
if(G.arcs[v][i] == 1 && visited[i] == false)
return i;
return -1;
}//FirstAdjVex
int NextAdjVex(Graph G, int v, int w)
{
int i;
for(i = w ; i < G.vexnum ; ++ i)
if(G.arcs[v][i] == 1 && visited[i] == false)
return i;
return -1;
}//NextAdjVex
int main(){
Graph G;
CreateUDN(G);
VerTexType c;
cin >> c;
int i;
for(i = 0 ; i < G.vexnum ; ++i){
if(c == G.vexs[i])
break;
}
DFS(G , i);
return 0;
}//main第2關(guān)：算法6.6采用鄰接表表示圖的深搜
任務(wù)描述
本關(guān)任務(wù)：編寫一個采用鄰接表表示圖的深搜程序。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：1.如何創(chuàng)建鄰接表 2.如何對圖進行深搜。
編程要求
根據(jù)提示，在右側(cè)編輯器補充代碼，輸出由一個頂點出發(fā)的深搜路徑，頂點之間間隔四個空格。
輸入輸出說明
輸入說明： 第一行為頂點數(shù)n和邊數(shù)e 第二行為n個頂點符號 接下來e行為e條邊，每行兩個字符代表無向圖的一條邊 最后一行僅包含一個字符，代表深搜開始頂點 輸出說明： 一條路徑，頂點之間相隔四個空格
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
4 5
a b c d
a b
a c
a d
b c
c d
c
測試輸出：
c a b d
參考代碼
//算法6.6 采用鄰接表表示圖的深度優(yōu)先搜索遍歷
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "1"
//#define NO cout << "0"
#define MaxInt 0x3f
#define MVNum 100
#define OK 1
#define ERROR 0
const int N = 1003;
using namespace std;
typedef long long LL;
typedef char VerTexType; //假設(shè)頂點的數(shù)據(jù)類型為字符型
typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型
//-------------圖的鄰接表---------------------
typedef struct ArcNode //邊結(jié)點
{
int adjvex; //該邊所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條邊的指針
}ArcNode;
typedef struct VNode
{
VerTexType data; //頂點信息
ArcNode *firstarc; //指向第一條依附該頂點的邊的指針
}VNode, AdjList[MVNum]; //AdjList表示鄰接表類型
typedef struct
{
AdjList vertices; //鄰接表
int vexnum, arcnum; //圖的當前頂點數(shù)和邊數(shù)
}ALGraph;
bool visited[MVNum]; //訪問標志數(shù)組，其初值為"false"
int LocateVex(ALGraph G , VerTexType v)
{
for(int i = 0; i < G.vexnum; ++i)
if(G.vertices[i].data == v)
return i;
return -1;
}//LocateVex
void CreateUDG(ALGraph &G){
//采用鄰接表表示法，創(chuàng)建無向圖G
int i , k;
cin >> G.vexnum >> G.arcnum; //輸入總頂點數(shù)，總邊數(shù)
for(i = 0; i < G.vexnum; ++i){ //輸入各點，構(gòu)造表頭結(jié)點表
cin >> G.vertices[i].data; //輸入頂點值
G.vertices[i].firstarc=NULL; //初始化表頭結(jié)點的指針域為NULL
}//for
for(k = 0; k < G.arcnum;++k){ //輸入各邊，構(gòu)造鄰接表
VerTexType v1 , v2;
int i , j;
cin >> v1 >> v2; //輸入一條邊依附的兩個頂點
i = LocateVex(G, v1); j = LocateVex(G, v2);
//確定v1和v2在G中位置，即頂點在G.vertices中的序號
ArcNode *p1=new ArcNode; //生成一個新的邊結(jié)點*p1
p1->adjvex=j; //鄰接點序號為j
p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//將新結(jié)點*p1插入頂點vi的邊表頭部
ArcNode *p2=new ArcNode; //生成另一個對稱的新的邊結(jié)點*p2
p2->adjvex=i; //鄰接點序號為i
p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2;
//將新結(jié)點*p2插入頂點vj的邊表頭部
}//for
}//CreateUDG
void DFS(ALGraph G, int v) //圖G為鄰接表類型
{
ArcNode *p;
cout << G.vertices[v].data << " ";
visited[v] = true;
p = G.vertices[v].firstarc;
while(p)
{
if(!visited[p -> adjvex]) DFS(G, p -> adjvex);
p = p -> nextarc;
}
}//DFS
int main(){
ALGraph G;
CreateUDG(G);
VerTexType c;
cin >> c;
int i;
for(i = 0 ; i < G.vexnum ; ++i){
if(c == G.vertices[i].data)
break;
}
DFS(G , i);
return 0;
}//main第3關(guān)：算法6.4非連通圖的深搜-鄰接矩陣表示圖
任務(wù)描述
本關(guān)任務(wù)：編寫一個采用鄰接表表示圖的深搜程序。
相關(guān)知識
為了完成本關(guān)任務(wù)，你需要掌握：1.如何創(chuàng)建鄰接表 2.如何對圖進行深搜。
編程要求
根據(jù)提示，在右側(cè)編輯器補充代碼，輸出由一個頂點出發(fā)的深搜路徑，頂點之間間隔四個空格。
輸入輸出說明
輸入說明： 第一行為頂點數(shù)n和邊數(shù)e 第二行為n個頂點符號 接下來e行為e條邊，每行兩個字符代表無向圖的一條邊 最后一行僅包含一個字符，代表深搜開始頂點 輸出說明： 一條路徑，頂點之間相隔四個空格
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：
6 6
a b c d e f
a b
a c
a d
c d
b d
e f
測試輸出：
a b d c
e f
參考代碼
//算法6.4 深度優(yōu)先搜索遍歷非連通圖
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
//#define YES cout << "1"
//#define NO cout << "0"
#define MaxInt 0x3f
#define MVNum 100
#define OK 1
#define ERROR 0
const int N = 1003;
using namespace std;
typedef long long LL;
typedef char VerTexType; //假設(shè)頂點的數(shù)據(jù)類型為字符型
typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型
//-------------圖的鄰接矩陣-----------------
typedef struct
{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum, arcnum; //圖的當前點數(shù)和邊數(shù)
}Graph;
bool visited[MVNum]; //訪問標志數(shù)組，其初值為"false"
int FirstAdjVex(Graph G , int v); //返回v的第一個鄰接點
int NextAdjVex(Graph G , int v , int w); //返回v相對于w的下一個鄰接點
int LocateVex(Graph G , VerTexType v){
//確定點v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vexs[i] == v)
return i;
return -1;
}//LocateVex
void CreateUDN(Graph &G){
//采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)G
int i , j , k;
cin >> G.vexnum >> G.arcnum; //輸入總頂點數(shù)，總邊數(shù)
for(i = 0; i < G.vexnum; ++i)
cin >> G.vexs[i]; //依次輸入點的信息
for(i = 0; i < G.vexnum; ++i) //初始化鄰接矩陣，邊的權(quán)值均置為極大值MaxInt
for(j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = 0;
for(k = 0; k < G.arcnum;++k){ //構(gòu)造鄰接矩陣
VerTexType v1 , v2;
cin >> v1 >> v2; //輸入一條邊依附的頂點及權(quán)值
i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置，即頂點數(shù)組的下標
G.arcs[j][i] = G.arcs[i][j] = 1; //置<v1, v2>的對稱邊<v2, v1>的權(quán)值為w
}//for
}//CreateUDN
void DFS(Graph G, int v)
{
cout << G.vexs[v];
visited[v] = true;
for(int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
{
if(!visited[w])
{
cout<<" ";
DFS(G,w);
}
}
}//DFS
void DFSTraverse(Graph G){
//對非連通圖G做深度優(yōu)先遍歷
/**************************Begin*************************/
for(int v=0;v<G.vexnum;++v) visited[v]=false;
for(int v=0;v<G.vexnum;++v)
if(!visited[v])
{cout<<endl;
DFS(G,v);
}
/**************************End****************************/
}//DFSTraverse
int FirstAdjVex(Graph G , int v){
//返回v的第一個鄰接點
int i;
for(i = 0 ; i < G.vexnum ; ++i){
if(G.arcs[v][i] == 1 && visited[i] == false)
return i;
}
return -1;
}//FirstAdjVex
int NextAdjVex(Graph G , int v , int w){
//返回v相對于w的下一個鄰接點
int i;
for(i = w ; i < G.vexnum ; ++i){
if(G.arcs[v][i] == 1 && visited[i] == false)
return i;
}
return -1;
}//NextAdjVex
int main(){
Graph G;
CreateUDN(G);
DFSTraverse(G);
return 0;
}//main作者有言
如果感覺博主講的對您有用，請點個關(guān)注支持一下吧，將會對此類問題持續(xù)更新……
?文章來源地址http://www.zghlxwxcb.cn/news/detail-768036.html
?文章來源：http://www.zghlxwxcb.cn/news/detail-768036.html
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)圖 算法6.1-6.2創(chuàng)建無向網(wǎng) 算法6.4-6.6DFS的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
