Question

数据结构中图的深度遍历问题：

# include <stdio.h># define Maxsize 10
typedef struct graph{
int vertex[Maxsize];//存放顶点的数组

int arc[Maxsize][Maxsize];//邻接矩阵二维数组
int visited[Maxsize];//顶点一位数组
int vertexNum;//图的顶点数
int arcNum;//图的边数}Graph;
void init(Graph G)
{
printf("请输入顶点的数：");
scanf("%d", &G.vertexNum);

printf("请输入边的数目：");
scanf("%d", &G.arcNum);

printf("请输入顶点的值：");
for (int i=0; i<G.vertexNum; i++)//初始化顶点数组
{
int val;//临时存放顶点的值；
scanf("%d", &val);
G.vertex[i] = val;
}

for (int v=0; v<G.vertexNum; v++)//初始化邻接矩阵 for (int j=0; j<G.vertexNum; j++)
{
G.arc[v][j] = 0;
}

printf("请输入边依附的顶点编号：");
for (int k=0; k<G.arcNum; k++)//建立图的邻接矩阵。 {
int i;
int j;

scanf("%d%d", &i, &i);
G.arc[i][j] = 1;
G.arc[j][i] = 1;
}

for (int r=0; r<G.vertexNum; r++)//初始化标记数组 {
G.visited[r] = 0;
}
}

void DFTraverse(Graph G, int v)//深度优先遍历{
printf("%d ", G.vertex[v]);
G.visited[v] = 1;

for (int i=0; i<G.vertexNum; i++) {
if (G.arc[v][i] == 1 && G.visited[i] == 0)
{
DFTraverse(G, i);
}
}
}

/*疑问：假如将ppt中的那个图进行初始化一个图，那么我们将图中的顶点依次按照：0， 1， 2， 3 输入并存在 顶点数组中。
然后再将边所依附的顶点输入：0 1 0 3 1 3 1 2 建立邻接矩阵。

当我们遍历的时候，先输出 vertex[0],值为0， 判断arc[0][1]; 满足条件，于是输出vertex[1]; 值为1；
这是遍历的时候根据邻接矩阵输出的， 只要开始建立的时候将边所依附的点输入的一样，不管是先输入的那个
边，最后建立的邻接矩阵都是一样的，所以进行遍历的时候假如都从0开始，肯定是先输出vertex[0]; vertex[1];
vertex[2];

问题在于：如果按照这种输出办法，那么我们将顶点保存到顶点数组vertex中的顺序不同，最后输出就不同。这很
显然不对啊。例如，第一种输入顶点的顺序是：0， 1， 2， 3，
遍历结果是：0， 1， 2， 3；
第二种输入顶点顺序为： 0， 2， 1， 3，
遍历结果是：0， 2， 1， 3； //很显然是错的，
因为第二次输入的时候vertex[0] = 0;
vertex[1] = 2;
*/
以不同 的顺序输入一个图的顶点，从同一点例如0.开始遍历，最后由于输入顶点的顺序不同而遍历结果不同，这这么解释？？？？按道理说，同一个图，同一个开始点，遍历的结果应该是相同 的。
我也知道从同一个点开始也可能结果不同，但是就上面的 这个图，v0访问完了就应该访问v1或是v3
也不是v2啊，但是，我们将顶点的输入顺序为：v0， v2 ， v1， v3，那么按照深度遍历函数可以看到输出的顺序为；v0 ， v2， v1， v3，
这很明显是不对的 ，怎么解释，遍历代码是从书上抄的，肯定没有问题。

Answer 1

通常情况下，我们会按照结构模型把系统产生的数据分为三种类型：结构化数据、半结构化数据和非结构化数据。结构化数据，即行数据，是存储在数据库里，可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据，它们可以某种标准格式存在于文件或记录的固定字段中。相对应的，没有固定结构不方便用数据库二维逻辑表来表现的数据即称为非结构化数据，包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。我们都知道，结构化的数据很容易被采集和存储，分析展示起来也很容易，市场上已经有很多成熟的BI…

Answer 2

程序我没看哈。就回答你最后那几句话：同一个图，同一个开始点，深度搜索出来的结果仍然肯能不同啊。就如你上面的图，V0-V1-V2-V3 和V0-V3-V1-v2都是符合的。更何况你输入的顶点顺序不同呢。但像你上面举得那个例子，那明显就是错的，这时就说明你代码有问题，自己调试吧兄弟。

追问

我也知道从同一个点开始进行同一种遍历可能结果不同，但是就上面的这例子，访问完v0，肯定不是v2，要么是v3，或是v1啊，当将点的顺序输入为：v0，v2, v1， v3，但是按照深度遍历函数可以看到，访问完v0后，访问vertex[1],此时的vertex[1]为v2，所以很明显不对啊，上面的代码是我从书上抄的，应该没有问题。求解，解答有加分

追答

