數據結構 圖及其應用

一、要求

　　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;
    }
}

運行結果：