数据结构 图及其应用

一、要求

　　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[MAX_VERTEX_NUM];
    int front;
    int rear;
}SqQueue;


int visited[MAX_VERTEX_NUM];//1--已访问   0--未访问 

typedef struct mgraph
{
    char vexs[MAX_VERTEX_NUM];//顶点向量 
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
    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[i][j]=rand()%2;
    }
    printf("该图的邻接矩阵如下：\n");
    for(int i=0;i<G.vexnum;i++)//随机生成邻接矩阵 
    {
        for(int j=0;j<G.vexnum;j++)
            printf("%d ",G.arcs[i][j]);
        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[v]=0; 
    for(int v=0;v<G.vexnum;v++)//调用DFS 
        if(!visited[v])
           DFS(G,v); 
}
void DFS(Mgraph G,int v)
{
    visited[v]=1;
    printf("%c ",G.vexs[v]);
    for(int n=0;n<G.vexnum;n++)
    {
        if((visited[n]==0)&&(G.arcs[v][n]==1))
            DFS(G,n);
    }
}

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

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

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

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

int empty_queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}

运行结果

 2.

#include<stdio.h>
#include<stdlib.h>  
#define MAX_SIZE 20
int visited[MAX_SIZE];

typedef struct queue
{
    int Data[MAX_SIZE];
    int front;
    int rear;
}SqQueue;

typedef struct ArcNode 
{
    int adjvex;//该弧指向顶点的位置 
    struct ArcNode *next;
}ArcNode;

typedef struct vnode
{
    int data;//顶点信息 
    ArcNode *first;//指向第一条依附该顶点的弧的指针 
}VNode;    

typedef struct 
{
    VNode vertices[MAX_SIZE];
    int vexnum;
    int edgenum;
}ALGraph;

void init_queue(SqQueue *);
void EnQueue(SqQueue *,int);
void DeQueue(SqQueue *);
int empty_queue(SqQueue *);
void DFSTraverse(ALGraph *G);
void DFS(ALGraph *G,int v); 
void BFSTraverse(ALGraph G);
void createALGraph(ALGraph *);                                                                                                                                                                                                                                                                                                                                                            
int main()
{
    ALGraph G;
    createALGraph(&G);
    DFSTraverse(&G);
    printf("\n");
    BFSTraverse(G);
    return 0;
 } 
 void DFSTraverse(ALGraph *G)
{
    for(int v=0;v<G->vexnum;v++)//标记赋值为未访问 
        visited[v]=0; 
    for(int v=0;v<G->vexnum;v++)//调用DFS 
        if(!visited[v])
           DFS(G,v); 
}
void DFS(ALGraph *G,int v)
{
    ArcNode *p;
    p = G->vertices[v].first;
    visited[v]=1;
    printf("%d ",G->vertices[v].data);
    while(p)
    {
        if(!visited[p->adjvex])
            DFS(G,p->adjvex);
        p=p->next;
    }
    
}

void BFSTraverse(ALGraph G)
{
    SqQueue Q;
    ArcNode *p;
    for(int i=0;i<G.vexnum;i++)
        visited[i]=0;
    init_queue(&Q);
    for(int i=0;i<G.vexnum;i++)
    {
        p = G.vertices[0].first;
        if(!visited[i])
        {
            visited[i]=1;
            printf("%d ",G.vertices[i].data);
            EnQueue(&Q,i);
        }
        while(!empty_queue(&Q))
        {
            DeQueue(&Q);
            while(p)
            {
                if(!visited[p->adjvex])
                {
                    visited[p->adjvex]=1;
                    printf("%d ",G.vertices[p->adjvex].data);
                    EnQueue(&Q,i);
                }
                p=p->next;
            }
                    
        }    
    }
}

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

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

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

int empty_queue(SqQueue *Q)
{
    if(Q->front==Q->rear)
        return 1;
    else
        return 0;
}

void createALGraph(ALGraph *G)
{
    int i, j;
    ArcNode *e; 
    printf("输入顶点数和边数：\n");
    scanf("%d %d",&G->vexnum,&G->edgenum);
    printf("输入顶点");
    for(i = 0; i < G->vexnum; i++)
    {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].first = NULL;
    } //输入边
    printf("输入边（i, j）上的顶点：\n");
    for(int k = 0; k < G->edgenum; k++)
    {
        scanf("%d %d", &i, &j);
        e = (ArcNode *) malloc (sizeof (ArcNode));
        e->adjvex = j;
        e->next = G->vertices[i].first;
        G->vertices[i].first = e;
        e = (ArcNode *) malloc (sizeof (ArcNode));
        e->adjvex = i;
        e->next = G->vertices[j].first;
        G->vertices[j].first= e;
    }
}

运行结果：