1. 实验目的
通过上机实验进一步掌握图的存储结构及基本操作的实现。
2. 实验内容与要求
要求:
⑴ 能根据输入的顶点、边/弧的信息建立图;
⑵ 实现图中顶点、边/弧的插入、删除;
⑶ 实现对该图的深度优先遍历;
⑷ 实现对该图的广度优先遍历。
备注:单号基于邻接矩阵,双号基于邻接表存储结构实现上述操作。
3. 数据结构设计
逻辑结构:图状结构
存储结构:顺序存储结构、链式存储结构
4. 算法设计
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
char data[2]; //顶点就设置和书上
V1 等等一样吧
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct
{
int data[MAX_VERTEX_NUM+10];
int front;
int rear;
}queue;
int visited[MAX_VERTEX_NUM];
queue q;
int main()
{
ALGraph G;
int CreateUDG(ALGraph &G);
int DeleteUDG(ALGraph &G);
int InsertUDG(ALGraph &G);
void BFSTraverse(ALGraph G, int
(*Visit)(ALGraph G,ArcNode v));
int PrintElement(ALGraph G,ArcNode
v);
void menu();
void depthfirstsearch(ALGraph *g,int
vi);
void travel(ALGraph *g);
void breadfirstsearch(ALGraph *g);
int i;
G.arcnum = G.vexnum = 0;
while(1)
{
menu();
do
{
printf ( "请输入要进行的操作\
n" );
scanf ("%d",&i);
if (i<1||i>6)
printf(" 错误数字,请重
新输入");
}while (i<1||i>6);