论坛 › Java › 数据结构 图及其应用

光之使者 发表于 2024-2-23 07:14:46

数据结构 图及其应用

一、要求
　　1.设计并验证如下算法：图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。
　　2.设计并验证如下算法：带权图采用邻接表表示，实现无向图的广度优先搜索与有向图的深度优先搜索。
二、代码
1.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef struct queue
{
    int Data;
    int front;
    int rear;
}SqQueue;


int visited;//1--已访问   0--未访问

typedef struct mgraph
{
    char vexs;//顶点向量
    int arcs;//邻接矩阵
    int vexnum;//图的顶点数
}Mgraph;

void init_queue(SqQueue *);
void EnQueue(SqQueue *,int);
void DeQueue(SqQueue *);
int empty_queue(SqQueue *);
void DFS(Mgraph G,int v);
void DFSTraverse(Mgraph G);
void BFSTraverse(Mgraph G);

int main()
{
    Mgraph G;
    printf("请输入图的顶点数\n");
    scanf("%d",&G.vexnum);
    printf("输入图的各个顶点向量\n");
    scanf("%s",&G.vexs);
    srand((unsigned)time(NULL));
    for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵
    {
      for(int j=0;j<G.vexnum;j++)
            G.arcs=rand()%2;
    }
    printf("该图的邻接矩阵如下：\n");
    for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵
    {
      for(int j=0;j<G.vexnum;j++)
            printf("%d ",G.arcs);
      printf("\n");
    }
    printf("深度优先遍历结果如下：\n");
    DFSTraverse(G);
    printf("\n");
    printf("广度优先遍历结果如下：\n");
    BFSTraverse(G);
    return 0;
}
void DFSTraverse(Mgraph G)
{
    for(int v=0;v<G.vexnum;v++)//标记赋值为未访问
      visited=0;
    for(int v=0;v<G.vexnum;v++)//调用DFS
      if(!visited)
         DFS(G,v);
}
void DFS(Mgraph G,int v)
{
    visited=1;
    printf("%c ",G.vexs);
    for(int n=0;n<G.vexnum;n++)
    {
      if((visited==0)&&(G.arcs==1))
            DFS(G,n);
    }
}

void BFSTraverse(Mgraph G)//广度优先遍历
{
    SqQueue Q;
    for(int i=0;i<G.vexnum;i++)
      visited=0;
    init_queue(&Q);
    for(int i=0;i<G.vexnum;i++)
    {
      if(!visited)
      {
            visited=1;
            printf("%c ",G.vexs);
            EnQueue(&Q,i);
      }
      while(!empty_queue(&Q))
      {
            DeQueue(&Q);
            for(int j=0;j<G.vexnum;j++)
            {
                if(!visited&&G.arcs)
                {
                  visited=1;
                  printf("%c ",G.vexs);
                  EnQueue(&Q,j);
                }
            }
         }
    }
}

void init_queue(SqQueue *Q)
{
    Q->front=Q->rear=0;
}

void EnQueue(SqQueue *Q,int e)
{
      Q->Data=e;
      Q->rear++;
}

void DeQueue(SqQueue *Q)
{
    Q->front++;
}

int empty_queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
      return 1;
    else
      return 0;
} 
运行结果：
 
 https://img2023.cnblogs.com/blog/3318273/202312/3318273-20231217205534419-817485348.png

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

查看完整版本: 数据结构 图及其应用