本文共 12998 字，大约阅读时间需要 43 分钟。

一、实验目的：

1、领会图的两种主要存储结构和图的基本运算算法设计；
2、领会图的两种遍历算法；
3、领会Prim算法求带权连通图中最小生成树的过程和相关算法设计；
4、掌握深度优先遍历和广度优先遍历算法在图路径搜索问题中的应用；
5、深入掌握图遍历算法在求解实际问题中的应用。

二、使用仪器、器材

微机一台
操作系统：WinXP
编程软件：C/C++编程软件

三、实验内容及原理

填入自己的内容（思路或算法流程图、源代码、说明等）

1、教材P310实验题1：实现图的邻接矩阵和邻接表的存储

编写一个程序graph.cpp，设计带权图的邻接矩阵与邻接表的创建和输出运算，并在此基础上设计一个主程序exp8-1.cpp完成以下功能。
（1）建立如图8.54所示的有向图G的邻接矩阵，并输出之。
（2）建立如图8.54所示的有向图G的邻接表，并输出之。
（3）销毁图G的邻接表。

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define maxn 1024   //最大顶点数int matrix[maxn][maxn];   //邻接矩阵int n,m; //顶点数，边数/*边结点*/struct ArcNode{       int adjvex;  //该边所指向的顶点的位置    int lowcost; //权值    ArcNode* next;  //指向的下一条边的指针};ArcNode* ArcList[maxn*(maxn-1)];   //所有边结点int in = 0;   //下标/*顶点*/struct{       ArcNode* firstarc;}AdjList[maxn];/*增加一条从i指向j的权值为k的顶点*/void add(int i,int j,int k){       matrix[i][j] = k;    ArcNode* p = new ArcNode();    p->adjvex = j;  //它指向的是j顶点    p->lowcost = k; //权值为k    //p插入到链表头部    p->next = AdjList[i].firstarc;    AdjList[i].firstarc = p;    ArcList[in++] = p;  //把这个边结点存储到数组中}int main() {   	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    n = 6;    m = 10;	//初始化邻接矩阵    for(int i = 0;i<n;++i){           for(int j = 0;j<n;++j){               matrix[i][j] = -1;        }    }    //初始化AdjList    for(int i = 0;i<n;++i){           AdjList[i].firstarc = NULL;    }    //增加m条边    add(0,1,5);    add(0,3,3);    add(1,2,4);    add(2,0,8);    add(2,5,9);    add(3,2,5);    add(3,5,6);    add(4,3,5);    add(5,4,1);    add(5,0,3);    //打印邻接矩阵    cout << "adjacent matrix:" << endl;    for(int i = 0;i<n;++i){           for(int j = 0;j<n;++j){               cout << matrix[i][j] << " \n"[j == n-1];        }    }    //打印邻接表    cout << "adjacency list:" << endl;    ArcNode* p = 0;    for(int i = 0;i < n;++i){           p = AdjList[i].firstarc;        cout << i << " : ";        while(p){               cout << p->adjvex << "(" << p->lowcost << ")" << " -> ";            p = p->next;        }        cout << "^" << endl;    }    p = 0;    //销毁邻接表    for(int i = 0;i<in;++i){           delete ArcList[i];  //删除        ArcList[i] = 0;  //指针置空    }    //修改每个顶点的firstarc为空    for(int i = 0;i<n;++i){           AdjList[i].firstarc = 0;    }    in = 0;	return 0;}

2、教材P310实验题2：实现图的遍历算法

