5.3 二叉樹周遊
traverse
#include <iostream>
#include <queue>//引入隊列頭檔案
using namespace std;
typedef struct Bnode /*定義二叉樹存儲結構*/
{ char data;
struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T) /*建立二叉樹函數*/
{
//按先序次序輸入二叉樹中結點的值（一個字元），建立二叉連結清單表示的二叉樹T
char ch;
cin >> ch;
if(ch=='#')
T=NULL; //遞歸結束，建空樹
else{
T=new Bnode;
T->data=ch; //生成根結點
Createtree(T->lchild); //遞歸建立左子樹
Createtree(T->rchild); //遞歸建立右子樹
}
}
void preorder(Btree T)//先序周遊
{
if(T)
{
cout<<T->data<<" ";
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(Btree T)//中序周遊
{
if(T)
{
inorder(T->lchild);
cout<<T->data<<" ";
inorder(T->rchild);
}
}
void posorder(Btree T)//後序周遊
{
if(T)
{
posorder(T->lchild);
posorder(T->rchild);
cout<<T->data<<" ";
}
}
bool Leveltraverse(Btree T)
{
Btree p;
if(!T)
return false;
queue<Btree>Q; //建立一個普通隊列(先進先出)，裡面存放指針類型
Q.push(T); //根指針入隊
while(!Q.empty()) //如果隊列不空
{
p=Q.front();//取出隊頭元素作為目前擴充結點livenode
Q.pop(); //隊頭元素出隊
cout<<p->data<<" ";
if(p->lchild)
Q.push(p->lchild); //左孩子指針入隊
if(p->rchild)
Q.push(p->rchild); //右孩子指針入隊
}
return true;
}
int main()
{
Btree mytree;
cout<<"按先序次序輸入二叉樹中結點的值（孩子為空時輸入#），建立一棵二叉樹"<<endl;
Createtree(mytree);//建立二叉樹
cout<<endl;
cout<<"二叉樹的先序周遊結果："<<endl;
preorder(mytree);//先序周遊二叉樹
cout<<endl;
cout<<"二叉樹的中序周遊結果："<<endl;
inorder(mytree);//中序周遊二叉樹
cout<<endl;
cout<<"二叉樹的後序周遊結果："<<endl;
posorder(mytree);//後序周遊二叉樹
cout<<endl;
cout<<"二叉樹的層次周遊結果："<<endl;
Leveltraverse(mytree);//層次周遊二叉樹
return 0;
}
depth
#include <iostream>
using namespace std;
typedef struct Bnode /*定義二叉樹存儲結構*/
{ char data;
struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T) /*建立二叉樹函數*/
{
//按先序次序輸入二叉樹中結點的值（一個字元），建立二叉連結清單表示的二叉樹T
char ch;
cin >> ch;
if(ch=='#')
T=NULL; //遞歸結束，建空樹
else{
T=new Bnode;
T->data=ch; //生成根結點
Createtree(T->lchild); //遞歸建立左子樹
Createtree(T->rchild); //遞歸建立右子樹
}
}
int Depth(Btree T)//求二叉樹的深度
{
int m,n;
if(T==NULL)//如果為空樹，深度為0
return 0;
else
{
m=Depth(T->lchild);//遞歸計算左子樹深度
n=Depth(T->rchild);//遞歸計算左子樹深度
if(m>n)
return m+1;//傳回左右子樹最大值加1
else
return n+1;
}
}
int main()
{
Btree mytree;
cout<<"按先序次序輸入二叉樹中結點的值（孩子為空時輸入#），建立一棵二叉樹"<<endl;
//ABD##E##CF#G###
Createtree(mytree);//建立二叉樹
cout<<endl;
cout<<"二叉樹的深度為："<<Depth(mytree)<<endl;
return 0;
}
leaf
#include <iostream>
using namespace std;
typedef struct Bnode /*定義二叉樹存儲結構*/
{ char data;
struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T) /*建立二叉樹函數*/
{
//按先序次序輸入二叉樹中結點的值（一個字元），建立二叉連結清單表示的二叉樹T
char ch;
cin >> ch;
if(ch=='#')
T=NULL; //遞歸結束，建空樹
else{
T=new Bnode;
T->data=ch; //生成根結點
Createtree(T->lchild); //遞歸建立左子樹
Createtree(T->rchild); //遞歸建立右子樹
}
}
int LeafCount(Btree T)//求二叉樹的葉子數
{
if(T==NULL)//如果為空樹，深度為0
return 0;
else
if(T->lchild==NULL&&T->rchild==NULL)//左右子樹均為空，則葉子數為1
return 1;
else
return LeafCount(T->lchild)+LeafCount(T->rchild);//遞歸計算左子樹和右子樹的葉子數之和
}
int NodeCount(Btree T)//求二叉樹的結點數
{
if(T==NULL)//如果為空樹，深度為0
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//遞歸計算左子樹和右子樹的結點數之和加1
}
int main()
{
Btree mytree;
cout<<"按先序次序輸入二叉樹中結點的值（孩子為空時輸入#），建立一棵二叉樹"<<endl;
//ABD##E##CF#G###
Createtree(mytree);//建立二叉樹
cout<<endl;
cout<<"二叉樹的結點數為："<<NodeCount(mytree)<<endl;
cout<<"二叉樹的葉子數為："<<LeafCount(mytree)<<endl;
return 0;
}
PreinCreateBitree
#include <iostream>
using namespace std;
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序還原建立二叉樹
{
if(len==0)
return NULL;
char ch=pre[0]; //找到先序中的第一個結點
int index=0;
while(mid[index]!=ch)//在中序中找到的根結點的左邊為該結點的左子樹，右邊為右子樹
{
index++;
}
BiTree T=new BiTNode;//建立根結點
T->data=ch;
T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子樹
T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子樹
return T;
}
BiTree pro_mid_createBiTree(char *last,char *mid,int len)//後序中序還原建立二叉樹
{
if(len==0)
return NULL;
char ch=last[len-1]; //取得後序周遊順序中最後一個結點
int index=0;//在中序序列中找根結點，并用index記錄長度
while(mid[index]!=ch)//在中序中找到根結點，左邊為該結點的左子樹，右邊為右子樹
index++;
BiTree T=new BiTNode;//建立根結點
T->data=ch;
T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子樹
T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子樹
return T;
}
void pre_order(BiTree T)//前序遞歸周遊二叉樹
{
if(T)
{
cout<<T->data;
pre_order(T->lchild);
pre_order(T->rchild);
}
}
void pro_order(BiTree T)//後序遞歸周遊二叉樹
{
if(T)
{
pro_order(T->lchild);
pro_order(T->rchild);
cout<<T->data;
}
}
int main()
{
BiTree T;
int n;
char pre[100],mid[100],last[100];
cout<<"1. 前序中序還原二叉樹\n";
cout<<"2. 後序中序還原二叉樹\n";
cout<<"0. 退出\n";
int choose=-1;
while(choose!=0)
{
cout<<"請選擇:";
cin>>choose;
switch (choose)
{
case 1://前序中序還原二叉樹
cout<<"請輸入結點的個數:"<<endl;
cin>>n;
cout<<"請輸入前序序列:"<<endl;
for(int i=0;i<n;i++)
cin>>pre[i];
cout<<"請輸入中序序列:"<<endl;
for(int i=0;i<n;i++)
cin>>mid[i];
T=pre_mid_createBiTree(pre,mid,n);
cout<<endl;
cout<<"二叉樹還原成功，輸出其後序序列:"<<endl;
pro_order(T);
cout<<endl<<endl;
break;
case 2://後序中序還原二叉樹
cout<<"請輸入結點的個數:"<<endl;
cin>>n;
cout<<"請輸入後序序列:"<<endl;
for(int i=0 ;i<n;i++)
cin>>last[i];
cout<<"請輸入中序序列:"<<endl;
for(int i=0 ;i<n;i++)
cin>>mid[i];
T=pro_mid_createBiTree(last,mid,n);
cout<<endl;
cout<<"二叉樹還原成功，輸出其先序序列:"<<endl;
pre_order(T);
cout<<endl<<endl;
break;
}
}
return 0;
}
6.圖
6.1 圖的存儲1 建立無向圖的鄰接矩陣
#include<iostream>//建立無向圖的鄰接矩陣
using namespace std;
#define MaxVnum 100 //頂點數最大值
typedef char VexType; //頂點的資料類型，根據需要定義
typedef int EdgeType; //邊上權值的資料類型，若不帶權值的圖，則為0或1
typedef struct {
VexType Vex[MaxVnum];
EdgeType Edge[MaxVnum][MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}AMGraph;
int locatevex(AMGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i])
return i;
return -1;//沒找到
}
void CreateAMGraph(AMGraph& G) {
int i, j;
VexType u, v;
cout << "請輸入頂點數：" << endl;
cin >> G.vexnum;
cout << "請輸入邊數:" << endl;
cin >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (int i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i];
for (int i = 0; i < G.vexnum; i++)//初始化鄰接矩陣所有值為0，如果是網，則初始化鄰接矩陣為無窮大
for (int j = 0; j < G.vexnum; j++)
G.Edge[i][j] = 0;
cout << "請輸入每條邊依附的兩個頂點：" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
G.Edge[i][j] = G.Edge[j][i] = 1; //鄰接矩陣儲置1
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void print(AMGraph G) {//輸出鄰接矩陣
cout << "圖的鄰接矩陣為：" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++)
cout << G.Edge[i][j] << "\t";
cout << endl;
}
}
int main() {
AMGraph G;
CreateAMGraph(G);
print(G);
return 0;
}
/*
4 5
a b c d
a b
a d
b c
b d
c d
*/
6.1 圖的存儲2 建立有向圖的鄰接表
#include<iostream>//建立有向圖的鄰接表
using namespace std;
const int MaxVnum = 100;//頂點數最大值
typedef char VexType;//頂點的資料類型為字元型
typedef struct AdjNode { //定義鄰接點類型
int v; //鄰接點下标
struct AdjNode* next; //指向下一個鄰接點
}AdjNode;
typedef struct VexNode { //定義頂點類型
VexType data; // VexType為頂點的資料類型，根據需要定義
AdjNode* first; //指向第一個鄰接點
}VexNode;
typedef struct {//定義鄰接表類型
VexNode Vex[MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}ALGraph;
int locatevex(ALGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i].data)
return i;
return -1;//沒找到
}
void insertedge(ALGraph& G, int i, int j) {//插入一條邊
AdjNode* s;
s = new AdjNode;
s->v = j;
s->next = G.Vex[i].first;
G.Vex[i].first = s;
}
void printg(ALGraph G) {//輸出鄰接表
cout << "----------鄰接表如下：----------" << endl;
for (int i = 0; i < G.vexnum; i++) {
AdjNode* t = G.Vex[i].first;
cout << G.Vex[i].data << "： ";
while (t != NULL) {
cout << "[" << t->v << "]\t";
t = t->next;
}
cout << endl;
}
}
void CreateALGraph(ALGraph& G) {//建立有向圖鄰接表
int i, j;
VexType u, v;
cout << "請輸入頂點數和邊數:" << endl;
cin >> G.vexnum >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i].data;
for (i = 0; i < G.vexnum; i++)
G.Vex[i].first = NULL;
cout << "請依次輸入每條邊的兩個頂點u,v" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
insertedge(G, i, j);
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
int main() {
ALGraph G;
CreateALGraph(G);//建立有向圖鄰接表
printg(G);//輸出鄰接表
return 0;
}
/*
5 7
a b c d e
a b
a c
a e
b c
c d
c e
d e
*/
6.1 圖的存儲3 建立無向網的鍊式向前星
#include<iostream>//建立無向網的鍊式前向星
#include<cstring>
using namespace std;
const int maxn = 100000 + 5;
int maxx[maxn], head[maxn];
int n, m, x, y, w, cnt;
struct Edge {
int to, w, next;
}e[maxn];
void add(int u, int v, int w) {//添加一條邊u--v
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
void printg() {//輸對外連結式前向星
cout << "----------鍊式前向星如下：----------" << endl;
for (int v = 1; v <= n; v++) {
cout << v << "： ";
for (int i = head[v]; ~i; i = e[i].next) {
int v1 = e[i].to, w1 = e[i].w;
cout << "[" << v1 << " " << w1 << "]\t";
}
cout << endl;
}
}
int main() {
cin >> n >> m;
memset(head, -1, sizeof(head));
cnt = 0;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w);//添加邊
add(y, x, w);//添加反向邊
}
printg();
return 0;
}
/*
4 5
1 2 5
1 4 3
2 3 8
2 4 12
3 4 9
*/
6.2周遊1 基于鄰接矩陣的廣度優先周遊
#include<iostream>
#include<queue>//引入隊列頭檔案
using namespace std;
const int MaxVnum = 100;//頂點數最大值
bool visited[MaxVnum]; //通路标志數組，其初值為"false"
typedef char VexType; //頂點的資料類型，根據需要定義
typedef int EdgeType; //邊上權值的資料類型，若不帶權值的圖，則為0或1
typedef struct {
VexType Vex[MaxVnum];
EdgeType Edge[MaxVnum][MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}AMGraph;
int locatevex(AMGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i])
return i;
return -1;//沒找到
}
void CreateAMGraph(AMGraph& G) {//建立有向圖的鄰接矩陣
int i, j;
VexType u, v;
cout << "請輸入頂點數：" << endl;
cin >> G.vexnum;
cout << "請輸入邊數:" << endl;
cin >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (int i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i];
for (int i = 0; i < G.vexnum; i++)//初始化鄰接矩陣所有值為0，如果是網，則初始化鄰接矩陣為無窮大
for (int j = 0; j < G.vexnum; j++)
G.Edge[i][j] = 0;
cout << "請輸入每條邊依附的兩個頂點：" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
G.Edge[i][j] = 1; //鄰接矩陣儲置1，若無向圖G.Edge[i][j]=G.Edge[j][i]=1
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void print(AMGraph G) {//輸出鄰接矩陣
cout << "圖的鄰接矩陣為：" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++)
cout << G.Edge[i][j] << "\t";
cout << endl;
}
}
void BFS_AM(AMGraph G, int v) {//基于鄰接矩陣的廣度優先周遊
int u, w;
queue<int>Q; //建立一個普通隊列(先進先出)，裡面存放int類型
cout << G.Vex[v] << "\t";
visited[v] = true;
Q.push(v); //源點v入隊
while (!Q.empty()) { //如果隊列不空
u = Q.front();//取出隊頭元素指派給u
Q.pop(); //隊頭元素出隊
for (w = 0; w < G.vexnum; w++) {//依次檢查u的所有鄰接點
if (G.Edge[u][w] && !visited[w]) {//u、w鄰接而且w未被通路
cout << G.Vex[w] << "\t";
visited[w] = true;
Q.push(w);
}
}
}
}
int main() {
int v;
VexType c;
AMGraph G;
CreateAMGraph(G);
print(G);
cout << "請輸入周遊圖的起始點：";
cin >> c;
v = locatevex(G, c);//查找頂點u的存儲下标
if (v != -1) {
cout << "廣度優先搜尋周遊圖結果：" << endl;
BFS_AM(G, v);
}
else
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
return 0;
}
/*測試資料
6 9
1 2 3 4 5 6
1 3
1 2
2 4
3 5
3 2
4 6
4 3
5 6
5 4
1
*/
6.2周遊2 基于鄰接表的廣度優先周遊
#include<iostream>
#include<queue>//引入隊列頭檔案
using namespace std;
const int MaxVnum = 100;//頂點數最大值
bool visited[MaxVnum]; //通路标志數組，其初值為"false"
typedef char VexType;//頂點的資料類型為字元型
typedef struct AdjNode { //定義鄰接點類型
int v; //鄰接點下标
struct AdjNode* next; //指向下一個鄰接點
}AdjNode;
typedef struct VexNode { //定義頂點類型
VexType data; // VexType為頂點的資料類型，根據需要定義
AdjNode* first; //指向第一個鄰接點
}VexNode;
typedef struct {//定義鄰接表類型
VexNode Vex[MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}ALGraph;
int locatevex(ALGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i].data)
return i;
return -1;//沒找到
}
void insertedge(ALGraph& G, int i, int j) {//插入一條邊
AdjNode* s;
s = new AdjNode;
s->v = j;
s->next = G.Vex[i].first;
G.Vex[i].first = s;
}
void printg(ALGraph G) {//輸出鄰接表
cout << "----------鄰接表如下：----------" << endl;
for (int i = 0; i < G.vexnum; i++) {
AdjNode* t = G.Vex[i].first;
cout << G.Vex[i].data << "： ";
while (t != NULL) {
cout << "[" << t->v << "] ";
t = t->next;
}
cout << endl;
}
}
void CreateALGraph(ALGraph& G) {//建立有向圖鄰接表
int i, j;
VexType u, v;
cout << "請輸入頂點數和邊數:" << endl;
cin >> G.vexnum >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i].data;
for (i = 0; i < G.vexnum; i++)
G.Vex[i].first = NULL;
cout << "請依次輸入每條邊的兩個頂點u,v" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
insertedge(G, i, j);
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void BFS_AL(ALGraph G, int v) {//基于鄰接表的廣度優先周遊
int u, w;
AdjNode* p;
queue<int>Q; //建立一個普通隊列(先進先出)，裡面存放int類型
cout << G.Vex[v].data << "\t";
visited[v] = true;
Q.push(v); //源點v入隊
while (!Q.empty()) { //如果隊列不空
u = Q.front();//取出隊頭元素指派給u
Q.pop(); //隊頭元素出隊
p = G.Vex[u].first;
while (p) {//依次檢查u的所有鄰接點
w = p->v;//w為u的鄰接點
if (!visited[w]) {//w未被通路
cout << G.Vex[w].data << "\t";
visited[w] = true;
Q.push(w);
}
p = p->next;
}
}
}
void BFS_AL(ALGraph G) {//非連通圖，基于鄰接表的廣度優先周遊
for (int i = 0; i < G.vexnum; i++)//非連通圖需要查漏點，檢查未被通路的頂點
if (!visited[i])//i未被通路,以i為起點再次廣度優先周遊
BFS_AL(G, i);
}
int main() {
ALGraph G;
int v;
VexType c;
CreateALGraph(G);//建立有向圖鄰接表
printg(G);//輸出鄰接表
cout << "請輸入周遊圖的起始點：";
cin >> c;
v = locatevex(G, c);//查找頂點u的存儲下标
if (v != -1) {
cout << "廣度優先搜尋周遊圖結果：" << endl;
BFS_AL(G, v);
}
else
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
return 0;
}
/*測試資料
6 9
1 2 3 4 5 6
1 3
1 2
2 4
3 5
3 2
4 6
4 3
5 6
5 4
1
*/
6.2周遊3 基于鄰接矩陣的深度優先周遊
#include<iostream>
using namespace std;
const int MaxVnum = 100; //頂點數最大值
bool visited[MaxVnum]; //通路标志數組，其初值為"false"
typedef char VexType; //頂點的資料類型，根據需要定義
typedef int EdgeType; //邊上權值的資料類型，若不帶權值的圖，則為0或1
typedef struct {
VexType Vex[MaxVnum];
EdgeType Edge[MaxVnum][MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}AMGraph;
int locatevex(AMGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i])
return i;
return -1;//沒找到
}
void CreateAMGraph(AMGraph& G) {//建立無向圖的鄰接矩陣
int i, j;
VexType u, v;
cout << "請輸入頂點數：" << endl;
cin >> G.vexnum;
cout << "請輸入邊數:" << endl;
cin >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (int i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i];
for (int i = 0; i < G.vexnum; i++)//初始化鄰接矩陣所有值為0，如果是網，則初始化鄰接矩陣為無窮大
for (int j = 0; j < G.vexnum; j++)
G.Edge[i][j] = 0;
cout << "請輸入每條邊依附的兩個頂點：" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
G.Edge[i][j] = G.Edge[j][i] = 1; //若有向圖G.Edge[i][j]=1
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void print(AMGraph G) {//輸出鄰接矩陣
cout << "圖的鄰接矩陣為：" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++)
cout << G.Edge[i][j] << "\t";
cout << endl;
}
}
void DFS_AM(AMGraph G, int v) {//基于鄰接矩陣的深度優先周遊
int w;
cout << G.Vex[v] << "\t";
visited[v] = true;
for (w = 0; w < G.vexnum; w++)//依次檢查v的所有鄰接點
if (G.Edge[v][w] && !visited[w])//v、w鄰接而且w未被通路
DFS_AM(G, w);//從w頂點開始遞歸深度優先周遊
}
int main() {
int v;
VexType c;
AMGraph G;
CreateAMGraph(G);//建立無向圖的鄰接矩陣
print(G);
cout << "請輸入周遊連通圖的起始點：";
cin >> c;
v = locatevex(G, c);//查找頂點u的存儲下标
if (v != -1) {
cout << "深度優先搜尋周遊連通圖結果：" << endl;
DFS_AM(G, v);
}
else
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
return 0;
}
/*測試資料
8 9
1 2 3 4 5 6 7 8
1 3
1 2
2 6
2 5
2 4
3 8
3 7
4 5
7 8
1
*/
6.2周遊4 基于鄰接表的深度優先周遊
#include<iostream>
using namespace std;
const int MaxVnum = 100; //頂點數最大值
bool visited[MaxVnum]; //通路标志數組，其初值為"false"
typedef char VexType; //頂點的資料類型為字元型
typedef struct AdjNode { //定義鄰接點類型
int v; //鄰接點下标
struct AdjNode* next; //指向下一個鄰接點
}AdjNode;
typedef struct VexNode { //定義頂點類型
VexType data; // VexType為頂點的資料類型，根據需要定義
AdjNode* first; //指向第一個鄰接點
}VexNode;
typedef struct {//定義鄰接表類型
VexNode Vex[MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}ALGraph;
int locatevex(ALGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i].data)
return i;
return -1;//沒找到
}
void insertedge(ALGraph& G, int i, int j) {//插入一條邊
AdjNode* s;
s = new AdjNode;
s->v = j;
s->next = G.Vex[i].first;
G.Vex[i].first = s;
}
void printg(ALGraph G) {//輸出鄰接表
cout << "----------鄰接表如下：----------" << endl;
for (int i = 0; i < G.vexnum; i++) {
AdjNode* t = G.Vex[i].first;
cout << G.Vex[i].data << "： ";
while (t != NULL) {
cout << "[" << t->v << "] ";
t = t->next;
}
cout << endl;
}
}
void CreateALGraph(ALGraph& G) {//建立無向圖鄰接表
int i, j;
VexType u, v;
cout << "請輸入頂點數和邊數:" << endl;
cin >> G.vexnum >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i].data;
for (i = 0; i < G.vexnum; i++)
G.Vex[i].first = NULL;
cout << "請依次輸入每條邊的兩個頂點u,v" << endl;
while (G.edgenum--) {
cin >> u >> v;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1) {
insertedge(G, i, j);
insertedge(G, j, i);//無向圖多插入一條邊
}
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void DFS_AL(ALGraph G, int v) {//基于鄰接表的深度優先周遊
int w;
AdjNode* p;
cout << G.Vex[v].data << "\t";
visited[v] = true;
p = G.Vex[v].first;
while (p) {//依次檢查v的所有鄰接點
w = p->v;//w為v的鄰接點
if (!visited[w])//w未被通路
DFS_AL(G, w);//從w出發，遞歸深度優先周遊
p = p->next;
}
}
void DFS_AL(ALGraph G) {//非連通圖，基于鄰接表的深度優先周遊
for (int i = 0; i < G.vexnum; i++)//非連通圖需要查漏點，檢查未被通路的頂點
if (!visited[i])//i未被通路,以i為起點再次深度優先周遊
DFS_AL(G, i);
}
int main() {
ALGraph G;
int v;
VexType c;
CreateALGraph(G);//建立無向圖的鄰接表
printg(G);//輸出鄰接表
cout << "請輸入周遊連通圖的起始點：";
cin >> c;
v = locatevex(G, c);//查找頂點u的存儲下标
if (v != -1) {
cout << "深度優先搜尋周遊連通圖結果：" << endl;
DFS_AL(G, v);
}
else
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
return 0;
}
/*測試資料
8 9
1 2 3 4 5 6 7 8
1 3
1 2
2 6
2 5
2 4
3 8
3 7
4 5
7 8
1
*/
7.1 最短路徑
7.1 最短路徑1 dijkstra
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int MaxVnum = 100; //城市的個數可修改
const int INF = 0x3f3f3f3f; //無窮大
int dist[MaxVnum], p[MaxVnum];//最短距離和前驅數組
bool flag[MaxVnum]; //如果s[i]等于true，說明頂點i已經加入到集合S;否則頂點i屬于集合V-S
typedef string VexType; //頂點的資料類型，根據需要定義
typedef int EdgeType; //邊上權值的資料類型，若不帶權值的圖，則為0或1
typedef struct {
VexType Vex[MaxVnum];
EdgeType Edge[MaxVnum][MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}AMGraph;
int locatevex(AMGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i])
return i;
return -1;//沒找到
}
void CreateAMGraph(AMGraph& G) {
int i, j, w;
VexType u, v;
cout << "請輸入頂點數：" << endl;
cin >> G.vexnum;
cout << "請輸入邊數:" << endl;
cin >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (int i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i];
for (int i = 0; i < G.vexnum; i++)//初始化鄰接矩陣為無窮大
for (int j = 0; j < G.vexnum; j++)
G.Edge[i][j] = INF;
cout << "請輸入每條邊依附的兩個頂點及權值：" << endl;
while (G.edgenum--) {
cin >> u >> v >> w;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
G.Edge[i][j] = w; //有向圖鄰接矩陣
else {
cout << "輸入頂點資訊錯！請重新輸入！" << endl;
G.edgenum++;//本次輸入不算
}
}
}
void Dijkstra(AMGraph G, int u) {
for (int i = 0; i < G.vexnum; i++) {
dist[i] = G.Edge[u][i]; //初始化源點u到其他各個頂點的最短路徑長度
flag[i] = false;
if (dist[i] == INF)
p[i] = -1; //源點u到該頂點的路徑長度為無窮大，說明頂點i與源點u不相鄰
else
p[i] = u; //說明頂點i與源點u相鄰，設定頂點i的前驅p[i]=u
}
dist[u] = 0;
flag[u] = true; //初始時，集合S中隻有一個元素：源點u
for (int i = 0; i < G.vexnum; i++) {
int temp = INF, t = u;
for (int j = 0; j < G.vexnum; j++) //在集合V-S中尋找距離源點u最近的頂點t
if (!flag[j] && dist[j] < temp) {
t = j;
temp = dist[j];
}
if (t == u) return; //找不到t，跳出循環
flag[t] = true; //否則，将t加入集合
for (int j = 0; j < G.vexnum; j++)//更新V-S中與t相鄰接的頂點到源點u的距離
if (!flag[j] && G.Edge[t][j] < INF)
if (dist[j] > (dist[t] + G.Edge[t][j])) {
dist[j] = dist[t] + G.Edge[t][j];
p[j] = t;
}
}
}
void findpath(AMGraph G, VexType u) {
int x;
stack<int>S;
cout << "源點為：" << u << endl;
for (int i = 0; i < G.vexnum; i++) {
x = p[i];
if (x == -1 && u != G.Vex[i]) {
cout << "源點到其它各頂點最短路徑為：" << u << "--" << G.Vex[i] << " sorry,無路可達" << endl;
continue;
}
while (x != -1) {
S.push(x);
x = p[x];
}
cout << "源點到其它各頂點最短路徑為：";
while (!S.empty()) {
cout << G.Vex[S.top()] << "--";
S.pop();
}
cout << G.Vex[i] << " 最短距離為：" << dist[i] << endl;
}
}
int main() {
AMGraph G;
int st;
VexType u;
CreateAMGraph(G);
cout << "請輸入源點的資訊:" << endl;
cin >> u;
st = locatevex(G, u);//查找源點u的存儲下标
Dijkstra(G, st);
cout << "小明所在的位置:" << u << endl;
for (int i = 0; i < G.vexnum; i++) {
cout << "小明:" << u << " - " << "要去的位置:" << G.Vex[i];
if (dist[i] == INF)
cout << " sorry,無路可達" << endl;
else
cout << " 最短距離為:" << dist[i] << endl;
}
findpath(G, u);
return 0;
}
/*
5 8
1 2 3 4 5
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
1
*/
7.1 最短路徑2 Floyd
#include<iostream>
#include<cstring>
using namespace std;
const int MaxVnum = 100; //頂點數最大值
const int INF = 0x3f3f3f3f; // 無窮大
typedef string VexType; //頂點的資料類型，根據需要定義
typedef int EdgeType; //邊上權值的資料類型，若不帶權值的圖，則為0或1
typedef struct {
VexType Vex[MaxVnum];
EdgeType Edge[MaxVnum][MaxVnum];
int vexnum, edgenum; //頂點數，邊數
}AMGraph;
int dist[MaxVnum][MaxVnum], p[MaxVnum][MaxVnum];
int locatevex(AMGraph G, VexType x) {
for (int i = 0; i < G.vexnum; i++)//查找頂點資訊的下标
if (x == G.Vex[i])
return i;
return -1;//沒找到
}
void CreateAMGraph(AMGraph& G) {//建立無向圖的鄰接矩陣
int i, j, w;
VexType u, v;
cout << "請輸入頂點數：" << endl;
cin >> G.vexnum;
cout << "請輸入邊數:" << endl;
cin >> G.edgenum;
cout << "請輸入頂點資訊:" << endl;
for (int i = 0; i < G.vexnum; i++)//輸入頂點資訊，存入頂點資訊數組
cin >> G.Vex[i];
for (int i = 0; i < G.vexnum; i++)//初始化鄰接矩陣所有值為0，若是網，則初始化為無窮大
for (int j = 0; j < G.vexnum; j++)
if (i != j)
G.Edge[i][j] = INF;
else
G.Edge[i][j] = 0; //注意i==j時，設定為0
cout << "請輸入每條邊依附的兩個頂點及權值：" << endl;
while (G.edgenum--) {
cin >> u >> v >> w;
i = locatevex(G, u);//查找頂點u的存儲下标
j = locatevex(G, v);//查找頂點v的存儲下标
if (i != -1 && j != -1)
G.Edge[i][j] = w; //有向圖鄰接矩陣存儲權值
}
}
void Floyd(AMGraph G) { //用Floyd算法求有向網G中各對頂點i和j之間的最短路徑
int i, j, k;
for (i = 0; i < G.vexnum; i++) //各對結點之間初始已知路徑及距離
for (j = 0; j < G.vexnum; j++) {
dist[i][j] = G.Edge[i][j];
if (dist[i][j] < INF && i != j)
p[i][j] = i; //如果i和j之間有弧，則将j的前驅置為i
else p[i][j] = -1; //如果i和j之間無弧，則将j的前驅置為-1
}
for (k = 0; k < G.vexnum; k++)
for (i = 0; i < G.vexnum; i++)
for (j = 0; j < G.vexnum; j++)
if (dist[i][k] + dist[k][j] < dist[i][j]) {//從i經k到j的一條路徑更短
dist[i][j] = dist[i][k] + dist[k][j]; //更新dist[i][j]
p[i][j] = p[k][j]; //更改j的前驅
}
}
void print(AMGraph G) {
int i, j;
for (i = 0; i < G.vexnum; i++) {//輸出最短距離數組
for (j = 0; j < G.vexnum; j++)
cout << dist[i][j] << "\t";
cout << endl;
}
cout << endl;
for (i = 0; i < G.vexnum; i++) {//輸出前驅數組
for (j = 0; j < G.vexnum; j++)
cout << p[i][j] << "\t";
cout << endl;
}
}
void DisplayPath(AMGraph G, int s, int t) {//顯示最短路徑
if (p[s][t] != -1) {
DisplayPath(G, s, p[s][t]);
cout << G.Vex[p[s][t]] << "-->";
}
}
int main() {
VexType start, destination;
int u, v;
AMGraph G;
CreateAMGraph(G);
Floyd(G);
print(G);
cout << "請依次輸入路徑的起點與終點的名稱：";
cin >> start >> destination;
u = locatevex(G, start);
v = locatevex(G, destination);
DisplayPath(G, u, v);
cout << G.Vex[v] << endl;
cout << "最短路徑的長度為：" << dist[u][v] << endl;
cout << endl;
return 0;
}
/*
4 8
0 1 2 3
0 1 1
0 3 4
1 2 9
1 3 2
2 0 3
2 1 5
2 3 8
3 2 6
0 2
*/
7.1 最短路徑3 bellman ford
#include<iostream>
#include<cstring>
using namespace std;
struct node {
int a, b, w;
}e[210];
int dis[110];
int n, m, cnt = 0;
void add(int a, int b, int w) {
e[cnt].a = a;
e[cnt].b = b;
e[cnt++].w = w;
}
bool bellman_ford(int u) {//求源點u到其它頂點的最短路徑長度，判負環
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0;
for (int i = 1; i < n; i++) {//執行n-1次
bool flag = false;
for (int j = 0; j < m; j++)//邊數m或cnt
if (dis[e[j].b] > dis[e[j].a] + e[j].w) {
dis[e[j].b] = dis[e[j].a] + e[j].w;
flag = true;
}
if (!flag)
return false;
}
for (int j = 0; j < m; j++)//再執行1次，還能松弛說明有環
if (dis[e[j].b] > dis[e[j].a] + e[j].w)
return true;
return false;
}
void print() {//輸出源點到其它節點的最短距離
cout << "最短距離：" << endl;
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
cout << endl;
}
int main() {
int a, b, w;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b >> w;
add(a, b, w);
}
if (bellman_ford(1))//判斷負環
cout << "有負環！" << endl;
else
print();
return 0;
}
/*測試資料1
5 8
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
*/
/*測試資料2，有負環
4 4
1 2 3
2 3 -4
3 4 2
4 2 1
*/
7.1 最短路徑4 spfa
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 505, maxe = 100001;
int n, m, cnt;
int head[maxn], dis[maxn], sum[maxn];
bool vis[maxn];//标記是否在隊列中
struct node {
int to, next, w;
}e[maxe];
void add(int u, int v, int w) {
e[cnt].to = v;
e[cnt].next = head[u];
e[cnt].w = w;
head[u] = cnt++;
}
bool spfa(int u) {
queue<int>q;
memset(vis, 0, sizeof(vis));//标記是否在隊列中
memset(sum, 0, sizeof(sum));//統計入隊的次數
memset(dis, 0x3f, sizeof(dis));
vis[u] = 1;
dis[u] = 0;
sum[u]++;
q.push(u);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (dis[v] > dis[x] + e[i].w) {
dis[v] = dis[x] + e[i].w;
if (!vis[v]) {
if (++sum[v] >= n)
return true;
vis[v] = 1;
q.push(v);
}
}
}
}
return false;
}
void print() {//輸出源點到其它節點的最短距離
cout << "最短距離：" << endl;
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
cout << endl;
}
int main() {
cnt = 0;
cin >> n >> m;
memset(head, -1, sizeof(head));
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add(u, v, w);
}
if (spfa(1))
cout << "有負環！" << endl;
else
print();
return 0;
}
/*測試資料1
5 8
1 2 2
1 3 5
2 3 2
2 4 6
3 4 7
3 5 1
4 3 2
4 5 4
*/
/*測試資料2，有負環
4 4
1 2 3
2 3 -4
3 4 2
4 2 1
*/
7.2 最小生成樹
Prim
#include<iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100;
bool s[N];//如果s[i]=true,說明頂點i已加入U
int c[N][N], closest[N], lowcost[N];
void Prim(int n) {
s[1] = true; //初始時，集合中U隻有一個元素，即頂點1
for (int i = 1; i <= n; i++) {
if (i != 1) {
lowcost[i] = c[1][i];
closest[i] = 1;
s[i] = false;
}
else
lowcost[i] = 0;
}
for (int i = 1; i < n; i++) {
int temp = INF;
int t = 1;
for (int j = 1; j <= n; j++) {//在集合中V-u中尋找距離集合U最近的頂點t
if (!s[j] && lowcost[j] < temp) {
t = j;
temp = lowcost[j];
}
}
if (t == 1)
break;//找不到t，跳出循環
s[t] = true;//否則，t加入集合U
for (int j = 1; j <= n; j++) { //更新lowcost和closest
if (!s[j] && c[t][j] < lowcost[j]) {
lowcost[j] = c[t][j];
closest[j] = t;
}
}
}
}
int main() {
int n, m, u, v, w;
cin >> n >> m;
int sumcost = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c[i][j] = INF;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
c[u][v] = c[v][u] = w;
}
Prim(n);
cout << "數組lowcost:" << endl;
for (int i = 1; i <= n; i++)
cout << lowcost[i] << " ";
cout << endl;
for (int i = 1; i <= n; i++)
sumcost += lowcost[i];
cout << "最小的花費：" << sumcost << endl;
return 0;
}
/*測試資料
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
輸出結果：
數組lowcost:
0 23 4 9 3 17 1
最小的花費：57
*/
Kruskal
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int fa[N];
int n,m;
struct Edge{
int u,v,w;
}e[N*N];
bool cmp(Edge x, Edge y){
return x.w<y.w;
}
void Init(int n){//初始化集合号為自身
for(int i=1;i<=n;i++)
fa[i]=i;
}
int Merge(int a,int b){//合并
int p=fa[a];
int q=fa[b];
if(p==q) return 0;
for(int i=1;i<=n;i++){//檢查所有結點，把集合号是q的改為p
if(fa[i]==q)
fa[i]=p;//a的集合号指派給b集合号
}
return 1;
}
int Kruskal(int n){//求最小生成樹
int ans=0;
sort(e,e+m,cmp);
for(int i=0;i<m;i++)
if(Merge(e[i].u,e[i].v)){
ans+=e[i].w;
n--;
if(n==1)//n-1次合并算法結束
return ans;
}
return 0;
}
int main(){
cin>>n>>m;
Init(n);
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
cout<<"最小的花費是："<<Kruskal(n)<<endl;
return 0;
}
/*測試資料
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
*/
Kruskal_2
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int fa[N];
int n,m;
struct Edge{
int u,v,w;
}e[N*N];
bool cmp(Edge x,Edge y){
return x.w<y.w;
}
void Init(int n){//初始化集合号為自身
for(int i=1;i<=n;i++)
fa[i]=i;
}
int Find(int x){//找祖宗
if(x!=fa[x])
fa[x]=Find(fa[x]);
return fa[x];
}
bool Merge(int a,int b){
int p=Find(a);
int q=Find(b);
if(p==q) return 0;
fa[q]=p;
return 1;
}
int Kruskal(int n){
int ans=0;
sort(e,e+m,cmp);
for(int i=0;i<m;i++)
if(Merge(e[i].u,e[i].v)){
ans+=e[i].w;
n--;
if(n==1)
return ans;
}
return 0;
}
int main(){
cin>>n>>m;
Init(n);
for(int i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
cout<<"最小的花費："<<Kruskal(n)<<endl;
return 0;
}
/*測試資料
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
*/
7.3拓撲排序
Topo sort
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=105;
int map[maxn][maxn],indegree[maxn],topo[maxn];
int n,m;
stack<int>s;
bool TopoSort(){ //拓撲排序
int cnt=0;
for(int i=0;i<n;i++)
if(indegree[i]==0)
s.push(i);
while(!s.empty()){
int u=s.top();
s.pop();
topo[cnt++]=u;
for(int j=0;j<n;j++)
if(map[u][j])
if(--indegree[j]==0)
s.push(j);
}
if(cnt<n) return 0;
return 1;
}
int main(){
cin>>n>>m;
memset(map,0,sizeof(map));
memset(indegree,0,sizeof(indegree));
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
map[u][v]=1;
indegree[v]++;
}
TopoSort();
for(int i=0;i<n-1;i++)
cout<<topo[i]<<" ";
cout<<topo[n-1]<<endl;
return 0;
}
/*測試資料
6 8
0 1
0 2
0 3
2 1
2 4
3 4
5 3
5 4
*/
7.4 關鍵路徑
CriticalPath
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=10010,maxe=50010;
int n,m,cnt;
int head[maxn]; //鍊式前向星頭
int in[maxn],topo[maxn]; //入度,拓撲序列
int ve[maxn]; //事件vi的最早發生時間
int vl[maxn]; //事件vi的最遲發生時間
stack<int>s;
struct node{
int to,next,w;
}e[maxe];
void add(int u,int v,int w){
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[cnt++].w=w;
}
bool TopoSort(){//拓撲排序
int cnt=0;
for(int i=0;i<n;i++)
if(in[i]==0)
s.push(i);
while(!s.empty()){
int u=s.top();
s.pop();
topo[cnt++]=u;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(--in[v]==0)
s.push(v);
}
}
if(cnt<n) return 0;//該有向圖有回路
return 1;
}
bool CriticalPath(){//關鍵路徑
if(TopoSort()){
cout<<"拓撲序列為："<<endl;
for(int i=0;i<n;i++)//輸出拓撲序列
cout<<topo[i]<<"\t";
cout<<endl;
}
else{
cout<<"該圖有環，無拓撲序列！"<<endl;
return 0;
}
for(int i=0;i<n;i++)//初始化最早發生時間為0
ve[i]=0;
//按拓撲次序求每個事件的最早發生時間
for(int j=0;j<n;j++){
int u=topo[j]; //取得拓撲序列中的頂點
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(ve[v]<ve[u]+w)
ve[v]=ve[u]+w;
}
}
for(int i=0;i<n;i++) //初始化每個事件的最遲發生時間為ve[n]
vl[i]=ve[n-1];
for(int j=n-1;j>=0;j--){//按逆拓撲序求每個事件的最遲發生時間
int u=topo[j]; //取得拓撲序列中的頂點
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(vl[u]>vl[v]-w)
vl[u]=vl[v]-w;
}
}
cout<<"事件的最早發生時間和最遲發生時間："<<endl;
for(int i=0;i<n;i++)
cout<<ve[i]<<"\t"<<vl[i]<<endl;
cout<<"關鍵活動路徑為:"<<endl;
for(int u=0;u<n;u++){ //每次循環針對vi為活動開始點的所有活動
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
int e=ve[u]; //計算活動<vi, vj>的最早開始時間e
int l=vl[v]-w; //計算活動<vi, vj>的最遲開始時間l
if(e==l) //若為關鍵活動，則輸出<vi, vj>
cout<<"<"<<u<<","<<v<<">"<<endl;
}
}
return 1;
}
int main(){
int u,v,w;
cin>>n>>m;
memset(head,-1,sizeof(head));
memset(in,0,sizeof(in));
for(int i=0;i<m;i++){
cin>>u>>v>>w;
add(u,v,w);
in[v]++;
}
CriticalPath();
return 0;
}
/*測試資料
6 8
0 1 2
0 2 15
1 3 10
1 4 19
2 1 4
2 4 11
3 5 6
4 5 5
*/
8.1 哈希表
Hash
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define m 15//哈希表的表長
#define NULLKEY 0//單元為空的标記
int HT[m],HC[m];
int H(int key){//哈希函數
return key%13;
}
int Linedetect(int HT[],int H0,int key,int &cnt){
int Hi;
for(int i=1;i<m;++i){
cnt++;
Hi=(H0+i)%m; //按照線性探測法計算下一個哈希位址Hi
if(HT[Hi]==NULLKEY)
return Hi; //若單元Hi為空，則所查元素不存在
else if(HT[Hi]==key)
return Hi; //若單元Hi中元素的關鍵字為key
}
return -1;
}
int Seconddetect(int HT[],int H0,int key,int &cnt){
int Hi;
for(int i=1;i<=m/2;++i){
int i1=i*i;
int i2=-i1;
cnt++;
Hi=(H0+i1)%m; //按照線性探測法計算下一個哈希位址Hi
if(HT[Hi]==NULLKEY)//若單元Hi為空，則所查元素不存在
return Hi;
else if(HT[Hi]==key)//若單元Hi中元素的關鍵字為key
return Hi;
cnt++;
Hi=(H0+i2)%m; //按照線性探測法計算下一個哈希位址Hi
if(Hi<0)
Hi+=m;
if(HT[Hi]==NULLKEY)//若單元Hi為空，則所查元素不存在
return Hi;
else if(HT[Hi]==key)//若單元Hi中元素的關鍵字為key
return Hi;
}
return -1;
}
int SearchHash(int HT[],int key){
//在哈希表HT中查找關鍵字為key的元素，若查找成功，傳回哈希表的單元标号，否則傳回-1
int H0=H(key); //根據哈希函數H（key）計算哈希位址
int Hi,cnt=1;
if(HT[H0]==NULLKEY)//若單元H0為空，則所查元素不存在
return -1;
else if(HT[H0]==key){//若單元H0中元素的關鍵字為key，則查找成功
cout<<"查找成功，比較次數："<<cnt<<endl;
return H0;
}
else{
Hi=Linedetect(HT,H0,key,cnt);
if(HT[Hi]==key){//若單元Hi中元素的關鍵字為key，則查找成功
cout<<"查找成功，比較次數："<<cnt<<endl;
return Hi;
}
else
return -1; //若單元Hi為空，則所查元素不存在
}
}
bool InsertHash(int HT[],int key){
int H0=H(key); //根據哈希函數H（key）計算哈希位址
int Hi=-1,cnt=1;
if(HT[H0]==NULLKEY){
HC[H0]=1;//統計比較次數
HT[H0]=key; //若單元H0為空，放入
return 1;
}
else{
Hi=Linedetect(HT,H0,key,cnt);//線性探測
//Hi=Seconddetect(HT,H0,key,cnt);//二次探測
if((Hi!=-1)&&(HT[Hi]==NULLKEY)){
HC[Hi]=cnt;
HT[Hi]=key;//若單元Hi為空，放入
return 1;
}
}
return 0;
}
void print(int HT[]){
for(int i=0;i<m;i++)
cout<<HT[i]<<"\t";
cout<<endl;
}
int main(){
int x;
memset(HT,0,sizeof(HT));
memset(HC,0,sizeof(HC));
print(HT);
cout<<"輸入12個關鍵字，存入哈希表中："<<endl;
for(int i=0;i<12;i++){
cin>>x;
if(!InsertHash(HT,x)){
cout<<"建立哈希表失敗！"<<endl;
return 0;
}
}
cout<<"輸出哈希表："<<endl;
print(HT);
print(HC);
cout<<"輸入要查找的關鍵字"<<endl;
cin>>x;
int result=SearchHash(HT,x);
if(result!=-1)
cout<<"在第"<<result+1<<"位置找到"<<endl;
else
cout<<"未找到"<<endl;
return 0;
}
//測試資料：14 36 42 38 40 15 19 12 51 65 34 25
8.2 字元串模式比對
BF
#include<iostream>
#include<string>
using namespace std;
int BF(string s,string t,int pos){
int i=pos,j=0,sum=0;
int slen=s.length();
int tlen=t.length();
while(i<slen&&j<tlen){
sum++;
if(s[i]==t[j])//如果相等，則繼續比較後面的字元
i++,j++;
else{
i=i-j+1; //i回退到上一輪開始比較的下一個字元
j=0; //j回退到第1個字元
}
}
cout<<"一共比較了"<<sum<<"次"<<endl;
if(j>=tlen) // 比對成功
return i-tlen+1;
else
return 0;
}
int main(){
string s,t;
cin>>s>>t;
cout<<BF(s,t,0)<<endl;
return 0;
}
/*
abaabaabeca
abaabe
*/
/*
aabaaabaaaabea
aaaab
*/
KMP
#include<iostream>
#include<string>
using namespace std;
int slen,tlen,next[1000+5];
void get_next(string t){//求模式串T的next函數
int j=0,k=-1;
next[0]=-1;
while(j<tlen){//模式串t的長度
if(k==-1||t[j]==t[k])
next[++j]=++k;
else
k=next[k];
}
for(int i=0;i<=tlen;i++)
cout<<next[i]<<" ";
}
void get_next2(string t){ //改進的next函數
int j=0,k=-1;
next[0]=-1;
while(j<tlen){//模式串t的長度
if(k==-1||t[j]==t[k]){
j++,k++;
if(t[j]==t[k])
next[j]=next[k];
else
next[j]=k;
}
else
k=next[k];
}
for(int i=0;i<=tlen;i++)
cout<<next[i]<<" ";
}
int KMP(string s,string t,int pos){
int i=pos,j=0,sum=0;
slen=s.length();
tlen=t.length();
get_next(t);
while(i<slen&&j<tlen){
sum++;
if(j==-1||s[i]==t[j])//如果相等，則繼續比較後面的字元
i++,j++;
else
j=next[j];//j回退到next[j]
}
cout<<"一共比較了"<<sum<<"次"<<endl;
if(j>=tlen) // 比對成功
return i-tlen+1;
else
return -1;
}
int main(){
string s,t;
cin>>s>>t;
cout<<KMP(s,t,0)<<endl;
return 0;
}
/*
abaabaabeca
abaabe
*/
/*
aabaaabaaaabea
aaaab
*/
8.3 二叉查找樹
bst
#include<iostream>
using namespace std;
#define ENDFLAG -1
typedef int ElemType;
typedef struct BSTNode{
ElemType data; //結點資料域
BSTNode *lchild,*rchild; //左右孩子指針
}BSTNode,*BSTree;
BSTree SearchBST(BSTree T,ElemType key)//二叉排序樹的遞歸查找
{
//若查找成功，則傳回指向該資料元素結點的指針，否則傳回空指針
if((!T)|| key==T->data)
return T;
else if (key<T->data)
return SearchBST(T->lchild,key);//在左子樹中繼續查找
else
return SearchBST(T->rchild,key); //在右子樹中繼續查找
}
void InsertBST(BSTree &T,ElemType e)//二叉排序樹的插入
{
//當二叉排序樹T中不存在關鍵字等于e的資料元素時，則插入該元素
if(!T)
{
BSTree S=new BSTNode; //生成新結點
S->data=e; //新結點S的資料域置為e
S->lchild=S->rchild=NULL;//新結點S作為葉子結點
T=S; //把新結點S連結到已找到的插入位置
}
else if(e<T->data)
InsertBST(T->lchild,e );//插入左子樹
else if(e>T->data)
InsertBST(T->rchild,e);//插入右子樹
}
void CreateBST(BSTree &T )//二叉排序樹的建立
{
//依次讀入一個關鍵字為key的結點，将此結點插入二叉排序樹T中
T=NULL;
ElemType e;
cin>>e;
while(e!=ENDFLAG)//ENDFLAG為自定義常量，作為輸入結束标志
{
InsertBST(T,e); //插入二叉排序樹T中
cin>>e;
}
}
void DeleteBST(BSTree &T,char key)
{
//從二叉排序樹T中删除關鍵字等于key的結點
BSTree p=T;BSTree f=NULL;
BSTree q;
BSTree s;
if(!T) return; //樹為空則傳回
while(p)//查找
{
if(p->data==key) break; //找到關鍵字等于key的結點p，結束循環
f=p; //f為p的雙親
if (p->data>key)
p=p->lchild; //在p的左子樹中繼續查找
else
p=p->rchild; //在p的右子樹中繼續查找
}
if(!p) return; //找不到被删結點則傳回
//三種情況：p左右子樹均不空、無右子樹、無左子樹
if((p->lchild)&&(p->rchild))//被删結點p左右子樹均不空
{
q=p;
s=p->lchild;
while(s->rchild)//在p的左子樹中繼續查找其前驅結點，即最右下結點
{
q=s;
s=s->rchild;
}
p->data=s->data; //s的值指派給被删結點p,然後删除s結點
if(q!=p)
q->rchild=s->lchild; //重接q的右子樹
else
q->lchild=s->lchild; //重接q的左子樹
delete s;
}
else
{
if(!p->rchild)//被删結點p無右子樹，隻需重接其左子樹
{
q=p;
p=p->lchild;
}
else if(!p->lchild)//被删結點p無左子樹，隻需重接其右子樹
{
q=p;
p=p->rchild;
}
/*――――――――――将p所指的子樹挂接到其雙親結點f相應的位置――――――――*/
if(!f)
T=p; //被删結點為根結點
else if(q==f->lchild)
f->lchild=p; //挂接到f的左子樹位置
else
f->rchild=p;//挂接到f的右子樹位置
delete q;
}
}
void InOrderTraverse(BSTree &T)//中序周遊
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<"\t";
InOrderTraverse(T->rchild);
}
}
int main()
{
BSTree T;
cout<<"請輸入一些整型數，-1結束"<<endl;
CreateBST(T);
cout<<"目前有序二叉樹中序周遊結果為"<<endl;
InOrderTraverse(T);
cout<<endl;
ElemType key;//待查找或待删除内容
cout<<"請輸入待查找關鍵字"<<endl;
cin>>key;
BSTree result=SearchBST(T,key);
if(result)
cout<<"找到"<<key<<endl;
else
cout<<"未找到"<<key<<endl;
cout<<"請輸入待删除關鍵字"<<endl;
cin>>key;
DeleteBST(T,key);
cout<<"目前有序二叉樹中序周遊結果為"<<endl;
InOrderTraverse(T);
return 0;
}
8.4 平衡二叉樹
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct AVLNode{
int data;
int height;
struct AVLNode *lchild;
struct AVLNode *rchild;
}*AVLTree;
AVLTree Empty(AVLTree &T)//删除樹
{
if(T==NULL) return NULL;
Empty(T->lchild);
Empty(T->rchild);
delete T;
return NULL;
}
inline int Height(AVLTree T)//計算高度
{
if(T==NULL) return 0;
return T->height;
}
void updateHeight(AVLTree &T)
{
T->height=max(Height(T->lchild),Height(T->rchild))+1;
}
AVLTree LL_Rotation(AVLTree &T)//LL旋轉
{
AVLTree temp=T->lchild;
T->lchild=temp->rchild;
temp->rchild=T;
updateHeight(T);//更新高度
updateHeight(temp);
return temp;
}
AVLTree RR_Rotation(AVLTree &T)//RR旋轉
{
AVLTree temp=T->rchild;
T->rchild=temp->lchild;
temp->lchild=T;
updateHeight(T);//更新高度
updateHeight(temp);
return temp;
}
AVLTree LR_Rotation(AVLTree &T)//LR旋轉
{
T->lchild=RR_Rotation(T->lchild);
return LL_Rotation(T);
}
AVLTree RL_Rotation(AVLTree &T)//RL旋轉
{
T->rchild=LL_Rotation(T->rchild);
return RR_Rotation(T);
}
AVLTree Insert(AVLTree &T,int x)
{
if(T==NULL) //如果為空，建立新結點
{
T=new AVLNode;
T->lchild=T->rchild=NULL;
T->data=x;
T->height=1;
return T;
}
if(T->data==x) return T;//查找成功，什麼也不做，查找失敗時才插入
if(x<T->data)//插入到左子樹
{
T->lchild=Insert(T->lchild,x);//注意插入後飯後結果挂接到T->lchild
if(Height(T->lchild)-Height(T->rchild)==2)//插入後看是否平衡，如果不平衡顯然是插入的那一邊高度大
{ //沿着高度大的那條路徑判斷
if(x<T->lchild->data)//判斷是LL還是LR,即插入的是lchild節點的lchild 還是rchild
T=LL_Rotation(T);
else
T=LR_Rotation(T);
}
}
else//插入到右子樹
{
T->rchild=Insert(T->rchild,x);
if(Height(T->rchild)-Height(T->lchild)==2)
{
if(x>T->rchild->data)
T=RR_Rotation(T);
else
T=RL_Rotation(T);
}
}
updateHeight(T);
return T;
}
AVLTree adjust(AVLTree &T)//删除結點後，需要判斷是否還是平衡，如果不平衡，就要調整
{
if(T==NULL) return NULL;
if(Height(T->lchild)-Height(T->rchild)==2)//沿着高度大的那條路徑判斷
{
if(Height(T->lchild->lchild)>=Height(T->lchild->rchild))
T=LL_Rotation(T);
else
T=LR_Rotation(T);
}
if(Height(T->rchild)-Height(T->lchild)==2)//沿着高度大的那條路徑判斷
{
if(Height(T->rchild->rchild)>=Height(T->rchild->lchild))
T=RR_Rotation(T);
else
T=RL_Rotation(T);
}
updateHeight(T);
return T;
}
AVLTree Delete(AVLTree &T,int x)
{
if(T==NULL) return NULL;
if(T->data==x)//如果找到删除節點
{
if(T->rchild==NULL)//如果該節點的右孩子為NULL,那麼直接删除
{
AVLTree temp=T;
T=T->lchild;
delete temp;
}
else//否則，将其右子樹的最左孩子作為這個節點，并且遞歸删除這個節點的值
{
AVLTree temp;
temp=T->rchild;
while(temp->lchild)
temp=temp->lchild;
T->data=temp->data;
T->rchild=Delete(T->rchild,T->data);
updateHeight(T);
}
return T;
}
if(T->data>x)//調節删除節點後可能涉及的節點
T->lchild=Delete(T->lchild,x);
if(T->data<x)
T->rchild=Delete(T->rchild,x);
updateHeight(T);
T=adjust(T);
return T;
}
void Preorder(AVLTree T)//前序周遊友善看樹的結果
{
if(T==NULL) return ;
cout<<T->data<<"\t"<<T->height<<endl;
Preorder(T->lchild);
Preorder(T->rchild);
}
void Inorder(AVLTree T)//中序周遊友善看樹的結果
{
if(T==NULL) return ;
Inorder(T->lchild);
cout<<T->data<<"\t"<<T->height<<endl;
Inorder(T->rchild);
}
void Posorder(AVLTree T)//後序周遊友善看樹的結果
{
if(T==NULL) return ;
Posorder(T->lchild);
Posorder(T->rchild);
cout<<T->data<<"\t"<<T->height<<endl;
}
void show(AVLTree T)
{
Preorder(T);
cout<<endl;
Inorder(T);
cout<<endl;
Posorder(T);
}
AVLTree CreateAVL(AVLTree &T)
{
int n,x;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
T=Insert(T,x);
}
return T;
}
int main()
{
int x;
AVLTree root=NULL;
root=Empty(root);
CreateAVL(root);
show(root);
cin>>x;
root=Delete(root,x);
show(root);
return 0;
}
9.1 二分搜尋
#include<iostream>
#include<algorithm>
using namespace std;
const int M=100;
int x,n,i;
int s[M];
int BinarySearch(int s[],int n,int x){//二分查找非遞歸算法
int low=0,high=n-1; //low指向有序數組的第一個元素，high指向有序數組的最後一個元素
while(low<=high){
int middle=(low+high)/2; //middle為查找範圍的中間值
if(x==s[middle]) //x等于查找範圍的中間值，算法結束
return middle;
else if(x>s[middle]) //x大于查找範圍的中間元素，則從左半部分查找
low=middle+1;
else //x小于查找範圍的中間元素，則從右半部分查找
high=middle-1;
}
return -1;
}
int recursionBS(int s[],int x,int low,int high){ //二分查找遞歸算法
//low指向數組的第一個元素，high指向數組的最後一個元素
if(low>high) //遞歸結束條件
return -1;
int middle=(low+high)/2; //計算middle值(查找範圍的中間值)
if(x==s[middle]) //x等于s[middle]，查找成功，算法結束
return middle;
else if(x<s[middle]) //x小于s[middle]，則從前半部分查找
return recursionBS(s,x,low,middle-1);
else //x大于s[middle]，則從後半部分查找
return recursionBS(s,x,middle+1,high);
}
int main(){
cout<<"該數列中的元素個數n為：";
cin>>n;
cout<<"請依次輸入數列中的元素：";
for(i=0;i<n;i++)
cin>>s[i];
sort(s,s+n); //二分查找的序列必須是有序的，如果無序需要先排序
cout<<"排序後的數組為：";
for(i=0;i<n;i++)
cout<<s[i]<<" ";
cout<<endl;
cout<<"請輸入要查找的元素：";
cin>>x;
//i=BinarySearch(s,n,x);
i=recursionBS(s,x,0,n-1);
if(i==-1)
cout<<"該數列中沒有要查找的元素"<<endl;
else
cout<<"要查找的元素在第"<<i+1<<"位"<<endl;//位序和下标差1
return 0;
}
9.2 深度優先搜尋
01Knapsack
#include<iostream>
using namespace std;
const int M=105;
int i,j,n,W;//n表示n個物品，W表示背包的容量
double w[M],v[M];//w[i] 表示第i個物品的重量，v[i] 表示第i個物品的價值
bool x[M]; //x[i]表示第i個物品是否放入背包
double cw; //目前重量
double cp; //目前價值
double bestp; //目前最優價值
bool bestx[M]; //目前最優解
double Bound(int i){//計算上界（即已裝入物品價值+剩餘物品的總價值）
//剩餘物品為第i~n種物品
int rp=0;
while(i<=n){//依次計算剩餘物品的價值
rp+=v[i];
i++;
}
return cp+rp;
}
void Backtrack(int t){//用于搜尋空間數，t表示目前擴充結點在第t層
if(t>n){//已經到達葉子結點
for(j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;//儲存目前最優解
return ;
}
if(cw+w[t]<=W){//如果滿足限制條件則搜尋左子樹
x[t]=1;
cw+=w[t];
cp+=v[t];
Backtrack(t+1);
cw-=w[t];
cp-=v[t];
}
if(Bound(t+1)>bestp){//如果滿足限界條件則搜尋右子樹
x[t]=0;
Backtrack(t+1);
}
}
void Knapsack(double W, int n){
cw=0;//初始化目前放入背包的物品重量為0
cp=0; //初始化目前放入背包的物品價值為0
bestp=0; //初始化目前最優值為0
double sumw=0.0; //用來統計所有物品的總重量
double sumv=0.0; //用來統計所有物品的總價值
for(i=1;i<=n;i++){
sumv+=v[i];
sumw+=w[i];
}
if(sumw<=W){
bestp=sumv;
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"所有的物品均放入背包。";
return;
}
Backtrack(1);
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"放入背包的物品序号為: ";
for(i=1;i<=n;i++){ //輸出最優解
if(bestx[i]==1)
cout<<i<<" ";
}
cout<<endl;
}
int main(){
cout<<"請輸入物品的個數n和背包的容量W:";
cin>>n>>W;
cout<<"請依次輸入每個物品的重量w和價值v,用空格分開:"<<endl;
for(i=1;i<=n;i++)
cin>>w[i]>>v[i];
Knapsack(W,n);
return 0;
}
/*測試資料
4 10
2 6
5 3
4 5
2 4
*/
01Knapsack_2
#include<iostream>
#include<algorithm>//sort函數需要該頭檔案
using namespace std;
const int M=105;
int i,j,n,W;//n表示n個物品，W表示背包的容量
double w[M],v[M];//w[i] 表示第i個物品的重量，v[i] 表示第i個物品的價值
bool x[M]; //x[i]表示第i個物品是否放入背包
double cw; //目前重量
double cp; //目前價值
double bestp; //目前最優價值
bool bestx[M]; //目前最優解
double Bound(int i){//計算上界（即将剩餘物品裝滿剩餘的背包容量時所能獲得的最大價值）
//i表示剩餘物品為第i~n種物品
double cleft=W-cw;//剩餘容量
double brp=0.0;
while(i<=n&&w[i]<cleft){
cleft-=w[i];
brp+=v[i];
i++;
}
if(i<=n)//裝滿背包
brp+=v[i]/w[i]*cleft;
return cp+brp;
}
void Backtrack(int t){//用于搜尋空間數，t表示目前擴充結點在第t層
if(t>n){//已經到達葉子結點
for(j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;//儲存目前最優解
return ;
}
if(cw+w[t]<=W){//如果滿足限制條件則搜尋左子樹
x[t]=1;
cw+=w[t];
cp+=v[t];
Backtrack(t+1);
cw-=w[t];
cp-=v[t];
}
if(Bound(t+1)>bestp){//如果滿足限制條件則搜尋右子樹
x[t]=0;
Backtrack(t+1);
}
}
struct Object{//定義物品結構體，包含物品序号和機關重量價值
int id; //物品序号
double d;//機關重量價值
};
bool cmp(Object a1,Object a2){//按照物品機關重量價值由大到小排序
return a1.d>a2.d;
}
void Knapsack(int W,int n){
double sumw=0; //用來統計所有物品的總重量
double sumv=0; //用來統計所有物品的總價值
Object Q[n]; //物品結構體類型,用于按機關重量價值(價值/重量比)排序
double a[n+1],b[n+1];//輔助數組,用于把排序後的重量和價值指派給原來的重量價值數組
for(i=1;i<=n;i++){
Q[i-1].id=i;
Q[i-1].d=1.0*v[i]/w[i];
sumv+=v[i];
sumw+=w[i];
}
if(sumw<=W){
bestp=sumv;
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"所有的物品均放入背包。";
return;
}
sort(Q,Q+n,cmp);
for(i=1;i<=n;i++){
a[i]=w[Q[i-1].id];//把排序後的資料傳遞過去
b[i]=v[Q[i-1].id];
}
for(i=1;i<=n;i++){
w[i]=a[i];//把排序後的資料傳遞過去
v[i]=b[i];
//cout<<"排序後的重量和價值為: "<<w[i]<<" "<<v[i]<<endl;
}
Backtrack(1);
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"放入背包的物品序号為: ";
for(i=1;i<=n;i++){
if(bestx[i]==1)
cout<<Q[i-1].id<<" ";
}
cout<<endl;
}
int main(){
cout<<"請輸入物品的個數n和背包的容量W:";
cin>>n>>W;
cout<<"請依次輸入每個物品的重量w和價值v,用空格分開:"<<endl;
for(i=1;i<=n;i++)
cin>>w[i]>>v[i];
Knapsack(W,n);
return 0;
}
/*測試資料
4 10
2 6
5 3
4 5
2 4
*/
permutation
#include<iostream>//1..n的全排列
#define MX 50
using namespace std;
int x[MX]; //解分量
int n;
void myarray(int t){
if(t>n){
for(int i=1;i<=n;i++) // 輸出排列
cout<<x[i]<<" ";
cout<<endl;
return ;
}
for(int i=t;i<=n;i++){ // 枚舉
swap(x[t],x[i]); // 交換
myarray(t+1); // 繼續深搜
swap(x[t],x[i]); // 恢複
}
}
int main(){
cout<<"輸入排列的元素個數n(求1..n的排列):"<<endl;
cin>>n;
for(int i=1;i<=n;i++) //初始化
x[i]=i;
myarray(1);
return 0;
}
queen
//program 5-4
#include<iostream>
#include<cmath> //求絕對值函數需要引入該頭檔案
#define M 105
using namespace std;
int n;//n表示n個皇後
int x[M]; //x[i]表示第i個皇後放置在第i行第x[i]列
long long countn; //countn表示n皇後問題可行解的個數
bool Place(int t) //判斷第t個皇後能否放置在第i個位置
{
bool ok=true;
for(int j=1;j<t;j++) //判斷該位置的皇後是否與前面t-1個已經放置的皇後沖突
{
if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))//判斷列、對角線是否沖突
{
ok=false;
break;
}
}
return ok;
}
void Backtrack(int t)
{
if(t>n) //如果目前位置為n,則表示已經找到了問題的一個解
{
countn++;
for(int i=1; i<=n;i++) //列印選擇的路徑
cout<<x[i]<<" ";
cout<<endl;
cout<<"----------"<<endl;
}
else
for(int i=1;i<=n;i++) //分别判斷n個分支,特别注意i不要定義為全局變量,否則遞歸調用有問題
{
x[t]=i;
if(Place(t))
Backtrack(t+1); //如果不沖突的話進行下一行的搜尋
}
}
int main()
{
cout<<"請輸入皇後的個數 n:";
cin>>n;
countn=0;
Backtrack(1);
cout <<"答案的個數是："<<countn<< endl;
return 0;
}
9.3 廣度優先搜尋
01Knapsack
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=10;
bool bestx[N];
//定義結點。每個節點來記錄目前的解。
struct Node{
int cp,rp; //cp為目前裝入背包的物品總價值，rp為剩餘物品的總價值
int rw; //剩餘容量
int id; //物品号
bool x[N];//解向量
Node(){}
Node(int _cp,int _rp,int _rw,int _id){
cp=_cp;
rp=_rp;
rw=_rw;
id=_id;
memset(x,0,sizeof(x));//解向量初始化為0
}
};
struct Goods{//物品
int weight;//重量
int value;//價值
}goods[N];
int bestp,W,n,sumw,sumv;
/*
bestp用來記錄最優解
W為背包最大容量。
n為物品的個數。
sumw為所有物品的總重量。
sumv為所有物品的總價值。
*/
int bfs(){//隊列式分支限界法
int t,tcp,trp,trw;//目前處理的物品序号t，裝入背包物品價值tcp,剩餘容量trw
queue<Node> q; //建立一個普通隊列(先進先出)
q.push(Node(0,sumv,W,1)); //壓入一個初始節點
while(!q.empty()){
Node livenode,lchild,rchild;//定義三個結點型變量
livenode=q.front();//取出隊頭元素作為目前擴充結點livenode
q.pop(); //隊頭元素出隊
t=livenode.id;//目前處理的物品序号
// 搜到最後一個物品的時候不需要往下搜尋
// 如果目前的背包沒有剩餘容量(已經裝滿)了，不再擴充
if(t>n||livenode.rw==0){
if(livenode.cp>=bestp){//更新最優解和最優值
for(int i=1;i<=n;i++)
bestx[i]=livenode.x[i];
bestp=livenode.cp;
}
continue;
}
if(livenode.cp+livenode.rp<bestp)//判斷目前結點是否滿足限界條件，如果不滿足不再擴充
continue;
tcp=livenode.cp; //目前背包中的價值
trp=livenode.rp-goods[t].value; //不管目前物品裝入與否，剩餘價值都會減少。
trw=livenode.rw; //背包剩餘容量
if(trw>=goods[t].weight){ //擴充左孩子，滿足限制條件，可以放入背包
lchild.rw=trw-goods[t].weight;
lchild.cp=tcp+goods[t].value;
lchild=Node(lchild.cp,trp,lchild.rw,t+1);
for(int i=1;i<t;i++)//複制以前的解向量
lchild.x[i]=livenode.x[i];
lchild.x[t]=true;
if(lchild.cp>bestp)//比最優值大才更新
bestp=lchild.cp;
q.push(lchild);//左孩子入隊
}
if(tcp+trp>=bestp){//擴充右孩子,滿足限界條件，不放入背包
rchild=Node(tcp,trp,trw,t+1);
for(int i=1;i<t;i++)//複制以前的解向量
rchild.x[i]=livenode.x[i];
rchild.x[t]=false;
q.push(rchild);//右孩子入隊
}
}
return bestp;//傳回最優值
}
int main(){
cin>>n>>W;//輸入物品的個數和背包的容量
bestp=0; //bestv用來記錄最優解
sumw=0; //sumw為所有物品的總重量。
sumv=0; //sumv為所有物品的總價值
for(int i=1;i<=n;i++){//輸入每個物品的重量和價值,用空格分開
cin>>goods[i].weight>>goods[i].value;//輸入第i件物品的重量和價值。
sumw+=goods[i].weight;
sumv+=goods[i].value;
}
if(sumw<=W){
bestp=sumv;
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
return 0;
}
bfs();
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"放入背包的物品序号為: ";
for(int i=1;i<=n;i++){// 輸出最優解
if(bestx[i])
cout<<i<<" ";
}
return 0;
}
/*測試資料
4 10
2 6 5 3 4 5 2 4
*/
01Knapsack_2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=10;
bool bestx[N]; //記錄最優解
int w[N],v[N];//輔助數組,用于存儲排序後的重量和價值
struct Node{//定義結點,記錄目前結點的解資訊
int cp; //已裝入背包的物品價值
double up; //價值上界
int rw; //背包剩餘容量
int id; //物品号
bool x[N];
Node() {}
Node(int _cp,double _up,int _rw,int _id){
cp=_cp;
up=_up;
rw=_rw;
id=_id;
memset(x, 0, sizeof(x));
}
};
struct Goods{ //物品結構體
int weight;//重量
int value;//價值
}goods[N];
struct Object{//輔助物品結構體，用于按機關重量價值(價值/重量比)排序
int id; //序号
double d;//機關重量價值
}S[N];
bool cmp(Object a1,Object a2){//排序優先級，按照物品機關重量價值由大到小排序
return a1.d>a2.d;
}
bool operator <(const Node &a, const Node &b){//隊列優先級。up越大越優先
return a.up<b.up;
}
int bestp,W,n,sumw,sumv;
/*
bestv 用來記錄最優解。
W為背包的最大容量。
n為物品的個數。
sumw為所有物品的總重量。
sumv為所有物品的總價值。
*/
double Bound(Node tnode){//計算節點的上界
double maxvalue=tnode.cp;//已裝入背包物品價值
int t=tnode.id;//排序後序号
double left=tnode.rw;//剩餘容量
while(t<=n&&w[t]<=left){
maxvalue+=v[t];
left-=w[t++];
}
if(t<=n)
maxvalue+=double(v[t])/w[t]*left;
return maxvalue;
}
int priorbfs(){//優先隊列式分支限界法
int t,tcp,trw;//目前處理的物品序号t，目前裝入背包物品價值tcp,目前剩餘容量trw
double tup; //目前價值上界tup
priority_queue<Node> q; //建立一個優先隊列
q.push(Node(0,sumv,W,1));//初始化,根結點加入優先隊列
while(!q.empty()){
Node livenode, lchild, rchild;//定義三個結點型變量
livenode=q.top();//取出隊頭元素作為目前擴充結點livenode
q.pop(); //隊頭元素出隊
t=livenode.id;//目前處理的物品序号
// 搜到最後一個物品的時候不需要往下搜尋。
// 如果目前的背包沒有剩餘容量(已經裝滿)了，不再擴充。
if(t>n||livenode.rw==0){
if(livenode.cp>=bestp){//更新最優解和最優值
for(int i=1;i<=n;i++)
bestx[i]=livenode.x[i];
bestp=livenode.cp;
}
continue;
}
if(livenode.up<bestp)//如果不滿足不再擴充
continue;
tcp=livenode.cp; //目前背包中的價值
trw=livenode.rw; //背包剩餘容量
if(trw>=w[t]){ //擴充左孩子，滿足限制條件，可以放入背包
lchild.cp=tcp+v[t];
lchild.rw=trw-w[t];
lchild.id=t+1;
tup=Bound(lchild); //計算左孩子上界
lchild=Node(lchild.cp,tup,lchild.rw,lchild.id);
for(int i=1;i<=n;i++)//複制以前的解向量
lchild.x[i]=livenode.x[i];
lchild.x[t]=true;
if(lchild.cp>bestp)//比最優值大才更新
bestp=lchild.cp;
q.push(lchild);//左孩子入隊
}
rchild.cp=tcp;
rchild.rw=trw;
rchild.id=t+1;
tup=Bound(rchild);//計算右孩子上界
if(tup>=bestp){//擴充右孩子，滿足限界條件，不放入
rchild=Node(tcp,tup,trw,t+1);
for(int i=1;i<=n;i++)//複制以前的解向量
rchild.x[i]=livenode.x[i];
rchild.x[t]=false;
q.push(rchild);//右孩子入隊
}
}
return bestp;//傳回最優值。
}
int main(){
bestp=0; //bestv用來記錄最優解
sumw=0; //sumw為所有物品的總重量。
sumv=0; //sumv為所有物品的總價值
cin>>n>>W;
for(int i=1;i<=n;i++){
cin>>goods[i].weight>>goods[i].value;//輸入第i件物品的重量和價值。
sumw+=goods[i].weight;
sumv+=goods[i].value;
S[i-1].id=i;
S[i-1].d=1.0*goods[i].value/goods[i].weight;
}
if(sumw<=W){
bestp=sumv;
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
return 0;
}
sort(S,S+n,cmp);//按價值重量比非遞增排序
for(int i=1;i<=n;i++){//把排序後的資料傳遞給輔助數組
w[i]=goods[S[i-1].id].weight;
v[i]=goods[S[i-1].id].value;
}
priorbfs();//優先隊列分支限界法
cout<<"放入背包的物品最大價值為: "<<bestp<<endl;
cout<<"放入背包的物品序号為: ";
for(int i=1;i<=n;i++){ //輸出最優解
if(bestx[i])
cout<<S[i-1].id<<" ";//輸出原物品序号(排序前的)
}
return 0;
}
/*測試資料
4 10
2 6 5 3 4 5 2 4
*/
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)