实验5 图的操作

?

?

?

参考代码：

?

#include "stdio.h"#include "conio.h"#define MaxVertexNum 100#define MAXSIZE 100typedef struct{    int data[MAXSIZE];    int front;    int rear;}SeqQueue;typedef char VertexType;typedef enum{FALSE,TRUE}Boolean;Boolean visited[MaxVertexNum];typedef char elemtype;/*边结点*/typedef struct node{    int adjvex;/*邻接点域*/    struct node *nextedge;/*链域*/}EdgeNode;/*顶点表结点*/typedef struct vnode{    VertexType vertex; /*顶点域*/    EdgeNode *firstedge; /*边表头指针*/}VertexNode;typedef VertexNode AdjList[MaxVertexNum];/*AdjList是邻接表类型*//*    对于简单的应用，无须定义此类型，可直接使用AdjList类型*/typedef struct{    AdjList adjlist;/*邻接表*/    int n,e;        /*当前结点数和边数*/    int kind;       /*图的种类标志*/}ALGraph;/*建立无向图的邻接表*/void CreateALGraPh(ALGraph *G1){    int i,j,k;    EdgeNode *s;    /*读入顶点数和边数*/    printf("please input vertices: ");    scanf("%d",&G1->n);getchar();    printf("please input Vertex edge number: ");    scanf("%d",&G1->e);getchar();    /*建立顶点表*/    for(i=0;i<G1->n;i++)    {        printf("please input the %dth Vertex\n",i+1);        scanf("%c",&G1->adjlist[i].vertex);getchar(); /*读入顶点信息*/        G1->adjlist[i].firstedge=NULL;    /*边表置为空表*/    }    printf("Please enter no to chart the relationship between vertices.the style is vi,vj\n\n ");    /*建立边表*/    for(k=0;k<G1->e;k++)    {        printf("the %dth is: ",k+1);        scanf("%d,%d",&i,&j);            /*读入边(vi,vj)的顶点对序号*/        s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成边表结点*/        s->adjvex=j;/*邻接点序号为j*/        s->nextedge=G1->adjlist[i].firstedge;        G1->adjlist[i].firstedge=s;/*将新结点*s插入顶点vi的边表头部*/        s=(EdgeNode *)malloc(sizeof(EdgeNode));        s->adjvex=i;/*邻接点序号为i*/        s->nextedge=G1->adjlist[j].firstedge;        G1->adjlist[j].firstedge=s; /*将新结点*s插入顶点vj的边表头部*/    }}/*邻接表表示的深度优先遍历*/void DFS(ALGraph *G1,int i){    EdgeNode *p;    printf("%c ",G1->adjlist[i].vertex);/*访问顶点vi*/    visited[i]=TRUE;/*标记vi已访问*/    p=G1->adjlist[i].firstedge;   /*取vi边表的头指针*/    while(p)    {        if(!visited[p->adjvex]) /*若vi尚未被访问，则以vj为出发点向纵深搜索*/        {           DFS(G1,p->adjvex);        }        p=p->nextedge;/*找vi的下一邻接点*/    }}/*邻接表表示的广度优先遍历*/void BFS(ALGraph *G,int k){    int i;    SeqQueue *Q;    EdgeNode *p;    /*初始队列*/    Q=(SeqQueue *)malloc(sizeof(SeqQueue));    Q->front=Q->rear=0;    printf("%c ",G->adjlist[k].vertex);    visited[k]=TRUE;    /*入队*/    Q->data[Q->rear]=k;    Q->rear=(Q->rear+1)%MAXSIZE;    Q->rear++;    while(Q->rear)    {        i=Q->data[Q->front];        Q->front=(Q->front+1)%MAXSIZE;        Q->rear--;        p=G->adjlist[i].firstedge;        while(p)        {            if(!visited[p->adjvex])            {                printf("%c ",G->adjlist[p->adjvex].vertex);                visited[p->adjvex]=TRUE;                Q->data[Q->rear]=p->adjvex;                Q->rear=(Q->rear+1)%MAXSIZE;                Q->rear++;            }            p=p->nextedge;        }    }}executeBFS(ALGraph *G){    int i;    for(i=0;i<G->n;i++)/*将图G的所有顶点设置未访问过标记 */        visited[i]=FALSE;    for(i=0;i<G->n;i++)/*对图G调用bfs函数进行广度优先搜索*/        if(!visited[i])            BFS(G,i);}main(){    ALGraph *G1;    int i;    CreateALGraPh(&G1);    printf("DFS\n");    DFS(&G1,0);    printf("\nBFS\n");    executeBFS(&G1);    getch();}

?

?

?

?

?