编写一个程序travsal.cpp实现图的两种遍历运算，并在此基础上设计一个程序exp8-2.cpp完成以下功能。
（1） 输出如图8.54的有向图G从顶点0开始的深度优先遍历序列（递归算法）。
（2） 输出如图8.54的有向图G从顶点0开始的深度优先遍历算法（非递归算法）。
（3） 输出如图8.54的有向图G从顶点0开始的广度优先遍历序列。

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define maxn 1024   //最大顶点数int n,m; //顶点数，边数/*边结点*/struct ArcNode{       int adjvex;  //该边所指向的顶点的位置    int lowcost; //权值    ArcNode* next;  //指向的下一条边的指针};ArcNode* ArcList[maxn*(maxn-1)];   //所有边结点int in = 0;   //下标/*顶点*/struct{       ArcNode* firstarc;}AdjList[maxn];/*增加一条从i指向j的权值为k的顶点*/void add(int i,int j,int k){       ArcNode* p = new ArcNode();    p->adjvex = j;  //它指向的是j顶点    p->lowcost = k; //权值为k    //p插入到链表头部    p->next = AdjList[i].firstarc;    AdjList[i].firstarc = p;    ArcList[in++] = p;  //把这个边结点存储到数组中}/*    销毁邻接表*/void destoryArc(){       //销毁邻接表    for(int i = 0;i<in;++i){           delete ArcList[i];  //删除        ArcList[i] = 0;  //指针置空    }    //修改每个顶点的firstarc为空    for(int i = 0;i<n;++i){           AdjList[i].firstarc = 0;    }}bool tag[maxn]; //访问标记/*深度优先遍历序列（递归）v : 当前访问的顶点*/void dfs1(int v = 0){       cout << v << " ";   //输出这个顶点    tag[v] = 1;     //给这个顶点加入标记    ArcNode* p = AdjList[v].firstarc; //邻接表    while(p){     //遍历所有和这个顶点相连的边        if(!tag[p->adjvex])  //如果准备访问的顶点没加访问标记，就加入            dfs1(p->adjvex);  //递归        p = p->next;   //指针后移    }    p = 0;  //指针置空}int stk[maxn];  //模拟栈int si = 0;  //栈里元素个数/*深度优先遍历 非递归*/void dfs2(){       memset(tag,0,sizeof(tag));  //清空访问标记    int v = 0;  //当前访问的顶点    si = 0;  //清空栈的元素    stk[si++] = v;  //入栈    tag[v] = 1;  //标记初始顶点    cout << "dfs(not recursion):";    ArcNode*p = 0;    while(si){           //只要栈内还有元素，就一直循环        v = stk[--si];  //出栈        cout << v << " ";  //输出        p = AdjList[v].firstarc;        while(p){               if(!tag[p->adjvex]){                   //只要没被访问过就入栈                stk[si++] = p->adjvex;                tag[p->adjvex] = 1;  //标记            }            p = p->next;  //指针后移        }        p = 0; //指针置空    }    cout << endl;}int que[maxn];  //队列int qi = 0,qj = 0;  //头指针和尾指针/*广度优先*/void bfs(){       memset(tag,0,sizeof(tag));  //清空访问标记    int v = 0;  //当前顶点    qi = 0;    qj = 0;    tag[v] = 1;  //标记初始顶点    cout << "bfs:";    que[qj++] = v;   //入队    ArcNode*p = 0;    while(qi != qj){           //只要队列不空，就一直循环        v = que[qi++];  //出队        cout << v << " "; //输出顶点        qi %= maxn; //如果qi >= maxn，则从0开始        p = AdjList[v].firstarc;        while(p){               if(!tag[p->adjvex]){                   //只要没被访问过就入栈                que[qj++] = p->adjvex;                qj %= maxn;                tag[p->adjvex] = 1;  //标记            }            p = p->next;  //指针后移        }        p = 0;  //指针置空    }    cout << endl;}int main() {   	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    n = 6;    m = 10;    //初始化AdjList    for(int i = 0;i<n;++i){           AdjList[i].firstarc = NULL;    }    //增加m条边    add(0,1,5);    add(0,3,3);    add(1,2,4);    add(2,0,8);    add(2,5,9);    add(3,2,5);    add(3,5,6);    add(4,3,5);    add(5,4,1);    add(5,0,3);    //-----------深度优先（递归）----------    memset(tag,0,sizeof(tag));  //清空访问标记    cout << "dfs(recursion):";    dfs1();    cout << endl;    memset(tag,0,sizeof(tag));  //清空访问标记    //-----------深度优先（非递归）----------    dfs2();    //-----------广度优先----------    bfs();    destoryArc();  //销毁邻接表	return 0;}

3、教材P311实验题5：采用Prim算法求最小生成树

