Question

图的遍历

图的存储方式，不管是邻接矩阵，还是邻接表，不都得把顶点元素存在一个一维数组里么？那么对图的遍历，直接对这个一维数组遍历不就行了么？

Answer 1

你遍历一个图的顶点的前提是：两个顶点之间要有边存在。如果你用一个一维数组如何表示边的关系呢？ 遍历一个一维数组很难实现的啊。

追问

教科书上说：“从图中某个顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这个过程就叫做图的遍历。”
而图中顶点都存在一个数组里，直接对这个数组作一次循环不就行了？

追答

关键是两个顶点(V1,V2)之间如果没有边，你不能从V1遍历到V2啊。

追问

为什么不可以？？？都说了顶点都放在一个数组里了

追答

囧，我发现你连图的遍历的具体意思都没明白。
完整的定义是这样的：“从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这个过程称为图的遍历。图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其余每个顶点进行访问, 并且使图中的每个顶点仅被访问一次的过程。“

从某个顶点出发的意思就是说，它的下一个顶点与它要有边相连，如果没有边相连，是访问不到的，你一个一维数组{V1,V2,V3,...Vn};你能确定你的V1可以访问到V2吗？ V2可以访问到V3吗？

所以必须要在访问的过程中，知道边的连通信息，因此，要使用二维数组或者邻接表！

Answer 2

邻接矩阵存储结构
各个顶点存在一个一维数组中
权值存在于二维数组中
所以遍历时不但要遍历一维数组，还要访问二维数组
邻接表存储结构
各个顶点存在一个一维数组
但数组中每个元素都含两部分：1是顶点值 2是一个指针
访问时，是根据指针访问的，也不是直接访问数组

追问

教科书上说：“从图中某个顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这个过程就叫做图的遍历。”
而图中顶点都存在一个数组里，直接对这个数组作一次循环不就行了？

追答

邻接矩阵存储时，顶点是在一维数组中，直接遍历数组就行了

追问

邻接表 也是存在数组里的，只不过这个数组的类型是结构体类型 但里面包含顶点的信息。
typedef struct ArcNode{
int adjvex;
InfoType *info;
struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
VertexType data;//顶点信息
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM;

typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;

追答

你说的对，邻接表的顶点是放在一个一维数组中，并且这个数组类型是结构体，其中包含顶点信息和一个指针，我想说的是，数组中的元素实际上是每个链表的头结点，其指针域链接的是一个链表，遍历时还要访问数组元素next域指向的那些结点。。。。。。希望对你有帮助

Answer 3

apple说的很对，楼主如果开发地图肯定会把别人指向死路，或者指向坑……总之各种坑