?要求1. 編程實作如下功能： （1）輸入有向圖的頂點數、邊數及各條邊的頂點對， 建立用鄰接表存盤的有向圖， （2）輸出有向圖的鄰接表 （3）對有向圖進行深度優先搜索和廣度優先搜索遍歷，并分別輸出其遍歷序列， 有向圖如下所示：
#include<iostream>
#include<string.h>
#include<iomanip>
using namespace std;
?
#define ERROR 0
#define OK 1
#define MVNum 100
#define MAX_VERTEX_NUM 100
#define MAXQSIZE 100 //最大佇列長度
?
bool visited[MAX_VERTEX_NUM]; //宣告一個輔助指標visited,即陣列
?
typedef int Status;
typedef char VerTexType; //假設頂點的資料型別為字符型
typedef int VerTexTypesqQueue; //佇列中元素的型別
?
/*------圖的鄰接表存盤表示------*/
typedef struct ArcNode //邊結點
{
int adjvex; //該邊所指向的頂點的位置
struct ArcNode* nextarc; //指向下一條邊的指標
}ArcNode;
?
typedef struct VNode //頂點資訊
{
VerTexType data;
ArcNode* firstarc; //指向第一條依附該頂點的邊的指標
}VNode, AdjList[MVNum]; //AdjList表示鄰接表型別
?
typedef struct
{
AdjList vertices; //鄰接表
int vexnum, arcnum; //圖的當前頂點數和邊數
}ALGraph;
?
//----佇列的定義
typedef struct
{
int* base; //初始化的動態分配存盤空間，注意佇列中存盤的是頂點的位置
int front; //頭指標，若佇列不空，指向隊頭元素
int rear; //尾指標，若佇列不空，指向隊尾元素的下一個位置
}sqQueue;
?
//佇列的相關操作
void InitQueue(sqQueue& Q)
{ //構造一個空佇列Q
Q.base = new VerTexTypesqQueue[MAXQSIZE];
if (!Q.base) exit(1); //存盤分配失敗
Q.front = Q.rear = 0;
} //InitQueue
?
void EnQueue(sqQueue& Q, int e)
{ //插入元素e為Q的新的隊尾元素
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
} //EnQueue
?
bool QueueEmpty(sqQueue Q)
{ //判斷是否為空隊
if (Q.rear == Q.front)
return true;
return false;
} //QueueEmpty
?
void DeQueue(sqQueue& Q, int& u)
{ //隊頭元素出隊并置為u
u = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
}
?
Status LocateVex(ALGraph G, VerTexType v) //求頂點在頂點陣列中的位置
{
for (int i = 0;i < G.vexnum;++i)
if (G.vertices[i].data == v) //找到該頂點
return i; //回傳頂點結點陣列的下標
return -1;
}
?
Status CreateUDG(ALGraph& G) /*采用鄰接表表示法創建有向圖*/
{
VerTexType v1, v2; //
ArcNode* p1; //
cout << "請輸入總頂點數，總邊數，以空格隔開：";
cin >> G.vexnum >> G.arcnum; //輸入頂點數和邊數
cout << endl;
cout << "輸入點的名稱，如a" << endl;
for (int i = 0;i < G.vexnum;i++)
{
cout << "請輸入第" << i + 1 << "個點的名稱：";
cin >> G.vertices[i].data; //輸入頂點的值
G.vertices[i].firstarc = NULL; //初始化表頭結點的指標域為NULL
}
?
cout << endl;
cout << "輸入邊依附的頂點，如a,b" << endl;
for (int k = 0;k < G.arcnum;k++) //輸入各邊，構造鄰接表
{
int i, j;
cout << "請輸入第" << k + 1 << "條邊依附的頂點：";
cin >> v1 >> v2; //輸入一條邊依附的兩個頂點
i = LocateVex(G, v1); //v1在表結點的位置
j = LocateVex(G, v2); //v2在表結點的位置
p1 = new ArcNode; //生成一個新的邊結點*p1
p1->adjvex = j; //鄰接點序號為j
p1->nextarc = G.vertices[i].firstarc; //采用頭插法插入邊結點
G.vertices[i].firstarc = p1; //將新結點*p1插入到頂點vi的邊表頭部
}
return OK;
}
?
void DispGraphAdjList(ALGraph G) //鄰接表的輸出
{
ArcNode* p;
cout << endl;
cout << "有向圖的鄰接表如下：" << endl;
for (int i = 0;i < G.vexnum;++i) //回圈表結點個數次
{
cout << G.vertices[i].data; //輸出表結點的頂點資訊
for (p = G.vertices[i].firstarc;p != NULL;p = p->nextarc)//從第一個邊結點開始，依次輸出所有的邊結點地址域所對應的頂點資訊
{
cout << setw(7) << G.vertices[p->adjvex].data;
}
cout << endl;
}
}
?
void DFS_AL(ALGraph G, int i) //鄰接表存盤的有向圖的DFS
{
ArcNode* p; //宣告一個ArcNode型別的指標p
int j; //記錄下標的變數
cout << setw(7) << G.vertices[i].data; //從頂點vi開始,輸出下標為i的頂點
visited[i] = 1; //頂點已訪問，置為1
p = G.vertices[i].firstarc; //p指向v的邊鏈表的第一個邊結點
while (p != NULL)
{
j = p->adjvex; //j是p的鄰接點下標
if (visited[j] == 0)
DFS_AL(G, j); //如果j未訪問，則遞回呼叫DFS_AL
p = p->nextarc; //p指向下一個邊結點
}
}
?
void BFS_AL(ALGraph G, int v) //鄰接表存盤的有向圖的BFS
{
sqQueue Q;
InitQueue(Q); //初始化佇列Q
int u;
ArcNode* p; //宣告一個ArcNode結點型別的指標p
for (int i = 0;i < G.vexnum;i++) //將所有的頂點的輔助值置為0
{
visited[i] = 0;
}
cout << setw(7) << G.vertices[v].data; //輸出下標為v的表結點頂點資訊
visited[v] = 1; //將下標為v的結點標記為已訪問
EnQueue(Q, v); //將訪問過的結點的下標入隊
while (!QueueEmpty(Q)) //如果堆疊不為空，則進入回圈
{
DeQueue(Q, u); //將隊首的下標出隊
p = G.vertices[u].firstarc; //找到隊首下標位置所對應的結點
while (p != NULL)
{
if (visited[p->adjvex] == 0) //如果沒有被訪問過
{
cout << setw(7) << G.vertices[p->adjvex].data;//訪問，輸出頂點資訊
visited[p->adjvex] = 1; //標記訪問標記
EnQueue(Q, p->adjvex); //將訪問過的結點的下標入隊
}
p = p->nextarc; //指標往后移動，遍歷下一個邊結點
}
}
}
?
int main()
{
VerTexType v;
ALGraph G; //宣告一個圖G
if (CreateUDG(G)) //創建鄰接表
cout << "有向圖G創建完成！" << endl << endl;
DispGraphAdjList(G); //鄰接表的輸出
?
cout << "請輸入遍歷有向圖的起始點:";
cin >> v; //輸入遍歷的起始點
cout << endl << "深度優先搜索遍歷有向圖結果：" << endl;
DFS_AL(G, LocateVex(G, v)); //DFS遍歷有向圖
?
cout << endl << "廣度優先搜索遍歷有向圖結果：" << endl;
BFS_AL(G, LocateVex(G, v)); //BFS遍歷有向圖
?
return 0;
}
執行結果圖：
要求2. 最小生成樹 采用鄰接矩陣的存盤結構，撰寫prim演算法完成最小生成樹，輸出最小生成樹的代價之和 無向圖如圖所示：
?#include<iostream>
#include<iomanip>
using namespace std;
?
#define MVNum 100 //頂點陣列的長度
#define MaxInt 32767 //邊的權值置為最大值
#define OK 1
?
typedef char VerTexType; //假設頂點的資料型別為字符型
typedef int ArcType; //表示邊的權值，型別為整形
typedef int Status;
?
typedef struct
{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum, arcnum; //圖的當前點數和邊數
}AMGraph;
?
Status LocateVex(AMGraph G, VerTexType v) //求頂點在頂點陣列中的位置
{
for (int i = 0;i < G.vexnum;++i)
if (G.vexs[i] == v) //找到該頂點
return i; //回傳頂點結點陣列的下標
return -1;
}
?
/*采用鄰接矩陣表示法創建無向圖*/
Status CreateUDN(AMGraph& G)
{
VerTexType v1, v2;
int w,i,j;
cout << "請輸入總頂點數，總邊數，以空格隔開：";
cin >> G.vexnum >> G.arcnum; //輸入總頂點數和總邊數
cout << endl;
cout << "請輸入點的名稱，如a" << endl;
for (i = 0;i < G.vexnum;++i)
{
cout << "請輸入第" << i + 1 << "個點的名稱：";
cin >> G.vexs[i]; //依次輸入頂點的資訊
}
for (i = 0;i < G.vexnum;++i) //初始化鄰接矩陣，邊的權值均置為最大值MaxInt
{
for (j = 0;j < G.vexnum;++j)
{
G.arcs[i][j] = MaxInt;
}
}
cout << endl << "輸入邊依附的頂點及權值，如AB 5" << endl;
for (int k = 0;k < G.arcnum;++k)
{
cout << "請輸入第" << k + 1 << "條邊依附的頂點及權值：";
cin >> v1 >> v2 >> w; //輸入一條邊依附的兩個頂點和權值
i = LocateVex(G, v1); //頂點v1在G中的位置
j = LocateVex(G, v2); //頂點v2在G中的位置
G.arcs[i][j] = w; //邊<v1,v2>的權值為w
G.arcs[j][i] = G.arcs[i][j]; //邊<v2,v1>的權值也為w
}
return OK;
}
?
/*無向網鄰接矩陣的輸出*/
void DispAMGraph(AMGraph G)
{
cout << endl << "無向網G的鄰接矩陣如下：" << endl;
cout << "輸出無向網的鄰接矩陣" << endl;
for (int i = 0;i < G.vexnum;++i) //回圈頂點的個數次
{
for (int j = 0;j < G.vexnum;++j)
{
cout << setw(7) << G.arcs[i][j]; //輸出鄰接矩陣
}
cout << endl;
}
}
?
//輔助陣列，用于每次篩選出權值最小的邊的鄰接點
struct {
VerTexType adjvex; //記錄權值最小的邊的起始點
ArcType lowcost; //記錄該邊的權值
}closedge[MVNum];
?
//在輔助陣列中找出權值最小的邊的陣列下標，就可以間接找到此邊的終點頂點，
int Min(AMGraph G)
{
int minNum = MaxInt;
int k = -1;
for (int i = 0;i < G.vexnum;++i)
{//權值為0，說明頂點已經歸入最小生成樹中；然后每次和min變數進行比較，最后找出最小的，
if (closedge[i].lowcost != 0&& closedge[i].lowcost < minNum)
{
minNum = closedge[i].lowcost;
k = i;
}
}
return k;//回傳最小權值所在的陣列下標
}
?
/*Prim演算法構造最小生成樹*/
void MiniSpanTree_Prim(AMGraph G, VerTexType u)
{ //無向網G以鄰接矩陣存盤，從頂點u出發構造G的最小生成樹T,輸出T的各條邊
int sum = 0; //記錄最小生成樹最小權值之和
cout << "******利用普里姆演算法構造最小生成樹結果：******" << endl;
VerTexType u0, v0; //宣告兩個臨時頂點變數
int k;
k = LocateVex(G, u); //起點位置，k為頂點u的下標
for (int j = 0;j < G.vexnum;++j) //對V-U的每個頂點vi,初始化closedge[i]
{
if (j != k)
{
closedge[j].adjvex = u; //最小邊在U中的頂點為u
closedge[j].lowcost = G.arcs[k][j]; //初始化權值
}
}
closedge[k].lowcost = 0; //初始，U = { u }
?
for (int i = 1;i < G.vexnum;++i)
{ //選擇其余n-1個頂點，生成n-1條邊（n = G.vexnum ）
k = Min(G); //求出T的下一個結點：closedge[k]存有當前最小邊
?
u0 = closedge[k].adjvex; //u0為最小邊的一個頂點，u0 屬于 U
v0 = G.vexs[k]; //v0為最小邊的另一個頂點，v0 屬于 V-U
cout << "邊 " << u0 << "--->" << v0 << setw(7) << closedge[k].lowcost << endl; //輸出當前的最小邊（u0,v0）
sum += closedge[k].lowcost;
closedge[k].lowcost = 0; //第k個頂點并入U集
for (int j = 0;j < G.vexnum;++j)
if (G.arcs[k][j] < closedge[j].lowcost)
{ //新頂點并入U后重新選擇最小邊
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost = G.arcs[k][j];
}
}
cout << "最小生成樹的代價之和 = " << sum << endl;
}
?
int main(void)
{
VerTexType v;
AMGraph G;
CreateUDN(G); //創建鄰接矩陣
DispAMGraph(G); //輸出無向網鄰接矩陣
cout << "請輸入起點：";
cin >> v; //輸入起始點
MiniSpanTree_Prim(G,v); //構造最小生成樹并輸出
return 0;
}
執行結果圖：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/233915.html
標籤：其他