编写一个程序exp8-5.cpp，实现求带权连通图中最小生成树的Prim算法，如图8.55所示的带权连通图G，输出从顶点0出发的一棵最小生成树。

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define maxn 100int matrix[maxn][maxn];  //邻接矩阵int n,m;bool tag[maxn];  //标记，tag[i] = true表示顶点i在集合U中struct{       int adjvex;  //最小边在U中的那个顶点    int lowcost;    //权值}closedge[maxn];/*增加一条连接i和j的权值为k的边*/void add(int i,int j,int k){       matrix[i][j] = k;    matrix[j][i] = k;}int main() {   	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    //初始化邻接矩阵    for(int i = 0;i < maxn;++i){           for(int j = 0;j < maxn;++j){               matrix[i][j] = -1;        }    }	n = 6;  //顶点6个    m = 10; //边10条    add(0,1,5);    add(1,2,4);    add(2,3,5);    add(3,4,5);    add(4,5,1);    add(5,0,3);    add(0,2,8);    add(0,3,7);    add(2,5,9);    add(3,5,6);    int v = 0;  //当前顶点为0    tag[0] = 1;  //从顶点0出发，所以要把顶点0加入到集合U    //初始化closedge    for(int i = 0;i<n;++i){           closedge[i] = {   0,matrix[i][0]};    }    int T = n-1;    //循环执行n-1次    while(T--){           //寻找closedge里一端不在集合U中的边        int mi = INT_MAX;        for(int i = 0;i<n;++i){               if(!tag[i] && closedge[i].lowcost != -1 && closedge[i].lowcost < mi){                   mi = closedge[i].lowcost;                v = i;            }        }            tag[v] = 1;   //加入集合U中        cout << v << " --- " << closedge[v].adjvex << endl; //输出这条边        //更新lowcost        for(int i = 1;i<n;++i){               if(!tag[i] && (closedge[i].lowcost == -1 || (matrix[i][v] != -1 && closedge[i].lowcost > matrix[i][v]))){                   closedge[i].lowcost = matrix[i][v];                closedge[i].adjvex = v;            }        }            }	return 0;}

4、教材P311实验题10：求有向图的简单路径

编写一个程序exp8-10.cpp，设计相关算法完成以下功能。
（1） 输出如图8.56的有向图G从顶点5到顶点2的所有简单路径。
（2） 输出如图8.56的有向图G从顶点5到顶点2的所有长度为3的简单路径。
（3） 输出如图8.56的有向图G从顶点5到顶点2的最短路径。

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define maxn 100   //最大顶点数int matrix[maxn][maxn];//邻接矩阵int n,m; //顶点个数，边的个数bool tag[maxn];  //标记这个顶点是否已经访问过int tmp[maxn];  //记录路径/*深度优先遍历找所有路径now:当前顶点dest:目标i:当前长度*/void dfs(int now,int dest,int i = 0){       tmp[i] = now;    if(now == dest){           //到达终点，输出        for(int j = 0;j<=i;++j){               cout << tmp[j] << " \n"[j == i];        }        return;    }    //遍历从该顶点出发的所有边    for(int j = 0;j<n;++j){           if(matrix[now][j] && !tag[j]){               //边存在并且未被访问过            tag[j] = 1;   //标记            dfs(j,dest,i+1);    //递归            tag[j] = 0;  //取消标记        }    }}/*深度优先遍历找指定长度的所有路径now:当前顶点dest:目标len:指定长度i:当前长度*/void dfs1(int now,int dest,int len,int i = 0){       tmp[i] = now;    if(now == dest){           //到达终点，并且长度为len，输出        if(i == len)            for(int j = 0;j<=i;++j){                   cout << tmp[j] << " \n"[j == i];            }        return;    }    if(i >= len){           return;    }    //遍历从该顶点出发的所有边    for(int j = 0;j<n;++j){           if(matrix[now][j] && !tag[j]){               //边存在并且未被访问过            tag[j] = 1;   //标记            dfs1(j,dest,len,i+1);    //递归            tag[j] = 0;  //取消标记        }    }}/*使用广度优先遍历计算从start到end的最短路径*/int last[maxn];  //记录在bfs过程中的顶点的上一顶点void bfs(int start,int end){       queue<int> q;  //队列    memset(tag,0,sizeof(tag));  //重置标记    memset(last,-1,sizeof(last));  //重置上一顶点的记录    cout << "Shortest path from vertex 5 to vertex 2 is:" << endl;    q.push(start);  //把开始顶点加入到队列    tag[start] = 1;  //给开始顶点添加标记    int v;  //当前顶点    while(!q.empty()){           //取出队列中的第一个元素        v = q.front();        q.pop();        if(v == end){               //找到结束点            break;        }        //遍历从v开始的边        for(int i = 0;i<n;++i){               //路径存在并且未被访问过            if(!tag[i] && matrix[v][i]){                   tag[i] = 1; //标记                last[i] = v;  //记录上一顶点                q.push(i);            }        }    }    int i = 0;  //tmp数组的下标（路径长度）    v = end;    while(v != -1){           tmp[i++] = v;        v = last[v];  //跳到上一顶点    }    //输出路径    while(i){           cout << tmp[--i] << " ";    }    cout << endl;}int main() {   	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    // 初始化邻接矩阵    for(int i = 0;i<n;++i){           for(int j = 0;j<n;++j){               matrix[i][j] = 0;        }    }	n = 6;    m = 12;    //下面m行建图    matrix[0][1] = 1;    matrix[0][3] = 1;    matrix[1][2] = 1;    matrix[2][5] = 1;    matrix[2][0] = 1;    matrix[3][2] = 1;    matrix[3][5] = 1;    matrix[4][3] = 1;    matrix[5][4] = 1;    matrix[5][3] = 1;    matrix[5][1] = 1;    matrix[5][0] = 1;    //（1）	输出有向图G从顶点5到顶点2的所有简单路径。    cout << "All the paths from vertex 5 to vertex 2:"<< endl;    memset(tag,0,sizeof(0));  //初始化tag    tag[5] = 1;  //标记5    dfs(5,2);    tag[5] = 0;  //取消标记5    //（2）	输出有向图G从顶点5到顶点2的所有长度为3的简单路径。    cout << "All paths from vertex 5 to vertex 2 of length 3:" << endl;    memset(tag,0,sizeof(0));  //初始化tag    tag[5] = 1;  //标记5    dfs1(5,2,3);    tag[5] = 0;  //取消标记5    // （3）输出有向图G从顶点5到顶点2的最短路径。    bfs(5,2);	return 0;}

