实验目的和要求
在熟悉图的存储、遍历、及其应用的基础上,通过键盘输入数据,建立一个无向图的邻接表,输出该邻接表,并计算每个顶点的度。达到巩固图的存储思想及其存储实现。
实验内容
完成下图的邻接表表示,并计算每个顶点的度。
附加要求:进行深度优先和广度优先遍历
实验时间:2020年11月10日(周二1,2节)
实验地点:10号楼413
实验提示:
1.类型定义(邻接表存储)
#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;
}
运行结果及分析:
输入图的顶点和弧的个数,从而输入顶点信息和相对应弧的相邻两个顶点,建立图的邻接表,进而输出每个顶点的度,利用深度优先搜索和广度优先搜索进行图的遍历。
心得体会:
通过此次实验,学会了构建图的邻接表,并且学习到了两种方式遍历图的顶点,对以后的学习有了很大帮助。