实验目的和要求
在熟悉图的存储、遍历、及其应用的基础上，通过键盘输入数据，建立一个无向图的邻接表，输出该邻接表，并计算每个顶点的度。达到巩固图的存储思想及其存储实现。
实验内容
完成下图的邻接表表示，并计算每个顶点的度。
附加要求：进行深度优先和广度优先遍历
编辑
实验时间：2020年11月10日（周二1，2节）
实验地点：10号楼413
实验提示:
１．类型定义（邻接表存储）
#define MAX_VERTEX_NUM 8 //顶点最大个数
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight; //边的权
}ArcNode; //表结点
#define VertexType char //顶点元素类型
typedef struct VNode
{
int degree;//顶点的度，入度
VertexType data;
ArcNode *firstarc;
}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;//顶点的实际数，边的实际数
}ALGraph;
程序流程图：
编辑
程序代码：
#include <iostream> #include <stdio.h> #include <queue> using namespace std; const int max_n = 100; bool vi[max_n]; int num[max_n] = { 0 }; queue<int>q; typedef struct ArcNode { char adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode; //表结点 typedef struct VNode { char data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 }VNode/*头结点*/,AdjList[max_n]; typedef struct { AdjList vertices; int vexnum,arcnum;//顶点的实际数，边的实际数 }AlGraph; int locat(AlGraph g, char v) { for (int i = 0; i < g.vexnum; i++) { if (g.vertices[i].data == v) return i; } } void creatGraph(AlGraph& g) { ArcNode* p1; ArcNode* p2; printf("请输入图的顶点个数和边的条数：\n"); cin >> g.vexnum >> g.arcnum; printf("请输入顶点的信息：\n"); for (int i = 0; i < g.vexnum; i++) { cin >> g.vertices[i].data; g.vertices[i].firstarc = NULL; } char v1, v2; printf("请输入弧的相邻两个顶点\n"); for (int j = 0; g.arcnum > j; j++) { cin >> v1 >> v2; char a = locat(g, v1);//v1的位置 char b = locat(g, v2);//v2的位置 p1 = new ArcNode; p2 = new ArcNode; p1->adjvex = b; p1->nextarc = g.vertices[a].firstarc; g.vertices[a].firstarc = p1; p2->adjvex = a; p2->nextarc = g.vertices[b].firstarc; g.vertices[b].firstarc = p2; num[a] =num[a] + 1;//度加一 num[b] =num[b] + 1; } } void dfs(AlGraph g, int v) { printf("%c",g.vertices[v].data); vi[v] = true; ArcNode* p; p = g.vertices[v].firstarc; while (p != NULL) { int w = p->adjvex; if (!vi[w]) dfs(g, w); p = p->nextarc; } } void bfs(AlGraph g, int v) { printf("%c",g.vertices[v].data); vi[v] = true; q.push(v); while (!q.empty()) { int u = q.front(); q.pop(); ArcNode* p; p = g.vertices[u].firstarc; while (p != NULL) { if (!vi[p->adjvex]) { cout << g.vertices[p->adjvex].data; vi[p->adjvex] = true; q.push(p->adjvex); } p = p->nextarc; } } } int main() { AlGraph g; creatGraph(g); int n = 0; for(int n=0;n<g.vexnum;n++) printf("点%c的度为：%d\n",g.vertices[n].data,num[n]); printf("深度优先搜索：\n"); dfs(g, 0); for (int i = 0; i < max_n; i++) { vi[i] = false; } printf("\n广度优先搜索：\n"); bfs(g, 0); return 0; }
运行结果及分析：
编辑
输入图的顶点和弧的个数，从而输入顶点信息和相对应弧的相邻两个顶点，建立图的邻接表，进而输出每个顶点的度，利用深度优先搜索和广度优先搜索进行图的遍历。
心得体会：
通过此次实验，学会了构建图的邻接表，并且学习到了两种方式遍历图的顶点，对以后的学习有了很大帮助。
