实验4 图的基本操作

实验目的

1． 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。

2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算

法，复习栈和队列的应用。

实验内容

程序1

/* 定义邻接矩阵类型 */

typedef int adjmatrix[n+1][n+1];

/* 建立图的邻接矩阵 */

void CreatMatrix(adjmatrix GA)

/* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */ void DfsMatrix(adjmatrix GA,int v)

/*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/ void BfsMatrix(adjmatrix GA,int v)

程序2

/* 邻接表的结点类型 */ typedef struct arc {int adjvex;

struct arc *next;}ArcNode; typedef struct VexNode {int vertex;

ArcNode *firstarc; }VerNode;

typedef VerNode AdjList[MAXNODE];

/* 建立图的邻接表 */

void CreatAdjlist(AdjList GL)

/* 从初始点v出发深度优先遍历邻接表GL表示的图 */ void DfsAdjlist(AdjList GL,int v)

/*从初始点v出发广度优先遍历邻接表GL表示的图*/ void BfsAdjlist(AdjList GL,int v)

参考源程序

程序一：以邻接表为存储结构时的遍历算法实现

#define MAXNODE 10 #define NULL 0

typedef struct arc {int adjvex;

struct arc *next;}ArcNode;

typedef struct VexNode {int vertex;

ArcNode *firstarc; }VerNode;

typedef VerNode AdjList[MAXNODE];

int visited[MAXNODE]; int vexnum,arcnum;

void creatgraph(AdjList GL) {int i,j,k;

ArcNode *p;

printf(\"请输入顶点个数和边的个数:\"); scanf(\"%d%d\

printf(\"请输入顶点(顶点用整型数代表):\\n\"); for(i=1;i<=vexnum;i++)

{scanf(\"%d\ GL[i].firstarc=NULL; }

printf(\"请输入图的所有边(一条边的两个端点中间用,分隔): , \\n\"); for(k=1;k<=arcnum;k++) {scanf(\"%d,%d\ if(i&&j) {p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->next=GL[i].firstarc;GL[i].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i;p->next=GL[j].firstarc; GL[j].firstarc=p; } } }

void DfsAdjlist(AdjList GL,int v) {int i;

for(i=1;i<=vexnum;i++) visited[i]=0; if(!visited[v]) dfs(GL,v); }

int dfs(AdjList G,int v) {ArcNode *q;

if(!visited[v]) printf(\"%d,\ visited[v]=1; q=G[v].firstarc;

while(q!=NULL)

{if(!visited[q->adjvex]) dfs(G,q->adjvex); q=q->next; } }

int BfsAdjlist(AdjList GL,int v)

{int k,i,j,Q[MAXNODE],front=0,rear=0; ArcNode *p;

for(i=1;i<=vexnum;i++) visited[i]=0; visited[v]=1;

printf(\"%d \ rear=(rear+1)%MAXNODE; Q[rear]=v;

while(front!=rear) {front=(front+1)%MAXNODE; k=Q[front]; p=GL[k].firstarc; while(p!=NULL) {if(!visited[p->adjvex]) {visited[p->adjvex]=1; printf(\"%d \ rear=(rear+1)%MAXNODE; Q[rear]=p->adjvex; } p=p->next; } } }

main()

{AdjList GL; int v;

creatgraph(GL);

printf(\"请输入深度优先遍历的开始结点:\"); scanf(\"%d\

printf(\"深度优先遍历序列是:\"); DfsAdjlist(GL,v); printf(\"\\n\");

printf(\"请输入广度优先遍历的开始结点:\"); scanf(\"%d\

printf(\"广度优先遍历序列是:\"); BfsAdjlist(GL,v); }

程序二：以邻接矩阵为存储结构时的遍历算法实现

#define n 5

#define MAXSIZE 10 /*广度优先遍历时所使用的队列的最大容量*/ #define MaxNum 10000 /*定义一个最大数*/

/* 定义邻接矩阵类型 */

typedef int adjmatrix[n+1][n+1]; /* 0号单元没用*/

int visited[n+1]; /* 0号单元没用*/ int arcnum; /*边的个数*/

/* 建立图的邻接矩阵 */

void CreatMatrix(adjmatrix GA) {int i,j,k;

printf(\"图中有%d个顶点\\n\ for(i=1;i<=n;i++) for(j=1;j<=n;j++)

if(i==j) GA[i][j]=0; /*对角线的值置为0*/

else GA[i][j]=MaxNum; /*其它位置的值初始化为一个最大数*/ printf(\"请输入边的个数(限制在1到10的范围内):\"); scanf(\"%d\

printf(\"请输入图的所有边(一条边的两个端点中间用,分隔): , \\n\"); for(k=1;k<=arcnum;k++)

{scanf(\"%d,%d\ /*读入边的信息*/ GA[i][j]=1; GA[j][i]=1; } }

/* 从初始点v出发深度优先搜索邻接矩阵GA表示的图 */ void DfsMatrix(adjmatrix GA,int v) {int j;

visited[v]=1; printf(\"%d,\ for(j=1;j<=n;j++)

if(v!=j&&GA[v][j]!=MaxNum&&!visited[j]) DfsMatrix(GA,j); }

void BfsMatrix(adjmatrix GA,int v) {int i,k,j,Q[MAXSIZE],front=0,rear=0; for(i=1;i<=n;i++) visited[i]=0;

visited[v]=1; printf(\"%d \

rear=(rear+1)%MAXSIZE; /*开始遍历的顶点入队列*/ Q[rear]=v;

while(front!=rear)

{front=(front+1)%MAXSIZE; /*队头元素出队*/ k=Q[front];

for(j=1;j<=n;j++)

if((!visited[j])&&(GA[k][j]==1)) /*访问与队头元素邻接的还未被访问的结点*/ {visited[j]=1; printf(\"%d \ rear=(rear+1)%MAXSIZE; Q[rear]=j; } } }

main()

{adjmatrix GA; int v;

CreatMatrix(GA);

printf(\"请输入深度优先遍历的开始结点:\"); scanf(\"%d\

printf(\"深度优先遍历序列是:\"); DfsMatrix(GA,v); printf(\"\\n\");

printf(\"请输入广度优先遍历的开始结点:\"); scanf(\"%d\

printf(\"广度优先遍历序列是:\"); BfsMatrix(GA,v); }