数据结构实验报告图的深度优先遍历算法

题目: 图的深度优先遍历算法

一、实验题目

前序遍历二叉树

二、实验目的

⑴ 掌握图的逻辑结构； ⑵ 掌握图的邻接矩阵存储结构；

⑶ 验证图的邻接矩阵存储及其深度优先遍历操作的实现。

三、实验内容与实现

⑴ 建立无向图的邻接矩阵存储；

⑵ 对建立的无向图，进行深度优先遍历；实验实现

#include #include

#define MaxVex 255 #define TRUE 1 #define FALSE 0

typedef char VertexType; typedef int Bool; Bool visited[MaxVex];

typedef struct EdgeNode { int adjvex;

struct EdgeNode *next; }EdgeNode;

typedef struct VertexNode { VertexType data; EdgeNode *firstedge; }VertexNode,AdjList[MaxVex];

typedef struct Graph{ AdjList adjList;

int numVertexes,numEdges; }Graph,*GraphAdjList;

typedef struct LoopQueue{ int data[MaxVex]; int front,rear; }LoopQueue,*Queue;

void initQueue(Queue &Q){ Q->front=Q->rear=0;

}

Bool QueueEmpty(Queue &Q){ if(Q->front == Q->rear){ return TRUE; }else{

return FALSE; } }

Bool QueueFull(Queue &Q){

if((Q->rear+1)%MaxVex == Q->front){ return TRUE; }else{

return FALSE; } }

void EnQueue(Queue &Q,int e){ if(!QueueFull(Q)){ Q->data[Q->rear] = e;

Q->rear = (Q->rear+1)%MaxVex; } }

void DeQueue(Queue &Q,int *e){ if(!QueueEmpty(Q)){

*e = Q->data[Q->front]; Q->front = (Q->front+1)%MaxVex; } }

void CreateALGraph(GraphAdjList &G){/* 建立图的邻接表结构*/

int i, j, k; if(G==NULL){

G = (GraphAdjList)malloc(sizeof(Graph)); }

printf(\输入图的结点数以及边数: \ scanf(\

fflush(stdin);

printf(\ printf(\输入各个顶点的数据:\\n\ for (i=0; inumVertexes; ++i){ printf(\顶点%d: \

scanf(\ G->adjList[i].firstedge = NULL; fflush(stdin); }

printf(\ for (k=0; knumEdges; ++k){

printf(\输入(vi,vj)上的顶点序号: \ scanf(\

EdgeNode

*ptrEdgeNode

ptrEdgeNode->adjvex = j;

ptrEdgeNode->next = G->adjList[i].firstedge; G->adjList[i].firstedge = ptrEdgeNode;

=

(EdgeNode*)malloc(sizeof(EdgeNode));