数据结构实验六,七,八
- 格式：doc
- 大小：162.00 KB
- 文档页数：19
1
实验六 图的遍历
一、实验目的
1、熟悉图的各种存储结构及其构造算法
2、熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。
3、应用图的遍历算法求解各种简单路径问题。
4、理解教科书中讨论的各种图的算法。
二、实验预备知识
本实验的重点：深度优先搜索和广度优先搜索。
图的遍历：和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
图的深度优先遍历：假设给定初始状态图G中的所有顶点均未曾访问过。在G中任选一顶点v出发，首先访问出发点v，并将其标记为已访问过，然后依次从v出发搜索v的每个邻接点。若该邻结点未曾访问过，则以该邻结点为新的出发点继续进行深度优先遍历，直至图中所有和点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均被访问为止。
2
v1v2v3v4v5v6v7
（a）无向图 G
v1v2v3v4v5v6v7123456
（b）图G深度优先过程
深度优先遍历序列：v1→v2→v4→v5→v3→v6→v7
图的广度优先遍历：设初始状态图G中的所有顶点均未访问过。在G中任选一顶点v，首先访问出发点v，接着依次访问v的所有邻接点，然后再依次访问与邻接的所有未曾访问过的顶点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。依此类推，直至图中所有和点v有路径相通的顶点都已访问到。若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。
3
v1v2v3v4v5v6v7v8v9
（c）无向图G
v1v2v3v4v5v6v7v8v912345678
（d）图G广度优先搜索过程
广度悠闲遍历序列：v1→v2→v3→v4→v5→v6→v7→v8→v9
三、实验要求
1、掌握图的遍历思想以及其特点。
2、选择程序上机进行调试找出问题、保存和打印出程序的运行结果。
3、上机学会运用图的思想解决实际问题。
4、课后尝试自己编写程序并上机运行得出结果。
4
深度遍历图，邻接表加递归
#include
#include
#include
#define MAX 100
typedef struct Linknode
{
int adjvex;
//int info;
struct Linknode *next;
}LinkNode;
typedef struct Vexnode
{
int vexdata;
LinkNode *first;
}VexNode;
typedef struct {
int vexnum;
VexNode adjlist[100];
}ALGraph;
ALGraph G;
int pre[MAX],path[MAX];
void create();
void print();
void DFS(int u,int v,int d);
void main()
{
create();
//print();
DFS(2,2,-1);
}
void create()
{
5
int i,tempi;
LinkNode *p,*q;
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&G.vexnum);
//scanf("%c",&temp);
for(i=0;i
{
scanf("%d",&G.adjlist[i].vexdata);
G.adjlist[i].first=NULL;
//scanf("%c",&temp);
}
for(i=0;i
{
scanf("%d",&tempi);
while(tempi!=100)
{
p=(LinkNode *)malloc(sizeof(LinkNode));
p->adjvex=tempi;
q=G.adjlist[i].first;
G.adjlist[i].first=p;
p->next=q;
scanf("%d",&tempi);
}
}
}
void print()
{
int i;
LinkNode *p;
for(i=0;i
{
printf("%d\t",G.adjlist[i].vexdata);
p=G.adjlist[i].first;
while(p!=NULL)
{
printf("%d\t",p->adjvex);
p=p->next;
}
printf("\n");
}
}
6
void DFS(int u,int v,int d)
{
int i,temp;
LinkNode *p;
pre[u]=1;
d++;
path[d]=u;
p=G.adjlist[u].first;
if(u==v )
{
for(i=0;i<=d;i++)
printf("%d\t",path[i]);
printf("\n");
}
while(p!=NULL)
{
temp=p->adjvex;
if(pre[temp]==0)
{
DFS(temp,v,d);
}
p=p->next;
}
pre[u]=0;
d--;
}
void print_path(int pre[],int v)
{
if(pre[v]!=v)
print_path(pre,pre[v]);
printf("%d ",v);
}
7
实验七 最小生成树
一、实验目的
1、图的邻接矩阵、邻接表和边集数组表示。
2、掌握建立图的邻接矩阵的算法，由邻接矩阵转换为邻接表和边集数组的算法。
3、熟悉最小生成树的构造。
4、熟悉并掌握求图的最小生成树的普里姆算法克鲁斯卡尔算法。
二、实验预备知识
掌握图的概念、图的邻接矩阵表示法和邻接表表示法、图的深度和广度优先遍历、生成树和最小生成树、树的最短路径、拓扑排序。
有向图：若图G中的每条边都是有方向的，则称G为有向图。
无向图：若图G中的每条边都是没有方向的，则称G为无向图。
完全图：有1/2条边的图无向图称为完全图。恰有n(n-1)条边的有向图称为有向完全图，恰有n(n-1)/2条边的无向图称无向完全图。
连通图：图中G中任意两个顶点Vi、Vj∈V、Vi和Vj连通的，则G称为连通图。v1v2v3v4v5
度：顶点V的度是和V相关联的边的数目。
8
强连通图：在有向图G中，如果对于每一对Vi，Vj∈V、Vi、Vj，从Vi到Vj和从Vj到Vi都存在路径，则G是强连通图。v1v2v3
无向图的路径：在无向图G中，若存在一个顶点序列vp,vi1，vi2,…，vim，vq，使得(vp，vi1)，(vi1，vi2)，…，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径。
有向图的路径：在有向图G中，路径也是有向的,它由E(G)中的有向边，，…，组成。
路径长度：路径长度定义为该路径上边的数目。
子图：设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图。
生成树：如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
最小生成树：权最小的生成树称为G的最小生成树。
图中（b）、（c）、（d）都是生成树，权分别是：21、13、9。可以证明（d）为一棵最小生成树。
9
1234541239543 123454953
（a）带权图 （b ）生成树
123452353 123451233
（c）生成树 （d）最小生成树
三、实验要求
1、认真阅读和掌握本实验的内容。
2、从实验本上选择一个程序上机调试。
3、得出正确的程序后，运行程序输入一个图形，保存和打印出程序运行的结果，并进行程序的性能分析。
4、请重新编写一个程序并上机进行调试，得出结果后总结出程序的特点。
最小生成树：prim
#include
#include
#include
#define MAX 100
typedef struct dege
