純C語言:檢索與周游廣度深度遍歷源碼分享

2020-01-26 15:38:41

字體：大中小

供稿：網(wǎng)友

#include <stdio.h>
typedef int datatype;   /*假定線性表元素的類型為整型*/
#define maxsize 1024    /*假定線性表的最大長度為1024*/
# define n 100            /* 圖的頂點(diǎn)最大個(gè)數(shù) */
typedef char VEXTYPE; /* 頂點(diǎn)的數(shù)據(jù)類型 */
typedef float ADJTYPE; /* 權(quán)值類型 */
typedef struct
{
VEXTYPE vexs[n] ; /* 頂點(diǎn)信息數(shù)組 */
    ADJTYPE arcs[n][n] ; /* 邊權(quán)數(shù)組 */
    int num ;    /* 頂點(diǎn)的實(shí)際個(gè)數(shù) */
}GRAPH;

/***********************1。置空圖**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}

/***********************2。求結(jié)點(diǎn)數(shù)**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}

/***********************3。創(chuàng)建圖**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("請輸入頂點(diǎn)數(shù)目：");
scanf("%d",&L->num);
printf("請輸入各頂點(diǎn)的信息(單個(gè)符號）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("請輸入邊權(quán)矩陣的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("圖已經(jīng)創(chuàng)建完畢！");
}

/***********************4。圖的輸出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("/n圖的頂點(diǎn)數(shù)目為：%d",L.num);
printf("/n圖的各頂點(diǎn)的信息為：/n");
for(i=0;i<L.num;i++)
  printf("%c ",L.vexs[i]);
printf("/n圖的邊權(quán)矩陣的信息為：/n");
for(i=0;i<L.num;i++)
{
    for(j=0;j<L.num;j++)
    {
    printf("%6.2f ",L.arcs[i][j]);
    }
    printf("/n");
}
printf("圖已經(jīng)輸出完畢！");
}

/***********************5。圖的深度周游**********************/
void DFS(GRAPH g,int qidian,int mark[])
//從第qidian個(gè)點(diǎn)出發(fā)深度優(yōu)先周游圖g中能訪問的各個(gè)頂點(diǎn)
{
int v1;
mark[qidian]=1;
printf("%c   ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
   if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
   DFS(g,v1,mark);
}
}
/***********************6。圖的深度周游**********************/
void GraphDFS(GRAPH g)
//深度優(yōu)先周游圖g中能訪問的各個(gè)頂點(diǎn)
{
int qidian,v,v1,mark[maxsize];
printf("/n深度周游：");
printf("/n請輸入起點(diǎn)的下標(biāo)：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
   DFS(g,v1,mark);
}
}
typedef int DATATYPE;     //隊(duì)列元素的數(shù)據(jù)類型
typedef struct
{
DATATYPE data[maxsize]; //隊(duì)中元素
   int front,rear;   //隊(duì)頭元素下標(biāo)、隊(duì)尾元素后面位置的下標(biāo)
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//將順序循環(huán)隊(duì)列sq置空（初始化）
{
   sq->front=0;
   sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果順序循環(huán)隊(duì)列sq為空，成功返回1，否則返回0
{
   if (sq.rear==sq.front)
      return(1);
   else
      return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//將順序循環(huán)隊(duì)列sq的隊(duì)頭元素保存到e所指地址，成功返回1，失敗返回0
{
if (QueueIsEmpty(sq))
    { printf("queue is empty!/n");return 0;}
    else
    { *e=sq.data[(sq.front)]; return 1;}
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//將元素x入隊(duì)列sq的隊(duì)尾，成功返回1，失敗返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!/n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//將隊(duì)列sq隊(duì)首元素出隊(duì)列，成功返回1,失敗返回0
{
    if (QueueIsEmpty(*sq))
    {
printf("queue is empty!/n");
return 0;
}
    else
    {
sq->front=(sq->front+1)%maxsize;
return 1;
    }
}
/***********************7。圖的廣度周游**********************/
void BFS(GRAPH g,int v,int mark[])
//從v出發(fā)廣度優(yōu)先周游圖g中能訪問的各個(gè)頂點(diǎn)
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c   ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
    QueueFront(q,&v1);
    QueueOut(&q);
    for(v2=0;v2<g.num;v2++)
    {
      if(g.arcs[v1][v2]!=0&&mark[v2]==0)
      {
     QueueIn(&q,v2);
     mark[v2]=1;
     printf("%c   ",g.vexs[v2]);
      }
     }
}
}
/***********************8。圖的廣度周游**********************/
void GraphBFS(GRAPH g)
//深度優(yōu)先周游圖g中能訪問的各個(gè)頂點(diǎn)
{
int qidian,v,v1,mark[maxsize];
printf("/n廣度周游：");
printf("/n請輸入起點(diǎn)的下標(biāo)：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
   BFS(g,v1,mark);
}
}