一、图的结构
二、程序实现
/*
项目名称：深度优先搜索算法
编译环境：VC++ 2008
作者相关：。。。
最后修改：2019.10.31
学习目标：1.掌握邻接矩阵的深度优先搜索算法
注意事项：1.测试所有功能是否正常
遇到问题：
1.深度优先算法的理解
(1)从顶点A开始遍历,找到A的邻接点B
(2)找B的邻接点，先找到A,发现A已遍历过，那么找B相对于A的下一个邻接点
(3)直到找到E，找E的邻接点时，发现E的邻接点都遍历过,这是w回到H
(4)然后H的邻接点也都遍历过,继续向上，直到A，发现C还没有遍历...
*/
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#define INFINITY -1//最大值
#define MAX_VERTEX_NUM 20//最大顶点个数
#define MAX_StrLength 20//最大串长
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}
typedef char VertexType;//自定义
typedef bool Status;
typedef int VRType;//顶点间关系类型(表示邻接否或权值)
typedef char InfoType;//弧段的信息类型
typedef struct ArcCell//该结点字面意思是?
{
VRType adj;//1.顶点关系类型。2.对无权图,-1或1表示是否相邻。3.对带权图为权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//图当前的顶点数和弧(边)数
GraphKind kind;//图的种类标志
}MGraph;
int LocateVex(MGraph &G,VertexType v);
int FirstAdjVex(MGraph G,VertexType v);
int NextAdjVex(MGraph G,VertexType v,VertexType u);
Status CreateUDN(MGraph &G);
Status Visit(MGraph G,int v);
bool visited[MAX_VERTEX_NUM];//定义全局变量
Status (*VisitFunc)(MGraph G,int v);//VisitFunc是指向函数的指针
void DFS(MGraph G,int v);//从第v个顶点遍历图
void DFSTraverse(MGraph G,Status (*Visit)(MGraph,int));//深度优先遍历
int main()
{
MGraph G;
CreateUDN(G);
printf("\n");
DFSTraverse(G,Visit);
return 0;
}
//确定v在G中的位置
int LocateVex(MGraph &G,VertexType v)
{
int i=0;
while(i<G.vexnum)
{
if(G.vexs[i]==v)
return i;
else
++i;
}
return -1;//没有返回-1
}
//图G存在,k是某个顶点的序号,返回该顶点的值
VertexType GetVex(MGraph G,int k)
{
if(k>G.vexnum||k<0)
return ERROR;
return G.vexs[k];
}
//图G存在,v是G中某个顶点,返回v的第一个邻接顶点,没有则返回空
int FirstAdjVex(MGraph G,VertexType v)
{
int i;
int index=LocateVex(G,v);
for(i=0;i<G.vexnum;i++)
{
if(G.arcs[index][i].adj!=-1)
break;
}
if(i==G.vexnum)
return -1;
else
return i;
}
//返回G中顶点v相对于w的下一邻接点
int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
int iv=LocateVex(G,v);
int iw=LocateVex(G,w);
int i;
for(i=iw+1;i<G.vexnum;i++)
if(G.arcs[iv][i].adj!=-1)
break;
if(i==G.vexnum)
return -1;
else
return i;
}
//构造无向网
Status CreateUDN(MGraph &G)
{
int IncInfo,i,j,k,w;//IncInfo为0表示弧(边)不含信息,当作标志位
VertexType v1,v2;//项点
printf("请输入无向网的顶点数和边数及弧是否含信息:\n");
scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
for(i=0;i<G.vexnum;++i)//构造顶点向量
{
printf("请输入第%d个顶点\n",i+1);
getchar();
scanf("%c",&G.vexs[i]);//输入顶点
}
for(i=0;i<G.vexnum;++i)//邻接矩阵的初始化
for(j=0;j<G.vexnum;++j)
//G.arcs[i][j]={INFINITY,NULL};///结构体数组成员初始化
{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
for(k=0;k<G.arcnum;++k)
{
printf("请输入第%d条边依附的项点和权值\n",k+1);
fflush(stdin);//清空标准输入流缓冲区中的内容
scanf("%c,%c,%d",&v1,&v2,&w);//这里避免读入空格
i=LocateVex(G,v1);//确定i在G中的下标位置
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;//弧(v1,v2)的权值
if(IncInfo)
{
printf("请输入该弧对应的相关信息:\n");
fflush(stdin);
G.arcs[i][j].info=(InfoType *)malloc(MAX_StrLength*sizeof(InfoType));
scanf("%s",G.arcs[i][j].info);
}
G.arcs[j][i]=G.arcs[i][j];
}
return OK;
}
Status Visit(MGraph G,int v)
{
printf("%c ",G.vexs[v]);
return OK;
}
void DFSTraverse(MGraph G,Status (*Visit)(MGraph,int))//深度优先遍历
{
int v;
VisitFunc=Visit;//通过VisitFunc可以调用传进来的函数
for(v=0;v<G.vexnum;++v)//访问标志数组初始化
visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)//这里是检验
if(!visited[v])//若v等于0就能完成对所有的遍历
DFS(G,v);//对尚未访问的顶点调用DFS
}
void DFS(MGraph G,int v)//从第v个顶点遍历图
{
VertexType V;
int w;
VisitFunc(G,v);
visited[v]=TRUE;
V=G.vexs[v];
for(w=FirstAdjVex(G,V);w>=0;w=NextAdjVex(G,V,G.vexs[w]))
if(!visited[w])
DFS(G,w);
}
三、输出结果
