-
一、实验目的
1
．掌
握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构；
< br>2
．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍
历算法，
复习栈和队列的应用；
3<
/p>
．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。
二、实验内容
实验内容
1
**
图的遍历
[
问题描述
]
许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍
历全部顶点。
[
基本要求
]
建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的
顶点为起点，分别输出每种遍历下的顶点访问序列。
[
实现提示
]
设图的顶点不超过
30
个，每个顶点用一个编号表示（如果一
个图有
N
个顶点，则它们的编
号分别为
1
，
2
，…，
N
）
。通过输入图的全部边输入一个图
，每条边是两个顶点编号对，可以对
边依附顶点编号的输入顺序作出限制（例如从小到大
）
。
[
编程思路
]
首先图的创建，
采用邻
接表建立，
逆向插入到单链表中，
特别注意无向是对称插入结点
，
且要把输入的字符在顶点数组中定位（
LocateVex(Graph
G,char
*name)
，以便后来的遍历操作，
深度遍历算法采用递归调用，
其中最主要的是
< br>NextAdjVex(Graph
G,
int
v,
int
w)
；
Fi
rstAdjVex
（）函数的书写，依次递归下去，广度遍历用队列的辅助。
[
程序代码
]
头文件：
#include
#include
#define
MAX_VERTEX_NUM 30
#define
MAX_QUEUE_NUMBER 30
#define OK
1
#define ERROR
0
#define INFEASIBLE
-1
#define OVERFLOW
-2
#define TRUE
1
#define FALSE
0
typedef int Status;
typedef
int InfoType;
typedef int Status;
/*
定义弧的结构
*/
typedef
struct ArcNode{
int
adjvex;
/*
该边所指向的顶点的位置
*/
struct ArcNode
*nextarc;
/*
指向下一条边的指针
*/
InfoType info;
/*
该弧相关信息的指针
*/
}ArcNode;
/*
定义顶点的结构
*/
typedef struct VNode{
char data[40];
/*
顶点信息
*/
ArcNode
*firstarc;
/*<
/p>
指向第一条依附该顶点的弧的指针
*/
}VNode,AdjList[MAX_VERTEX_NUM];
/*
定义图的结构
*/
typedef struct {
AdjList
vertices;
int vexnum,arcnum;
/*
图的当前顶点数和弧数
*/
int
kind;
/*
图的类型标志
*/
}Graph;
/*
定义队列的结构
*/
typedef struct{
int *elem;
int front, rear;
}Queue;
/*
功能选择
*/
void MenuSelect(int w);
/*
顶点定位
*/
int LocateVex(Graph G
,char
*name);
/*
创建无向图
*/
void CreateGraph(Graph &G);
/*
求第一个顶点
*/
int FirstAdjVex(Graph G
, int
v);
/*
求下一个顶点
*/
int NextAdjVex(Graph G
, int
v, int w);
/*
深度递归
*/
void DFS(Graph G
, int v)
/*
深度遍历
*/
void DFSTravel(Graph G
,int
v);
/*
广度遍历
*/
void
BFSTraverse(Graph G
,char
*name);
/*
初始化队列
*/
Status
InitQueue(Queue &Q);
/*
判空
*/
Status
EmptyQueue(Queue Q);
/*
进队
*/
Status
EnQueue(Queue &Q, int e);
/*
出队
*/
Status
DeQueue(Queue &Q, int &e);
实现文件
：
#include
#include
#include
#include
#include
bool visited[MAX_VERTEX_NUM];
/**************************
*********************************
*
顶点定位
*
**
**************************************************
*******/
int
LocateVex(Graph G
,char *name)
{
} <
/p>
/***************************************
********************
*
创建无向图
*
int i;
for(i=1;i<=G
.vexnum;i++)
//
从
1
号位置开
始存储
if(strcmp(name,G
.vertices[i].data)==0)
//
相等则找到，返回位序
return i;
return
-1;
***********************************
************************/
void
CreateGraph(Graph &G)
{
ArcNode *p;
char
name1[10],name2[10];
int i,j,k;
printf(
请输入
顶点数
,
按回车键结束：
scanf(
.vexnum);
printf(
请输入弧数
,
按回车键结束：
scanf(
.arcnum);
printf(
请依次输入顶点名（用空格分开且字符小于
10
）
,
按回车键结束：
n
printf(
printf(
pri
ntf(
………………………………………输入小提示………………………………………
n
printf(
< br>为避免输入遗漏，最好从选择任意一点，输入所有相邻边
n
printf(
< br>输入边时格式
(
用空格分开，即格式为顶点（空格）顶点
（空格
)
）
n
pri
ntf(
………………………………………输入小提示………………………………………
nnnn
{
pri
ntf(
请输入相邻的两个顶点
,
按回
车键结束：
scanf(
i=Loca
teVex(G
,name1);
//
返回位序
for(k=0;k
.arcnum;k++)
for(i=1;i<=G
.vexnum;i++)
//<
/p>
从
1
号位置开始存储
{
}
scanf(
.vertices[i].data);
//
从一号位置开始初始化
G
.vertices[i].firstarc=NULL;
j=LocateVex(G
,name2);
p=(ArcNode *)malloc(sizeof(ArcNode));
//
申请边节点
p->adjvex=j;
//<
/p>
插入到邻接表中，注意此处为逆向插入到单链表中
p->
nextarc=G
.vertices[i].firstarc;
G
.vertices[i].firstarc=p;
//
无向图，注意是对称插入结点
p=(ArcNode *)malloc(sizeof(ArcNode));
}
<
/p>
/***************************************
********************
*
求第一个顶点
* <
/p>
****************************************
*******************/
int
FirstAdjVex(Graph G
, int v)
{
ArcNode *p;
if(v>=1 && v<=G
.vexnum)
{
p=G
.vertices[v].firstarc;
if(p->nextarc==NULL)
return 0;
else
return
(p->nextarc->adjvex);
//
返回第一个顶点字符
}
return -1;
}
/*************************
**********************************
*
求下一个顶点
*
}
p->adjvex=i;
p->nextarc=G
.vertices[j].first
arc;
G
.vertices[j].firstarc=p;
*****************************************
******************/
int
NextAdjVex(Graph G
, int v, int w)
{
//
在图
G
中寻找第
v
个顶点的相对于
w
的下一个邻接顶点
ArcNode *p;
if(v>=1 && v<=G
.vexnum &&
w>=1 && w<=G
.vexnum)
{
p=G
.vertices[v].firstarc;
while(p->adjvex!=w)
p=p->nextarc;
//<
/p>
在顶点
v
的弧链中找到顶点
w
if(p->nextarc!=NULL)
return 0;
//
若已是最后一个顶点，返回
0
else
return(p->nextarc->adjvex);
//
返回下一个邻接顶点的序号
}
return -1;
}
/***
**************************************************
******
*
深度递归
* <
/p>
****************************************
*******************/
void DFS(Graph
G
, int v)
{
int w;
ArcNode *p;
visited[v]=1;
printf(
.vertices[v].data);
//<
/p>
访问第
v
个顶点
p=G
.vertices[v].firstarc;
//p
为依附顶点的第一条边
while (p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(G
,w);
p=p->nextarc;
//
下移指针
-
-
-
-
-
-
-
-
-
上一篇：ANSYS_常用菜单中英对照(超详细)概论
下一篇：这些数学符号用英文怎么读