5、教材P313实验题14：用图搜索方法求解如图3.28（教材P119）的迷宫问题（也可以自建迷宫）

编写一个程序exp8-14.cpp，完成以下功能。
（1） 建立一个迷宫对应的邻接表表示。
（2） 采用深度优先遍历算法输出从入口（1，1）到出口（M,N）的所有迷宫路径。

#include <bits/stdc++.h>using namespace std;typedef long long ll;struct ArcNode;  //提前声明一下int m[6][6] = {       {   0,0,0,0,0,0},    {   0,1,1,1,0,0},    {   0,1,0,1,1,0},    {   0,1,1,1,0,0},    {   0,0,1,1,1,0},    {   0,0,0,0,0,0}};  //地图int DIRECTIONS[2][4] = {   {   1,-1,0,0},{   0,0,1,-1}};/*顶点*/struct Point{       int x,y;    ArcNode* firstArc;}*mp[6][6];/*边*/struct ArcNode{       Point* p;   //该边指向的顶点    ArcNode* next; //下一个指针};bool tag[6][6];  //标记是否有被访问过/*深度优先搜索x,y:坐标i:path的下标*/Point* path[6*6];  //记录路径void dfs(int x,int y,int i = 0){       path[i] = mp[x][y];    if(x == 4 && y == 4){           //到达终点        for(int j = 0;j<=i;++j){               cout << "(" << path[j]->x << "," << path[j]->y << ")" << " \n"[j == i];  //输出路径        }        return;    }    ArcNode*p = 0;  //邻接链表    p = mp[x][y]->firstArc;  //p一开始指向firstArc    int xi,yi;    while(p){     //只要p不为空，就一直循环        xi = p->p->x;         yi = p->p->y;        if(!tag[xi][yi]){               //只有没被访问过才能访问            tag[xi][yi] = 1;  //标记            dfs(xi,yi,i+1);   //递归            tag[xi][yi] = 0;  //取消标记        }        p = p->next;    }}int main() {   	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    //初始化mp数组    for(int i = 0;i<6;++i){           for(int j = 0;j<6;++j){               if(m[i][j]){                   mp[i][j] = new Point();                mp[i][j]->x = i;                mp[i][j]->y = j;                mp[i][j]->firstArc = 0;            }else{                   mp[i][j] = 0;            }                    }    }    //初始化邻接表    int x,y;    for(int i = 1;i<=4;++i){           for(int j = 1;j<=4;++j){               if(m[i][j]){                   for(int k = 0;k<4;++k){                       x = i + DIRECTIONS[0][k];                    y = j + DIRECTIONS[1][k];                    if(m[x][y]){                           //地图上有点                        ArcNode* p = new ArcNode();                        p->p = mp[x][y];                         //链表常规插入操作                        p->next = mp[i][j]->firstArc;                        mp[i][j]->firstArc = p;                    }                }            }                    }    }    memset(tag,0,sizeof(tag));  //初始化tag数组    cout << "The maze path from entry to exit is as follows:" << endl;    tag[1][1] = 1;  //给起点添加访问标记    dfs(1,1);   //深度优先	return 0;}