图的存储结构和遍历
一、图的存储结构
图的存储结构是指将图结构存储在计算机中的方法。常见的图存储结构有两种：邻接矩阵存储法和邻接表存储法。
1. 邻接矩阵存储法
邻接矩阵存储法是将图的节点之间的关系存储在一个二维数组中。邻接矩阵的每个元素表示两个节点之间是否有关系。如果两个节点之间有关系，则对应的元素值为1，否则为0。
例如，在上面的实验报告中，邻接矩阵示意图如下：
V0 v1 v2 v3 v4 v5
V0 0 1 0 1 0 1
V1 1 0 1 1 1 0
V2 0 1 0 0 1 0
V3 1 1 0 0 1 1
V4 0 1 1 1 0 0
V5 1 0 0 1 0 0
2. 邻接表存储法
邻接表存储法是将图的节点之间的关系存储在一个链表中。每个节点对应一个链表，链表中的每个元素表示该节点与其他节点之间的关系。
例如，在上面的实验报告中，邻接表存储图如下：
...
二、图的遍历
图的遍历是指从图中的一个节点出发，访问图中的所有节点的过程。常见的图遍历方法有两种：深度优先遍历和广度优先遍历。
1. 深度优先遍历
深度优先遍历是从图中的一个节点出发，沿着边访问邻接节点，直到访问所有节点为止。深度优先遍历的实现可以使用递归或栈来实现。
例如，在上面的实验报告中，深度优先遍历算法的实现如下：
void dfs(AdjList *G, int v) {
visited[v] = 1;
printf("%d ", v);
Arode *p = G[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
dfs(G, p->adjvex);
}
p = p->nextarc;
}
}
2. 广度优先遍历
广度优先遍历是从图中的一个节点出发，访问所有邻接节点，然后访问所有邻接节点的邻接节点，直到访问所有节点为止。广度优先遍历的实现可以使用队列来实现。
例如，在上面的实验报告中，广度优先遍历算法的实现如下：
void bfs(AdjList *G, int v) {
queue q;
initqueue(&q);
enque(&q, v);
visited[v] = 1;
printf("%d ", v);
while (!isempty(&q)) {
v = deque(&q);
Arode *p = G[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
enque(&q, p->adjvex);
visited[p->adjvex] = 1;
printf("%d ", p->adjvex);
}
p = p->nextarc;
}
}
}
三、实验方法和步骤
实验中，我们使用Visual C++ 6.0作为实验环境。实验步骤如下：
1. 我们使用二维数组来表示图中节点与节点的关系。
2. 然后，我们设计了一个将邻接矩阵转换为邻接表的算法，并设计了一个在屏幕上显示邻接表的算法。
3. 接下来，我们实现了基于邻接表的深度优先遍历算法和广度优先遍历算法，并输出了遍历序列。
四、结论
实验结果表明，我们成功地实现了图的存储结构和遍历算法。邻接矩阵存储法和邻接表存储法都是图存储结构的有效方法，而深度优先遍历和广度优先遍历是图遍历的两种常见方法。
VIP享7折，此内容立减5.97元 
