图的两种存储和遍历

实验7图的两种存储和遍历

一、 实验内容：

（1） 键盘输入数据，分别建立一个有向图和一个无向图的邻接表。

（2） 输出该邻接表。

（3） 在有向图的邻接表的基础上计算各顶点的度，并输出。

（4） 采用邻接表存储实现无向图的深度优先遍历。

（5） 采用邻接表存储实现无向图的广度优先遍历。

（6） 在主函数中设计一个简单的菜单，分别调试上述算法。

二、 源代码：

#include

#include

#include

#define MAX_VERTEX_NUM 20

#define OK 1

#define ERROR 0

#define OVERFLOW 0

int visited[MAX_VERTEX_NUM];

//表结点

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

char *info;

}ArcNode;

//头结点

typedef struct VNode

{

char data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

//图结构

typedef struct

{

AdjList vertices;

int vexnum,arcnum;

}ALGraph;

//用于BFS遍历的附设链队列结点结构

typedef struct QNode

{

int data;

struct QNode *next;

}QNode,*QueuePtr;

//链队列

typedef struct

{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

//初始化链队

int InitQueue(LinkQueue &Q)

{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front) exit(OVERFLOW);

Q.front->next=NULL;

return OK;

}

//元素e入队

int EnQueue(LinkQueue &Q,int e)

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p) exit(OVERFLOW);

p->next=NULL;

p->data=e;

Q.rear->next=p;

Q.rear=p;

return OK;

}

//队首元素出队,由e返回其值

int DeQueue(LinkQueue &Q,int &e)

{

QueuePtr p;

if(Q.front==Q.rear) exit(OVERFLOW);

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)

Q.rear=Q.front;

free(p);

return OK;

}

//判断队列Q是否为空

int EmptyQueue(LinkQueue Q)

{

if(Q.front==Q.rear)

return 1;

return 0;

}

//查找值为v的顶点在顶点向量G.vexs[]中的位置

int LocateVex(ALGraph G,char v)

{

int i;

for(i=0;iif(v==G.vertices[i].data)

return i;

return -1;

}

//返回v的第一个邻接顶点的序号

int FirstAdjVex(ALGraph G,char v)

{

int i;

ArcNode *p;

i=LocateVex(G,v);

if(i==-1)

return -1;

p=G.vertices[i].firstarc;

if(p)

return p->adjvex;

else

return -1;

}

//返回v的(相对于w)的下一个邻接顶点的序号

int NextAdjVex(ALGraph G,char v,char w)

{

int i,j;

ArcNode *p,*q; i=LocateVex(G,v);

j=LocateVex(G,w);

if(i==-1||j==-1||i==j)

return -1;

p=G.vertices[i].firstarc;

while(p->nextarc&&p->adjvex!=j)

p=p->nextarc;

if(p->nextarc)

{

q=p->nextarc;

return q->adjvex;

}

else

return -1;

}

//采用邻接表表示，构造有向图G

int CreateDG(ALGraph &G)

{

int v,e,i,j,t;

ArcNode *p,*q;

char tail,head;

printf(\"输入顶点个数:\");

scanf(\"%d\

if(v<0)

return ERROR;

G.vexnum=v;

printf(\"输入弧的条数:\");

scanf(\"%d\

if(e<0)

return ERROR;

G.arcnum=e;

printf(\"建立DG:\\n\");

//建立头结点顺序表

for(t=0;t{

fflush(stdin);

printf(\"输入%d的信息:\

scanf(\"%c\

G.vertices[t].firstarc=NULL;

}

//建立表结点链表(每个顶点的邻接顶点链表)

for(t=0;t{

fflush(stdin);

printf(\"输入弧的信息(弧尾-弧头)\");

scanf(\"%c%*c%c\

i=LocateVex(G,tail);

j=LocateVex(G,head);

if(i==-1||j==-1||i==j)

return ERROR;

p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=j;

p->info=NULL;

p->nextarc=NULL;

if(!G.vertices[i].firstarc)

G.vertices[i].firstarc=p;

else

{

for(q=G.vertices[i].firstarc;q->nextarc;

q=q->nextarc);

q->nextarc=p;

}

}

}

//从第v个顶点出发，递归的深度优先遍历有向图G

int DFS(ALGraph G,int v)

{

int w;

visited[v]=-1;

printf(\"%c \

w=FirstAdjVex(G,G.vertices[v].data);

for(;w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))

if(!visited[w])

DFS(G,w);

return OK;

}

//深度优先搜索遍历图G

int DFSTraverse(ALGraph G)

{

int i;

for(i=0;ivisited[i]=0;

for(i=0;iif(!visited[i])

DFS(G,i);

return OK;

}

//广度优先搜索遍历图G

int Visit(char v)

{

printf(\"%c \

return OK;

}

//从第v个顶点出发，递归的广度优先遍历有向图G

int BFSTraverse(ALGraph G,int(*visit)(char v)) {

LinkQueue Q;

int v,w,u;

for(v=0;vvisited[v]=0;

InitQueue(Q);

for(v=0;v{

if(!visited[v])

{

visited[v]=1;

Visit(G.vertices[v].data);

}

EnQueue(Q,v);

while(!EmptyQueue(Q))

{

DeQueue(Q,u);

for(w=FirstAdjVex(G,G.vertices[u].data);

w>0;

w=NextAdjVex (G,G.vertices[u].data,G.vertices[w].data))

if(!visited[w])

{

visited[w]=1;

Visit(G.vertices[w].data);

EnQueue(Q,w);

}

}

}

return OK;

}

//主函数

void main() {

ALGraph G;

printf(\"建立有向图G\\n\");

if(CreateDG(G))

{

printf(\"深度优先搜索的顺序:\");

DFSTraverse(G);

printf(\"\\n\");

printf(\"广度优先搜索的顺序:\");

BFSTraverse(G,Visit);

}

printf(\"\\n\");

}

三、运行结果：