实验07 图的两种存储和遍历

实验学时：2学时 实验类型：上机

背景知识：图的存储、遍历及其应用。

目的要求：

1．掌握图的存储思想及其存储实现。

2．掌握图的深度、广度优先遍历算法思想及其程序实现。

实验内容：

（1） 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。 （2） 输出该邻接表。

（3） 在有向图的邻接表的基础上计算各顶点的度，并输出。 （4） 采用邻接表存储实现无向图的深度优先遍历。 （5） 采用邻接表存储实现无向图的广度优先遍历。

（6） 在主函数中设计一个简单的菜单，分别调试上述算法。 （7） *综合训练

地下迷宫探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式：

输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例：

6 8 1 1 2 2 3 3 4 4 5 5 6 6 4 3 6 1 5 输出样例：

1 2 3 4 5 6 5 4 3 2 1

实验说明：

1．类型定义（邻接表存储）

#define MAX_VERTEX_NUM 20 //顶点最大个数 typedefstructArcNode{ intadjvex;

structArcNode *nextarc; intweight; //边的权值

}ArcNode; //表结点

#define VertexTypeint //顶点元素类型 typedefstructVNode{ VertexType data; ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM]; // typedefstruct{

AdjList vertices;

intvexnum,arcnum;//顶点的实际数，边的实际数 int kind;

}ALGraph;

2．上述类型定义可以根据实际情况适当调整。 3．算法4、5分别利用栈、队列实现非递归算法。

注意问题：

1．注意理解各算法实现时所采用的存储结构。

2．注意区别正、逆邻接。

地下迷宫探索

#include #include #include #include #include #include #include #include

using namespace std;

#define N 1005

int n , m , s ;

vector vt[N] ;

bool cmp(int x ,int y) {

return x < y ; }

bool vis[N] ;

deque que ;

bool flag ; // 输出控制

int outLen ; // 判断是否可以遍历所有节点

void dfs() {

int sta = que.back() ; if(sta == s && vis[s]) return ;

int len = vt[sta].size(); if(len > 1)

sort(vt[sta].begin() ,vt[sta].end() , cmp);

for(int i = 0 ; i < len ;i++) {

int nextNum = vt[sta][i] ; if(!vis[nextNum]) {

if(!flag) // 打印入队列的路径

{

printf(\"%d\ flag = true ; outLen ++ ; }else{

printf(\" %d\ outLen ++ ; }

que.push_back(nextNum) ; vis[sta] = true ; dfs() ; } }

// 打印回去的路径

if(!que.empty()) // 当dfs 找不到的时候 就出队列 并设置为true 输出 {

int top = que.back() ; que.pop_back() ; vis[top] = true ; if(!flag) {

printf(\"%d\ flag = true ; outLen ++ ; }else{

printf(\" %d\ outLen ++ ; } } }

int main() {

//freopen(\"in.txt\

while( scanf(\"%d%d%d\ {

int i ;

int v1 , v2 ;

for(i = 1 ; i <= n ; i++) {

vt[i].clear() ; }

for(i = 0 ;i < m ; i++) {

scanf(\"%d%d\" , &v1 , &v2); vt[v1].push_back(v2) ; vt[v2].push_back(v1) ; }

for(i = 1 ; i <= n ; i++) {

vis[i] = false ; }

while(!que.empty()) {

que.pop_back(); }

que.push_back(s) ; flag = false ; outLen = 0 ; dfs();

if(outLen != 2*n -1) printf(\" 0\") ; printf(\"\\n\") ; }

return 0 ; }