图遍历操作的实现

一、实验学时： 2学时 二、实验目的

1．实现图的基本操作 2．实现图的遍历操作

三、实验内容（2,3选做）

1. 深度优先和广度优先搜索图 2. 求图的关键路径 3．求图的最短路径

四、主要仪器设备及耗材

硬件：计算机一台

软件：VC++ 6.0，MSDN2003或者以上版本

五、实验步骤

1. 分析问题 2. 写出算法 3. 编制程序 4. 上机调试 5. 分析结果

六、程序清单

#include #include using namespace std;

#define MaxInt 32767 //权值的最大值 #define MVNum 100 //最大顶点数 #define max 50

//邻接矩阵存储结构定义 typedef struct{ char vexs[MVNum]; //存放顶点的数组 int arcs[MVNum][MVNum]; //存放邻接矩阵的数组 int vexnum,arcnum; //顶点数和边（弧）数 }AMGraph;

//边（弧）结点结构定义 typedef struct ArcNode{ int adjvex; struct ArcNode* nextarc;

int weight; }ArcNode;

//顶点类型定义

typedef struct VNode{ char data; ArcNode* firstarc;

}VNode,AdjList[MVNum]; //顶点数组类型定义

//邻接表结构定义 typedef struct{ AdjList vertices; //顶点数组 int vexnum,arcnum; //顶点数和边（弧）数 }ALGraph;

//顺序队列结构定义 typedef struct{ int front; //队头 int rear; //队尾 char base[MVNum]; //存放队列元素的数组 }SqQueue;

bool visited[MVNum]; //存放图中顶点访问标志的数组

//初始化队列

void InitQueue(SqQueue &Q) { Q.front = Q.rear = 0; }

//判断队列Q是否为空，为空返回true，非空返回false bool QueueEmpty(SqQueue Q) { if(Q.rear == Q.front ) return true; else return false; }

//入队操作，将n插入顺序队列Q的尾部 void EnQueue(SqQueue &Q,int n) { if(Q.rear-Q.front == MVNum) //队满时，不能执行入队操作 exit(-1);

else { Q.base[Q.rear] = n; Q.rear++; } }

//出队操作，删除队列Q的队头元素，被删元素用n返回 void DeQueue(SqQueue &Q,int &n) { if(QueueEmpty(Q)) //若队列为空，不能执行出队操作 exit(-1); else { n = Q.base [Q.front]; Q.front++; } }

//在以邻接表方式存储的图G中，查找值为ch的顶点的位置 int LocateVex(ALGraph G,char ch) { for(int i=0;i//在以邻接矩阵方式存储的图G中，查找值为ch的顶点的位置 int LocateVex1(AMGraph G,char ch) { for(int i=0;i//以邻接表为存储结构，创建无向图G void CreateUDG_AL(ALGraph &G) { int i, j, k; char v1, v2;

ArcNode *p1,*p2; cout<<\"请输入要创建的无向图的顶点数和边数，中间用空格分隔:\"<>G.vexnum>>G.arcnum; //输入总顶点数，总边数 cout<<\"请输入图中的顶点\"<>G.vertices[i].data; //输入顶点值 G.vertices[i].firstarc=NULL; //初始化第i个表头结点的指针域为NULL } for(k=0;k> v1 >> v2; //输入一条边依附的两个顶点 i = LocateVex(G, v1); //查找顶点v1在图中的位置 j = LocateVex(G, v2); //查找顶点v2在图中的位置,即顶点在G.vertices中的序号 p1=new ArcNode; //创建一个新的边结点p1 p1->adjvex=j; //设置p1的邻接点域为j p1->nextarc= G.vertices[i].firstarc; //把边结点p1插入到第i个边链表中（前插法） G.vertices[i].firstarc=p1; //将新结点p1插入顶点vi的边表头部 p2=new ArcNode; //创建另一个对称的新的边结点p2 p2->adjvex=i; //设置p1的邻接点域为i p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2; //将新结点p2插入顶点vj的边表头部 } }

//以邻接矩阵为存储结构，创建有向图G void CreateDG_AM(AMGraph &G) { int i, j, k; char v1, v2; cout<<\"请输入要创建的有向网的顶点数和边数，中间用空格分隔:\"<>G.vexnum>>G.arcnum; //输入总顶点数，总边数 cout<<\"请输入顶点\"<>G.vexs [i]; } for(i=0;i} //依次输入每条弧及权值，建立邻接矩阵 for(k=0;k>v1>>v2; //输入弧尾v1，弧头v2和权值weight i = LocateVex1(G,v1); //确定v1和v2在G中的位置，即顶点数组的下标 j = LocateVex1(G,v2); G.arcs[i][j]=1; //将邻接矩阵中第i行第j列的值修改为权值 } }

