杭电数据结构课程实践-哈密顿图的判断

90 阅读 0 评论 60 点赞

我是靠谱客的博主结实灯泡，最近开发中收集的这篇文章主要介绍杭电数据结构课程实践-哈密顿图的判断，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

哈密顿图的判断

- - 需求分析
  - 详细设计
  - 程序流程图

需求分析

经过图中的每个顶点一次且仅一次的通路称为哈密顿通路，经过图中每个顶点一次且仅一次的回路称为哈密顿回路，具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。哈密顿图是关于连通图的问题，在邮路问题、旅行问题、售货问题等都有较好的应用价值。
判断哈密顿图的充要条件是图论中尚未解决的难题，但应用图的深度优先搜索策略却能描述一个判断哈密顿图是否存在的算法。借助辅助工作栈，初始所有顶点均设置为未被访问状态false,计数器count=0,且设u为源点，用深度优先搜索策略判断哈密顿图的递归算法大致如下：

从图中某个顶点u出发，该顶点入栈，设置该项点访问状态为true, count++。
依次从与u邻接且未被访问过的邻接点出发，在count小于图中的顶点数且栈不空时重复(1)、(2)，递归地深度优先搜索图，直至当前顶点u的所有邻接点都已被访问。
若此时count小于图中的顶点数，则count–,设置当前顶点u的访问状态为false,退栈，回到步骤(2)。或count等于图中的顶点数但源点不是当前结点u的邻接点，该图至少是半哈密顿图，若要继续做哈密顿图的判断，则同样置当前顶点u的访问状态为false、退栈，回到步骤(2)。执行以上步骤，直至count等于图中的顶点数且源点是当前结点u的邻接点，则该图存在哈密顿回路，是哈密顿图;或栈空，则该图不是哈密顿图。

应用图的深度优先搜索策略判断哈密顿图是否存在的算法是基于邻接点的搜索策略，由于图的邻接表表示法在取顶点的邻接点操作时因表中没有无效的邻接点信息而操作效率比数组表示法高，因此，本算法选用邻接表表示法作为图的存储结构，并在此基础上实现图的抽象数据类型及描述哈密顿图的判断算法。

详细设计

图抽象类型的实现（邻接表）.h

