📄 图的搜索.cpp
字号:
/*图的一些算法*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Max 100/*最多的顶点数*/
#define initsize 20/*栈的初始大小*/
#define increasize 10/*增加的大小*/
#define INFINITY 100000000/*一个计算机充许的最大的数*/
struct ArcNode/*边或弧*/
{
int adjvex;/*该弧所指向的顶点位置*/
ArcNode *nextarc;/*指向下一条弧的指针*/
int info;/*该的相关信息,即带权图中的权值,无权图为'1'或'0'*/
};
struct VNode/*结点*/
{
int Vertex;/*顶点标号*/
ArcNode *firstarc;/*指向第一条依附该顶点的弧的指针*/
}*AdjList;
struct Graph/*图*/
{
int vexnum,arcnum;/*图的当前顶点数和弧数*/
}ALGraph;
struct dsUR/*非递归深度优先中用的栈*/
{
int stacksize;/*栈大小*/
VNode **base;/*栈底*/
VNode **top;/*栈顶*/
}S;
struct quer/*在广度优先搜索中用到的队列*/
{
quer *front;/*头指针*/
quer *rear;/*尾指针*/
VNode *date;/*邻接表各链头地址*/
}Q;
void select();/*功能选择*/
void createGraph(int[][Max]);/*构造一个图*/
void adjacency(int[][Max]);/*邻接表存储一个图*/
void depth_Search_Recursion();/*深度优先递归搜索*/
void depth_Search_URecursion();/*深度优先非递归搜索*/
void depth_Reacursion(bool[],int,VNode*[]); /*深度优先搜索中的递归调用*/
void breadth_Search();/*广度优先搜索*/
void initDsUR();/*初始化栈*/
void increaseDsUR();/*增加栈大小*/
void initquer();/*初始化队列*/
void saveFile(int[][Max]);/*把邻接矩阵保存在文件中*/
void main()
{
AdjList = NULL;/*让邻接表的首地址指空*/
select();/*功能选择*/
}
void select()/*功能选择*/
{
char select;/*记录选择的变量*/
int matrix[Max][Max];/*邻接矩阵*/
AA: system("cls");
printf("\n\t\t图的相关算法实现\n\n"
"\t1. 构造一个图.\n"
"\t2. 深度优先递归搜索.\n"
"\t3. 深度优先非递归搜索.\n"
"\t4. 广度优先搜索.\n"
"\t5. 清屏.\n"
"\t6. 退出程序.\n");
do
{
printf("select : ");
fflush(stdin);/*清空缓存*/
scanf("%c",&select);
fflush(stdin);
if (!AdjList&&select!='1'&&select!='6')
{
printf("\n你还没有构建一个图.\n");
select = '5';
system("pause");
}
switch(select)
{
case '1':
createGraph(matrix);/*构造一个图*/
goto AA;
break;
case '2':
depth_Search_Recursion();/*深度优化递归搜索*/
break;
case '3':
depth_Search_URecursion();/*深度优化非递归搜索*/
break;
case '4':
breadth_Search();/*广度优化搜索*/
break;
case '5':
goto AA;
break;
case '6':
printf("\n\n谢谢测试!!!!!!\n\n");
exit(0);
break;
default:
printf("\n你的选择无效,\n");
system("pause");/*等待输入任意键继续*/
break;
}
}while(1);
}
void createGraph(int matrix[][Max])/*输入一个邻接矩阵*/
{
int i = 0;
int j = 0;
int select;/*选择一个构图方式*/
char fname[30];/*文件名*/
FILE *fp;/*文件指针变量*/
for (i = 0; i<ALGraph.vexnum; i++)/*把邻接矩阵初始为零*/
{
for (j = 0; j<ALGraph.vexnum; j++)
matrix[i][j] = 0;
}
BB: printf("\n1. 从文件调入."
"\n2. 现在输入."
" \nselect : ");
scanf("%d",&select);
fflush(stdin);/*清空缓存*/
if (select==1)/*从文件读取邻接矩阵*/
{
printf("\n默认下有三个文件:004.txt, 005.txt, 008.txt.\n你可以在现在输入矩阵中保存你自定义的图.\n");
AA: printf("\n请输入文件名 : ");
gets(fname);/*输入文件名*/
fflush(stdin);
if (!(fp = fopen(fname,"r")))/*把开文件*/
{
printf("\n这个文件不存在,");
system("pause");
printf("\n\n你想重新打开文件吗?(y/n): ");
if(getchar()=='y')
{
fflush(stdin);
goto AA;
}
else
goto BB;
}
ALGraph.vexnum = (int)(fgetc(fp)-48);/*在文件中获取顶点数*/
for (i = 0; i<ALGraph.vexnum; i++)
{
for (j = 0; j<ALGraph.vexnum; j++)
{
matrix[i][j] = (int)(fgetc(fp)-48);/*在文件中读取邻接矩阵*/
}
}
fclose(fp);/*关闭文件*/
printf("\n文件提取完成,");
system("pause");
}
else if (select==2)/*用户现在输入邻接矩阵*/
{
printf("\n请输入顶点数 : ");
scanf("%d",&ALGraph.vexnum);/*输入图的顶点数*/
fflush(stdin);
printf("\n请输入一个邻接矩阵(以行序为主序): ");
for (i = 0; i<ALGraph.vexnum; i++)/*输入邻接矩阵*/
{
for (j = 0; j<ALGraph.vexnum; j++)
scanf("%d",&matrix[i][j]);
}
fflush(stdin);
printf("\n是否保存(y/n)");
if (getchar()=='y')
saveFile(matrix);/*调用保存到文件中的函数*/
fflush(stdin);
}
else/*选择不是1 或 2时*/
{
printf("\n你选择错误,");
system("pause");
}
printf("\n你输入的邻接矩阵是: \n");
for (i = 0; i < ALGraph.vexnum; i++)/*在屏幕上显示这个邻接矩阵*/
{
printf("\t");
for(j = 0; j < ALGraph.vexnum; j++)
printf("%d ",matrix[i][j]);
printf("\n");
}
adjacency(matrix);/*调用函数把这个图从矩阵转化到邻接表中存储*/
fflush(stdin);
printf("\n图的邻接表构造完成\n");
system("pause");
}
void saveFile(int matrix[][100])/*把邻接矩阵保存在文件中*/
{
char fname[30];/*文件名*/
FILE *fp;/*文件流指针*/
int i,j;
printf("\n请输入文件名 : ");
scanf("%s",fname);
fflush(stdin);
if (!(fp = fopen(fname,"w")))/*打开文件*/
{
printf("\n内存分配失败.");
exit(0);
}
fputc((char)(ALGraph.vexnum+48),fp);/*把顶点数写到文件名*/
for (i = 0; i<ALGraph.vexnum; i++)
{
for (j = 0; j<ALGraph.vexnum; j++)
{
fputc((char)(matrix[i][j]),fp);/*把邻接表写到文件中*/
}
}
fclose(fp);
printf("\n邻接矩阵数据已经保存在文件 %s ",fname);
system("pause");
}
void adjacency(int adjmatrix[][100])/*邻接表存储一个图*/
{
int i;
int j;
bool sign;
VNode *H;/*保存邻接表的头地址*/
ArcNode *p,*q;/*申明两个工作指针*/
free(AdjList);/*把先前存储的图的邻接表释放空间*/
/*在邻接表中为每个顶点创建单链表的头指针*/
if(!(AdjList = (VNode*)malloc(ALGraph.vexnum*sizeof(VNode))))
{
puts("内存分存失败.");
exit(0);
}
H = AdjList;
for (i = 0; i<ALGraph.vexnum; i++)/*建邻接表*/
{
sign = false;
AdjList->Vertex = i;
AdjList->firstarc = NULL;
for(j = 0; j<ALGraph.vexnum; j++)
{
if (adjmatrix[i][j]!=0)
{
if (sign)
{
if (!(p = (ArcNode*)malloc(sizeof(ArcNode))))
{
puts("内存分存失败.");
exit(0);
}
p->adjvex = j;
p->info = adjmatrix[i][j];
q->nextarc = p;
q = q->nextarc;
q->nextarc = NULL;
}
if(!sign)
{
AdjList->firstarc = (ArcNode*)malloc(sizeof(ArcNode));
q = AdjList->firstarc;
if (!q)
{
puts("内存分存失败.");
exit(0);
}
AdjList->firstarc->adjvex = j;
AdjList->firstarc->info = adjmatrix[i][j];
sign = true;
AdjList->firstarc->nextarc = NULL;
}
}
}
AdjList++;
}
AdjList = H;
}
void depth_Search_Recursion()/*深度优先递归搜索*/
{
bool visited[Max];/*标记是否已经访问过*/
int v = 0;
VNode *p[Max];/*存储邻接表的各个单链表的首地址*/
VNode *H = AdjList;/*保存邻接表的首地址*/
printf("\n深度优化搜索的结点顺序 : ");
while (v<ALGraph.vexnum)
p[v++] = AdjList++;/*把邻接表中各个单链表的首地址保存到p[]数组中*/
v = 0;
while (v < ALGraph.vexnum)visited[v++] = false;/*初始化访问标志*/
for (v = 0; v < ALGraph.vexnum; v++)
{
if(!visited[v])
depth_Reacursion(visited,v,p);/*对没有被访问的调用递归函数访问*/
}
AdjList = H;
printf("\n深度优先递归搜索完成,");
system("pause");
}
void depth_Reacursion(bool visited[],int v,VNode *p[])/*深度优先中的递归调用*/
{
ArcNode *w;
visited[v] = true;
if (v!=0)printf("->");
printf("v%d",p[v]->Vertex+1);
for (w = p[v]->firstarc; w!=NULL; w = w->nextarc)
{
v = w->adjvex;
if(!visited[v])
depth_Reacursion(visited,v,p);
}
}
void depth_Search_URecursion()/*深度优先非递归搜索*/
{
bool visited[Max];/*访问标志*/
int v = 0;
int k = 0;
VNode *p[Max];
VNode *H = AdjList;
ArcNode *q;
bool sign;
bool sign1;
while (v<ALGraph.vexnum)/*把邻接表中各个单链表的首地址保存到p[]数组中*/
p[v++] = AdjList++;
AdjList = H;
q = p[0]->firstarc;
printf("\n深度优化搜索的结点顺序 : ");
v = 0;
while (v < ALGraph.vexnum)visited[v++] = false;/*初始化访问标志*/
initDsUR();
S.top++;
for (v = 0; v < ALGraph.vexnum; v++)/*访问这个邻接表*/
{
k = v;
if(!visited[k])
{
*S.top = p[k];
if (S.top - S.base==S.stacksize)increaseDsUR();
visited[k] = true;
if(k!=0)printf("->");
printf("v%d",p[k]->Vertex+1);
while(S.top!=S.base)
{
q = (*S.top)->firstarc;
while (q)
{
sign = true;
sign1 = true;
k = q->adjvex;
if (!visited[k])
{
do
{
k = q->adjvex;
if (!visited[k])
{
*(++S.top) = p[k];
if (S.top - S.base==S.stacksize)increaseDsUR();
visited[k] = true;
printf("->v%d",k+1);
q = p[k]->firstarc;
if(!q)
{
S.top--;
sign = false;
}
}
else
{
q = NULL;
sign1 = false;
break;
}
}while(q);
}
if(q)q = q->nextarc;
}
if(sign&&sign1)S.top--;
}
}
}
printf("\n深度优先非递归搜索完成,");
system("pause");
}
void initDsUR()/*初始化栈*/
{
if(!(S.base = S.top = (VNode**)malloc(initsize*sizeof(VNode*))))/*初始化栈空间*/
{
puts("内存分存失败.");
exit(0);
}
S.stacksize = initsize;/*初始化栈大小*/
}
void increaseDsUR()/*增加栈大小*/
{
if (!(S.base = (VNode**)realloc(S.base,(S.stacksize+increasize)*sizeof(VNode*))))/*增加栈空间*/
{
puts("内存分配失败.");
exit(0);
}
S.stacksize+=increasize;/*更新栈大小*/
}
void initquer()/*初始化队列*/
{
Q.rear = Q.front = (quer*)malloc(Max*sizeof(quer));/*初始化队列空间*/
if (!Q.front)
{
printf("内存分配失败.");
exit(0);
}
}
void breadth_Search()/*广度优先搜索*/
{
int visited[Max];/*访问标志*/
int v = 0;
VNode *H = AdjList;
VNode *u;
ArcNode *w;
VNode *p[Max];
printf("\n广度优先搜索 : ");
while (v<ALGraph.vexnum)/*把邻接表中各个单链表的首地址保存到p[]数组中*/
p[v++] = AdjList++;
for (v = 0; v<ALGraph.vexnum; v++)visited[v] = false;/*初始化访问标志*/
initquer();/*调用函数初始化栈*/
for (v = 0; v<ALGraph.vexnum; v++)/*广度搜索*/
{
if (!visited[v])
{
Q.front->date = p[v];
Q.front++;
visited[v] = true;
if (v!=0)printf("->");
printf("v%d",p[v]->Vertex+1);
while (Q.front!=Q.rear)
{
u = Q.rear->date;
Q.rear++;
for (w = u->firstarc; w!=NULL; w = w->nextarc)
{
if (!visited[w->adjvex])
{
visited[w->adjvex] = true;
printf("->v%d",w->adjvex+1);
Q.front->date = p[w->adjvex];
Q.front++;
}
}
}
}
}
printf("\n广度优化完成,");
AdjList = H;
system("pause");
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -