数据结构实验报告(全)安工大(7)

实验四图的遍历算法实现

一、 实验目的

掌握图的基本操作,运用图的邻接矩阵和邻接表解决问题。 二、 实验要求

建立图的邻接矩阵或邻接表，实现图的遍历（DFS/BFS） 三、实验内容

1、图的邻接矩阵或邻接表的建立 #include #include //建立邻接矩阵 #define MAXSIZE 30 #define VertexType char #define Edgetype int typedef struct{ VertexType vertexs[MAXSIZE];

Edgetype arcs[MAXSIZE][MAXSIZE]; int vertexNum,edgeNum; } MGrah;

int CreatMgrah(MGrah *G) { int i,j,k,t; scanf(\ for(i=0;ivertexNum;i++) { scanf(\ } for(i=0;iedgeNum;j++) for(j=0;jedgeNum;j++) { G->arcs[i][j]=0; } for(k=0;kedgeNum;k++) { scanf(\ G->arcs[i][j]=1; } }

//建立邻接表

#define MAXSZIE 30 typedef struct node{ int adjvertex; //InfoType info; struct node * next; }EdgeNode; typedef struct{ VertexType vertex; EdgeNode* firstedge; }VertexNode; typedef struct{ VertexNode adjlist[MAXSIZE]; int vertexNum,edgeNum; }ALGraph;

void CreatALGraph(ALGraph* G) { int i,j,k; EdgeNode* p; scanf(\ for(i=0;ivertexNum;i++) { scanf(\ G->adjlist[i].firstedge=NULL; } for(k=0;kedgeNum;k++) { scanf(\ p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvertex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } }

int main() { ALGraph* G; CreatALGraph(G); MGrah *G1; CreatMgrah(G1); }

2、图的遍历算法实现 #include #include #define MAXSIZE 100 #define VertexType char #define False 0 #define True 1 typedef struct{ int data[MAXSIZE]; int front,rear;

}SeqQueue,*PseqQueue; PseqQueue Init() { PseqQueue Q; Q=(PseqQueue)malloc(sizeof(SeqQueue)); if(Q) { Q->front=0; Q->rear=0; } return Q; }

int Empty(PseqQueue Q) { if(Q&&Q->front==Q->rear) return(1); else return(0); }

int IN(PseqQueue Q,int x) { if((Q->rear+1)%MAXSIZE==Q->front) { printf(\队满\ return -1; } else { Q->rear=(Q->rear+1)%MAXSIZE; Q->data[Q->rear]=x;

return 1; } }

int Out (PseqQueue Q,int *x) { if(Empty(Q)) { printf(\队空\ return -1; } else { Q->front=(Q->front+1)%MAXSIZE; *x=Q->data[Q->front]; return 1; } }

/*队列的初始化*/ typedef struct node{ int adjvertex; //InfoType info; struct node *next; }EdgeNode; typedef struct{ VertexType vertex; EdgeNode *firstedge; }VertexNode; typedef struct{ VertexNode adjlist[MAXSIZE]; int vertexNum,edgeNum; }ALGraph;

void CreatALGraph(ALGraph *G) { int i,j,k; EdgeNode *p; printf(\请输入（顶点数，边数）：\\n\ scanf(\ printf(\请输入顶点信息：\\n\ for(i=0;ivertexNum;i++) { scanf(\ G->adjlist[i].firstedge=NULL; } printf(\请输入边的信息：\\n\

for(k=0;kedgeNum;k++) { scanf(\ p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvertex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvertex=i; p->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=p; } }

/*深度优先搜索邻接表法*/ int visited[MAXSIZE];

void DFS(ALGraph *G, int i) {

//以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p;

printf(\ // 访问顶点vi visited[i] = True; //标记vi已访问

p = G->adjlist[i].firstedge; //取vi边表的头指针 while (p)

{ //依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvertex]) //若vi尚未被访问

DFS(G, p->adjvertex); //则以Vj为出发点向纵深搜索 p = p->next; //找vi的下一邻接点 } }

void DFStraverse(ALGraph *G) { int i;

for (i = 0; i < G->vertexNum; i++) visited[i] = False;

for (i = 0; i < G->vertexNum; i++) if (!visited[i]) DFS(G, i); }

/*广度优先搜索算法邻接表法*/ int visited1[MAXSIZE];

void BFS(ALGraph G,int v) { EdgeNode *p;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构实验报告(全)安工大(7)在线全文阅读。