#ifndef _graph_H_
#define _graph_H_
#define MAX_NAME 3 // 顶点字符串的最大长度+1
typedef int InfoType;
typedef char VertexType[ MAX_NAME ];
#define MAX_VERTEX_NUM 20
using namespace std;
//图的种类：{有向图,有向网,无向图,无向网}
enum GraphKind{ DG, DN, UDG, UDN };
//表结点结构
struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
ArcNode *nextarc; // 指向下一条弧的指针
InfoType *info; // 网的权值指针
};
//头结点结构
typedef struct {
VertexType data; // 顶点信息
ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针
}VNode, AdjList[ MAX_VERTEX_NUM ];
//图的邻接表存储结构
struct ALGraph {
AdjList vertices;
// 顶点数组
int vexnum,arcnum; // 图的当前顶点数和弧数
int kind; // 图的种类标志
};
//以下为基于邻接表的图的基本操作的实现
//查找顶点在顶点数组中的位置
int LocateVex( ALGraph G, VertexType u )
{
int i;
for ( i = 0; i < G.vexnum; i++ )
if ( strcmp( u, G.vertices[ i ].data ) == 0 )
return i;
return -1;
}
//采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)
bool CreateGraph( ALGraph &G )
{
int i, j, k;
int w; // 权值
VertexType va, vb;
ArcNode *p;
cout << "(请输入图的类型(0:有向图,1:有向网,2:无向图,3:无向网):";
cin >> G.kind;
cout << "请输入图的顶点数目,边或弧的数目: ";
cin >> G.vexnum >> G.arcnum;
cout << "请输入" << G.vexnum << "个顶点的值(小于" << MAX_NAME << "个字符):" << endl;
for ( i = 0; i < G.vexnum; i++ )
{
// 构造顶点向量
cin >> G.vertices[ i ].data;
G.vertices[ i ].firstarc = NULL;
}
if ( G.kind == 1 || G.kind == 3) // 网
cout << "请顺序输入每条弧(边)的权值、弧尾和弧头:" << endl;
else // 图
cout << "请顺序输入每条弧(边)的弧尾和弧头:" << endl;
for ( k = 0; k < G.arcnum; k++ )
{
// 构造表结点链表
if ( G.kind == 1 || G.kind == 3 ) // 网
cin >> w >> va >> vb;
else // 图
cin >> va >> vb;
i = LocateVex( G, va ); // 弧尾
j = LocateVex( G, vb ); // 弧头
p = new ArcNode;
p->adjvex = j;
if ( G.kind == 1 || G.kind == 3 )
{
// 网
p->info = new int;
*( p->info ) = w;
}
else
p->info = NULL; // 图
p->nextarc = G.vertices[ i ].firstarc; // 插在表头
G.vertices[ i ].firstarc = p;
if ( G.kind >= 2 )
{
// 无向图或网,产生第二个表结点
p = new ArcNode;
p->adjvex = i;
if ( G.kind == 3 )
{
// 无向网
p->info = new int;
*( p->info ) = w;
}
else
p->info = NULL; // 无向图
p->nextarc = G.vertices[ j ].firstarc; // 插在表头
G.vertices[ j ].firstarc = p;
}
}
return true;
}
// 初始条件: 图G存在。操作结果: 销毁图G
void DestroyGraph( ALGraph &G )
{
int i;
ArcNode *p, *q;
for ( i = 0; i < G.vexnum; i++ )
{
p = G.vertices[ i ].firstarc;
while ( p )
{
q = p->nextarc;
if ( G.kind % 2 ) // 网
delete p->info;
delete p;
p = q;
}
}
G.vexnum = 0;
G.arcnum = 0;
}
//初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值
VertexType& GetVex( ALGraph G, int v )
{
if ( v >= G.vexnum || v < 0 )
exit( false );
return G.vertices[ v ].data;
}
//初始条件: 图G存在,v是G中某个顶点,操作结果: 对v赋新值value
bool PutVex( ALGraph &G, VertexType v, VertexType value )
{
int i;
i = LocateVex( G,v );
if ( i > - 1 )
{
// v是G的顶点
strcpy( G.vertices[ i ].data, value );
return true;
}
return false;
}
// 初始条件: 图G存在,v是G中某个顶点
// 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int FirstAdjVex( ALGraph G, int v )
{
ArcNode *p;
p = G.vertices[ v ].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
// 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点
// 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。
//
若w是v的最后一个邻接点,则返回-1
int NextAdjVex( ALGraph G, int v, int w )
{
ArcNode *p;
p = G.vertices[ v ].firstarc;
while ( p && p->adjvex != w ) // 指针p不空且所指表结点不是w
p = p->nextarc;
if ( ! p || ! p->nextarc ) // 没找到w或w是最后一个邻接点
return -1;
else // p->adjvex==w
return p->nextarc->adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号
}
// 初始条件: 图G存在,v和图中顶点有相同特征
// 操作结果: 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)
void InsertVex( ALGraph &G, VertexType v )
{
strcpy( G.vertices[ G.vexnum ].data, v ); // 构造新顶点向量
G.vertices[ G.vexnum ].firstarc = NULL;
G.vexnum++; // 图G的顶点数加1
}
// 初始条件: 图G存在,v是G中某个顶点
// 操作结果: 删除G中顶点v及其相关的弧
bool DeleteVex( ALGraph &G, VertexType v )
{
int i, j;
ArcNode *p, *q;
j = LocateVex( G, v ); // j是顶点v的序号
if ( j < 0 ) // v不是图G的顶点
return false;
p = G.vertices[ j ].firstarc; // 删除以v为出度的弧或边
while ( p )
{
q = p;
p = p->nextarc;
if ( G.kind % 2 ) // 网
delete q->info;
delete q;
G.arcnum --; // 弧或边数减1
}
G.vexnum--; // 顶点数减1
for ( i = j; i < G.vexnum; i++ ) // 顶点v后面的顶点前移
G.vertices[ i ] = G.vertices[ i + 1 ];
for ( i = 0; i < G.vexnum; i++ )
{
// 删除以v为入度的弧或边且必要时修改表结点的顶点位置值
p = G.vertices[ i ].firstarc; // 指向第1条弧或边
while ( p )
{
// 有弧
if ( p->adjvex == j )
{
if ( p == G.vertices[ i ].firstarc )
{
// 待删结点是第1个结点
G.vertices[ i ].firstarc = p->nextarc;
if ( G.kind % 2 ) // 网
delete p->info;
delete p;
p = G.vertices[ i ].firstarc;
if ( G.kind < 2 ) // 有向
G.arcnum--; // 弧或边数减1
}
else
{
q->nextarc = p->nextarc;
if ( G.kind % 2 ) // 网
delete p->info;
delete p;
p = q->nextarc;
if ( G.kind < 2 ) // 有向
G.arcnum --; // 弧或边数减1
}
}
else
{
if ( p->adjvex > j )
p->adjvex--; // 修改表结点的顶点位置值(序号)
q = p;
p = p->nextarc;
}
}
}
return true;
}
//初始条件: 图G存在,v和w是G中两个顶点
// 操作结果: 在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>
bool InsertArc( ALGraph &G, VertexType v, VertexType w )
{
ArcNode *p;
int w1, i, j;
i = LocateVex( G, v ); // 弧尾或边的序号
j = LocateVex( G, w ); // 弧头或边的序号
if ( i < 0 || j < 0 )
return false;
G.arcnum++; // 图G的弧或边的数目加1
if ( G.kind % 2 )
{
// 网
cout << "请输入弧(边)<<v<<","<<w<<的权值: ";
cin >> w1;
}
p = new ArcNode;
p->adjvex = j;
if( G.kind % 2 )
{
// 网
p->info = new int;
*( p->info ) = w1;
}
else
p->info = NULL;
p->nextarc = G.vertices[ i ].firstarc; // 插在表头
G.vertices [i ].firstarc = p;
if ( G.kind >= 2 )
{
// 无向,生成另一个表结点
p = new ArcNode;
p->adjvex = i;
if ( G.kind == 3 )
{
// 无向网
p->info = new int;
*( p->info ) = w1;
}
else
p->info = NULL;
p->nextarc = G.vertices [ j ].firstarc; // 插在表头
G.vertices[ j ].firstarc = p;
}
return true;
}
// 初始条件: 图G存在,v和w是G中两个顶点
// 操作结果: 在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>
bool DeleteArc( ALGraph &G, VertexType v, VertexType w )
{
ArcNode *p, *q;
int i, j;
i = LocateVex( G, v ); // i是顶点v(弧尾)的序号
j = LocateVex( G, w ); // j是顶点w(弧头)的序号
if ( i < 0 || j < 0 || i == j )
return false;
p = G.vertices[ i ].firstarc; // p指向顶点v的第一条出弧
while ( p && p->adjvex != j )
{
// p不空且所指之弧不是待删除弧<v,w>，则p指向下一条弧
q = p;
p = p->nextarc;
}
if ( p && p->adjvex == j )
{
// 找到弧<v,w>
if ( p == G.vertices[ i ].firstarc ) // p所指是第1条弧
G.vertices[ i ].firstarc = p->nextarc; // 指向下一条弧
else
q->nextarc = p->nextarc; // 指向下一条弧
if ( G.kind % 2 ) // 网
delete p->info;
delete p; // 释放此结点
G.arcnum --; // 弧或边数减1
}
if ( G.kind >= 2 )
{
// 无向,删除对称弧<w,v>
p = G.vertices[ j ].firstarc; // p指向顶点w的第一条出弧
while ( p && p->adjvex != i )
{
// p不空且所指之弧不是待删除弧<w,v>，则 p指向下一条弧
q = p;
p = p->nextarc;
}
if ( p && p->adjvex == i )
{
// 找到弧<w,v>
if ( p == G.vertices[ j ].firstarc ) // p所指是第1条弧
G.vertices[ j ].firstarc = p->nextarc; // 指向下一条弧
else
q->nextarc = p->nextarc; // 指向下一条弧
if ( G.kind == 3 ) // 无向网
delete p->info;
delete p; // 释放此结点
}
}
return true;
}
bool visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
void( *VisitFunc )( char* v ); // 函数变量(全局量)
// 从第v个顶点出发递归地深度优先遍历图G
void DFS( ALGraph G, int v )
{
int w;
visited[ v ] = true; // 设置访问标志为TRUE(已访问)
VisitFunc( G.vertices[ v ].data ); // 访问第v个顶点
for ( w = FirstAdjVex( G, v ); w >= 0; w = NextAdjVex( G, v, w ) )
if ( ! visited[ w ] )
DFS( G, w ); // 对v的尚未访问的邻接点w递归调用DFS
}
// 对图G作深度优先遍历。
void DFSTraverse( ALGraph G, void( *Visit )( char* ) )
{
int v;
VisitFunc = Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数
for ( v = 0; v < G.vexnum; v++ )
visited[ v ] = false; // 访问标志数组初始化
cout << "深度优先遍历的结果是:" << endl;
for ( v = 0; v < G.vexnum; v++ )
if ( ! visited[ v ] )
DFS( G, v ); // 对尚未访问的顶点调用DFS
cout << endl;
}
typedef int QElemType; // 队列类型
#include"LinkQueue.h"
//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited
void BFSTraverse( ALGraph G, void( *Visit )( char* ) )
{
int v, u, w;
VertexType u1, w1;
LinkQueue Q;
for ( v = 0; v < G.vexnum; v++ )
visited[ v ] = false; // 置初值
InitQueue( Q ); // 置空的辅助队列Q
cout << "广度优先遍历的结果是:" << endl;
for ( v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图
if ( ! visited[ v ] )
{ // v尚未访问
visited[ v ] = true;
Visit( G.vertices[ v ].data );
EnQueue( Q, v ); // v入队列
while ( ! QueueEmpty( Q ) )
{
// 队列不空
DeQueue( Q, v ); // 队头元素出队并置为u
for ( w = FirstAdjVex( G, v ); w >= 0; w = NextAdjVex( G, v, w ) )
if ( ! visited[ w ] )
{ // w为u的尚未访问的邻接顶点
visited[ w ] = true;
Visit( G.vertices[ w ].data );
EnQueue( Q, w ); // w入队
}
}
}
cout << endl;
}
// 输出图的邻接矩阵G
void Display( ALGraph G )
{ // 输出图的邻接矩阵G
int i;
ArcNode *p;
switch ( G.kind )
{
case DG:
cout << endl << "该图为有向图,";
break;
case DN:
cout << endl << "该图为有向网,";
break;
case UDG:
cout << endl << "该图为无向图,";
break;
case UDN:
cout << endl << "该图为无向网,";
}
cout << "其中有" << G.vexnum << "个顶点,各顶点值分别为:" << endl;
for ( i = 0; i < G.vexnum; i++ )
cout << G.vertices[ i ].data << " ";
cout << endl << "该图有" << G.arcnum << "条弧(边),所建邻接表为:" << endl;
for ( i = 0; i < G.vexnum; i++ )
{
p = G.vertices[ i ].firstarc;
while ( p )
{
if ( G.kind <= 1 )
{
// 有向
cout << G.vertices[ i ].data << "->" << G.vertices[ p->adjvex ].data;
if ( G.kind == DN ) // 网
cout << ":" << *( p->info ) << " ";
}
else
{
// 无向(避免输出两次)
cout << G.vertices[ i ].data << "--" << G.vertices[ p->adjvex ].data << "
";
if ( G.kind == UDN ) // 网
cout << ":" << *( p->info ) << " ";
}
p = p->nextarc;
}
cout << endl;
}
}
#endif

LinkQueue.h

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
//链队列结点结构
struct LinkNode {
QElemType data;
LinkNode *next;
};
//带头结点的链队列结构 
struct LinkQueue {
LinkNode
*front;
//队头指针
LinkNode
*rear;
//队尾指针
};
//构造一个空的链队列。
void InitQueue( LinkQueue &Q )
{
Q.front = Q.rear = new LinkNode ;
Q.front->next = NULL;
}//LinkQueue
//将链队列清空。
void ClearQueue( LinkQueue &Q )
{
LinkNode *p;
while ( Q.front->next != NULL )
{
p = Q.front->next;
Q.front->next = p->next;
delete p;
}
Q.rear = Q.front;
}
//链队列结构销毁。
void DestroyQueue( LinkQueue &Q )
{
ClearQueue( Q );
//成员函数Clear()的功能是释放链表中的所有元素结点
delete Q.front;
Q.front = Q.rear = NULL;
}
//判链队列是否为空，若为空，则返回true，否则返回false。
bool QueueEmpty( LinkQueue Q )
{
return Q.front == Q.rear;
}
//返回链队列中元素个数。
int QueueLength( LinkQueue Q )
{
int i = 0;
LinkNode *p = Q.front->next;
while ( p != NULL )
{
i++;
p = p->next;
}
return i;
}
//取链队列队头元素的值。先决条件是队列不空。
QElemType GetHead( LinkQueue &Q )
{
return Q.front->next->data;
}
//取链队列队尾元素的值。先决条件是队列不空。
QElemType GetLast( LinkQueue &Q )
{
return Q.rear->data;
}
//链队列入队，插入e到队尾。
void EnQueue( LinkQueue &Q, QElemType e )
{
LinkNode *p;
p = new LinkNode ;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
}
//链队列出队。先决条件是队列不空。
bool DeQueue( LinkQueue &Q,QElemType &e )
{
if ( QueueEmpty( Q ) )
return false;
LinkNode *p = Q.front->next;
Q.front->next = p->next;
e = p->data;
if ( p == Q.rear )
Q.rear = Q.front;
//若出队后队列为空，需修改Q.rear。
delete p;
return true;
}
#endif

SqStack.h

#ifndef _SqStack_
#define _SqStack_
//顺序栈结构
struct SqStack {
SElemType *base;
//基地址指针
int top;
//栈顶指针
int size;
//向量空间大小
};
//栈的初始化，分配m个结点的顺序空间，构造一个空的顺序栈
void InitSqStack( SqStack &s, int m )
{
s.top = 0;
s.base = new SElemType[ m ];
s.size = m;
}
//栈销毁
void DestroySqStack( SqStack &s )
{
delete[] s.base;
s.top = 0;
s.size = 0;
}
//置空栈
void ClearSqStack( SqStack &s )
{
s.top = 0;
}
//判别栈是否为空 
bool SqStackEmpty( SqStack s )
{
return s.top == 0;
}
//求栈中元素个数
int SqStackLength( SqStack s )
{
return s.top;
}
//取栈顶元素的值。先决条件是栈不空。
bool GetTop( SqStack s, SElemType &e )
{
if ( ! SqStackEmpty( s ) )
{
e = s.base[ s.top - 1 ];
return true;
}
else
return false;
}
//入栈，若栈满，则先扩展空间。插入e到栈顶
void PushSqStack( SqStack &s, SElemType e )
{
if ( s.top >= s.size )
{
//若栈满，则扩展空间。 
SElemType *newbase;
newbase = new SElemType[ s.size + 10 ];
for ( int j = 0; j < s.top; j++ )
newbase[ j ] = s.base[ j ];
delete[] s.base;
s.base = newbase;
s.size += 10;
}
s.base[ s.top++ ] = e;
}
//出栈,先决条件是栈非空。
bool PopSqStack( SqStack &s, SElemType &e )
{
if ( SqStackEmpty( s ) )
return false;
e = s.base[ --s.top ];
return true;
}
#endif

哈密顿路径的搜索.cpp

#include <iostream>
#include <iomanip>
#include <string.h>
#include <cstdlib>
#include "图抽象类型的实现（邻接表）.h"
using namespace std;
//访问函数实体 
void print( char *i )
{
cout << setw( 3 ) << i;
}
typedef int SElemType; // 栈类型
#include"SqStack.h" 
// 从第v个顶点出发,深度优先方式（递归）搜索哈密顿路径
void HMDDFS( ALGraph G, int v, int &u, int &count, SqStack &S1, SqStack &S2, bool &tag1, bool &tag2 )
{
visited[ v ] = true; // 设置访问标志为TRUE(已访问)
PushSqStack( S1, v );
if ( ! tag2 ) PushSqStack( S2, v );
count++;
ArcNode *p;
if ( count < G.vexnum )
{
for ( p = G.vertices[ v ].firstarc; p && ! tag1; p = p->nextarc )
if ( ! visited[ p->adjvex ] )// 对v的尚未访问的邻接点w递归调用HMDDFS
HMDDFS( G, p->adjvex, u, count, S1, S2,tag1, tag2 );
if ( ! tag1 )
{
count--;
PopSqStack( S1, v ); //回溯 
if ( ! tag2 )
PopSqStack( S2, v );
visited[ v ] = false;
}
}
else
{
tag2 = true; //找到哈密顿通路 
for ( p = G.vertices[ v ].firstarc; p; p = p->nextarc )
if ( p->adjvex == u )
{
tag1 = true;//找到哈密顿回路 
PushSqStack( S1, u );
}
if( ! tag1 )
{
count--;
PopSqStack( S1, v );//回溯 
visited[ v ] = false;
}
}
}
// 对哈密顿图的判断
void HMDSearch( ALGraph G, void( *Visit )( char* ) )
{
SqStack S1, S2, T;
InitSqStack( S1, G.vexnum + 1 );//若图G为哈密顿图，栈s1 存放哈密顿回路 
InitSqStack( S2, G.vexnum + 1 );//若图G为半哈密顿图，栈s2 存放哈密顿通路
InitSqStack( T, G.vexnum + 1 );//T为辅助栈，用以输出 哈密顿回路或哈密顿通路 
int v;
for ( v = 0; v < G.vexnum; v++ )
visited[ v ] = false; // 访问标志数组初始化; 
v = 0;
int count = 0;
//若tag1为true，则图G是哈密顿图，若tag2为true则图G是半哈密顿图
bool tag1 = false, tag2 = false;
// 具有哈密顿回路的图为哈密顿图，因此，v既是源点，也是终点 
HMDDFS( G, v, v, count, S1, S2, tag1, tag2 );
if( tag1 )
{
cout << endl << "该图为哈密顿图，一条哈密顿回路为:" << endl;
while ( ! SqStackEmpty( S1 ) )
{
PopSqStack( S1, v );
PushSqStack( T, v );
}
while ( ! SqStackEmpty( T ) )
{
PopSqStack( T, v );
Visit( G.vertices[ v ].data );
}
}
else
{ //在图G非哈密顿图的情况下，依次从每一顶点出发探测哈密顿通路

for ( v = 1; ! tag2 && v < G.vexnum; v++)
HMDDFS(G, v, v, count, S1, S2, tag1, tag2);
if ( tag2 )
{
cout << endl << "该图为半哈密顿图，一条哈密顿通路为:" << endl;
while ( ! SqStackEmpty( S2 ) )
{
PopSqStack( S2, v );
PushSqStack( T, v );
}
while ( ! SqStackEmpty( T ) )
{
PopSqStack( T, v );
Visit( G.vertices[ v ].data );
}
}
else
cout << endl << "该图不是哈密顿图。" << endl;
}
cout << endl;
}
int main()
{
ALGraph g;
CreateGraph( g );
Display( g );
HMDSearch( g, print );
cout << endl;
return 0;
}