你那代码是从哪里搞的，我改了好半天，你好歹把你跑的程序代码贴上来。没事儿给顶点赋值干嘛，老老实实初始化时0对应0,1对应1，正是没这样干，才把你搞糊涂啦，当然它这样做是为了在遍历时起点可改变。你输入0,2,1,3，就相当于v[0]=0,v[1]=2,v[2]=1,v[3]=3。现在假如我们从V0开始遍历，结果就是V0，V1，V2，V3，可你代码输出用的是 printf("%d  ", G.vertex[v]);，即输出0,2,1,3。没错啊，这里0,2,1,3，又不是对应节点号。printf("%d  ", v);改成这样就容易明白啦。

学习这个东西，头脑想不通，就自己学会跑程序。然后再不懂就把你跑的代码发上来。你这种大大浪费我的时间。

既然帮你就帮到底，下面是代码（你自己再修正一下）：

# include <stdio.h>

# define Maxsize 10

typedef struct graph

{

 int vertex[Maxsize];//存放顶点的数组

 

 int arc[Maxsize][Maxsize];//邻接矩阵二维数组

 int visited[Maxsize];//顶点一位数组

 int vertexNum;//图的顶点数

 int arcNum;//图的边数

}Graph;

void init(Graph &G)

{

 printf("请输入顶点的数：");

 scanf("%d", &G.vertexNum);

 

 printf("请输入边的数目：");

 scanf("%d", &G.arcNum);

 

 printf("请输入顶点的值：");

 for (int i=0; i<G.vertexNum; i++)//初始化顶点数组

 {

  int val;//临时存放顶点的值；

  scanf("%d", &val);

  G.vertex[i] = val; 

 }

 

 for (int v=0; v<G.vertexNum; v++)//初始化邻接矩阵 

 for (int j=0; j<G.vertexNum; j++)

  {

   G.arc[v][j] = 0;

  }

 

 printf("请输入边依附的顶点编号：");

 for (int k=0; k<G.arcNum; k++)//建立图的邻接矩阵。 

 {

  int i;

  int j;

 

  scanf("%d-%d", &i, &j);

  G.arc[i][j] = 1;

  G.arc[j][i] = 1;

 }

 

 for (int r=0; r<G.vertexNum; r++)//初始化标记数组

 {

  G.visited[r] = 0;

 }

}

 

void DFTraverse(Graph G, int v)//深度优先遍历

{

 printf("%d  ", v);

 G.visited[v] = 1;

 

 for (int i=0; i<G.vertexNum; i++) 

 {

if (G.arc[v][i] == 1 && G.visited[i] == 0)

DFTraverse(G, i);

  }

}

int main()

{

Graph G;

init(G);

DFTraverse(G,1);

return 0;

}

结果有点小问题，这你自己去思考吧。

追问

多谢批评，受教，可算是遇到大神了， 你说的很对，就是这个问题，改成printf("%d", v);
在这里是对的，那是因为这里很巧，顶点存的是数， j = 1时正巧是点1，可以输出 v
但是，假如顶点数组中存的是字符 ， 根据临边矩阵，判断的结果依然是 j = 1；时可访问
那怎么输出呢？？？？
真心求解，我提高悬赏，

追答

还没搞懂啊。当然它这样做是为了在遍历时起点可改变。这是上面说的话。本来顶点数组就不用存东西，懂不？存字符，就大错特错啦（对于你这个程序而言的）。
我先发了代码的，不知怎么搞的，怎么看不见啦。算啦。
先给你说下，你这个程序，你想一下，顶点里存上0就行啦，完全不用另外还搞个visit数组。
我们遍历就按顶点数组下标来，遍历了的，就设置其为1。如果你想顶点信息含字符的话，你把顶点设置为结构体不就行啦。

追问

，visited数组没有必要，这个我们先不讨论，我要问的是：你按照顶点素族下表访问时，如果，对定点数组赋值时：vertex[0] = v0;  vertex[1] =  v1;  vertex[2] = v2; vertex[3] = v3; 

那书结果是对的，如果vertex[0] = v0;  vertex[1] =  v3;  vertex[2] = v2; vertex[3] = v1；那么很显然，都从零开始访问时：结果是错的，输出 v0， v3， v2， v1，你上面的改成   printf("%d", v);   这恰好是第i个存是i。

追答

如果用printf("%d", v);就是按我说的按顺序对应存，这是要求，因为如果按vertex[0] = v0; vertex[1] = v3; vertex[2] = v2; vertex[3] = v1；这样来理解，就有问题，我们的v是下标，才是我们真正对应的节点，你结果赋个值为V1，V2的，你这不是混淆自己吗。
如果用printf("%d", G.vertex[v]),也没错，此时你就可以随意赋值啦。拿你上面的例子来说。
第二种输入顶点顺序为： 0， 2， 1， 3，
遍历结果是：0， 2， 1， 3；这里0,2,1,3不是节点序号，而是节点值。
你输入0,2,1,3，就相当于v[0]=0,v[1]=2,v[2]=1,v[3]=3，输出0,2,1,3，对应值去看节点序号，
就是V0,V1,V2,V3.这遍历也是对的啊，只不过它输出地是节点的信息而已，你可以将节点信息换成字符型，这样你也好理解。再没懂算啦，睡觉去吧。