//以邻接矩阵为存储结构，创建有向网G void CreateDN_AM(AMGraph &G) { int i, j, k, w; char v1, v2; cout<<\"请输入要创建的有向网的顶点数和边数，中间用空格分隔:\"<>G.vexnum>>G.arcnum; //输入总顶点数，总边数 cout<<\"请输入顶点\"<>G.vexs [i]; } for(i=0;i>v1>>v2>>w; //输入弧尾v1，弧头v2和权值w i = LocateVex1(G,v1); //确定v1和v2在G中的位置，即顶点数组的下标 j = LocateVex1(G,v2); G.arcs[i][j]=w; //将邻接矩阵中第i行第j列的值修改为权值 } }

//从图中的第v个顶点出发，深度遍历图G（以邻接表为存储结构） void DFS(ALGraph G,int v) { ArcNode *p; int w; cout << G.vertices[v].data << \" \"; //输出第v个顶点 visited[v] = true; //设置第v个顶点的访问标志 //依次从v的未被访问过的邻接点出发，深度遍历图G p = G.vertices[v].firstarc; //p指向v的边链表的第一个边结点 while(p) //边结点非空 { w = p->adjvex; //表示w是v的邻接点 if(!visited[w]) DFS(G, w); //如果w未访问，则递归调用DFS p = p->nextarc; //p指向下一个边结点 } }

//深度遍历图G

void DFSTraverse(ALGraph G) { int v; for(v=0;v//从图中的第v个顶点出发，广度遍历图G（以邻接表为存储结构） void BFS(ALGraph G,int v) { SqQueue Q; //Q为顺序队列 ArcNode *p; int w,u; InitQueue(Q); //初始化队列Q cout<p = G.vertices[u].firstarc; while(p) { w = p->adjvex; //取得邻接点w if(!visited[w]) { cout<nextarc; //处理下一个边（弧）结点 } } }

//广度遍历图G

void BFSTraverse(ALGraph G) { int v; for(v=0;v//使用迪杰斯特拉算法求第v0个顶点到其它顶点的最短路径 void ShortestPath_DIJ(AMGraph G,int v0) { int D[MVNum],Path[MVNum],i,v,w,min; bool S[MVNum]; for(v=0;vD[v0] = 0; //循环G.vexnum-1次,求第v0个顶点到图中其它顶点的最短距离 for(i=1;i= 0; i--) { cout << \"->\"; cout <cout<void AdjacentMatrix(AMGraph &G) { for(int i = 0 ; i < G.vexnum ; ++i) { for( int j = 0; j < G.vexnum; ++j) { if(j != G.vexnum - 1) { if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << \"\\"; else cout << \"∞\" << \"\\"; } else { if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] <void AdjacencyList(ALGraph &G) { for(int i = 0 ; 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; p = p->nextarc; } } cout << endl; } }

int main() { ALGraph G; AMGraph G1; char ch; int k;

//以下操作完成无向图G的创建(基于邻接表存储方式)、G的深度遍历和广度遍历 cout<<\"以下操作完成无向图G的创建(基于邻接表存储方式)、G的深度遍历和广度遍历\"<>ch; //输入源点 k=LocateVex1(G1,ch); //求源点在G1中的位置k ShortestPath_DIJ(G1,k); //使用迪杰斯特拉算法求第k个顶点到其它顶点的最短路径 return 0; }

七、运行结果及分析

一、无向图G的邻接表和深度、广度遍历：

下图是一种解法：

二、无向网G1的邻接矩阵和迪杰斯特拉求最短路径： 下图是一种解法：

三、问题与解决方法：

问题一：广度遍历序列和预想的不一样。

解决方法：在查看了一下我的广度遍历BFS(ALGraph G,int v)之后，我找出来原来是代码写错了。改正后，可以得到想要的结果啦。

问题二：在用迪杰斯特拉算法，输出源点到其它顶点的最短路径及路径长度时，输出的最短路径都是倒着的，很不舒服。

解决方法：首先，我自己尝试修改了一下，达不到正序排列的效果，于是，我就上网查了一下，做了一些调整后，终于实现了预期的效果。