程序填空题：本题要求实现对图的深度优先遍历（邻接矩阵表示图）
本题要求实现对图的深度优先遍历，并输出结点信息。
本题中图的表示采用邻接矩阵表示方法。
```c
#include
#include
#include//使用INT_MAX宏，指定整数变量不能存储超出此限制的任何值
typedef struct GRAPHMATRIX_STRU
{
int size; //图中结点的个数
int **graph; //二维数组保存图
}GraphMatrix;
GraphMatrix* InitGraph(int num)
{
int i;
int j;
GraphMatrix* graphMatrix = (GraphMatrix*)malloc(sizeof(GraphMatrix));
graphMatrix->size = num;
graphMatrix->graph = (int**)malloc(sizeof(int*)* graphMatrix->size);
for (i = 0; isize; i++)
{
graphMatrix->graph[i] = (int*)malloc(sizeof(int)* graphMatrix->size);
}
for (i = 0; isize; i++)
{
for (j = 0; jsize; j++)
{
graphMatrix->graph[i][j] = INT_MAX;
}
}
return graphMatrix;
}
void ReadGraph(GraphMatrix* graphMatrix)
{
int vex1, vex2, weight;
//输入方式为点 点 权值，权值为0，则输入结束
scanf("%d %d %d", &vex1, &vex2, &weight);
while (weight != 0)
{
graphMatrix->graph[vex1][vex2] = weight;
scanf("%d %d %d", &vex1, &vex2, &weight);
}
}
/*从结点i开始深度优先遍历 */
void DFS(GraphMatrix* graphMatrix, int * visited, int i)
{
int j;
visited[i] = 1;
printf("%d ", i);
for (j = 0; j < graphMatrix->size; j++)
{
if (graphMatrix->graph[i][j] != INT_MAX && !visited[j])
@@[DFS(graphMatrix, visited, j)](3);
}
}
/*图的深度优先遍历*/
void DFSGraphMatrix(GraphMatrix* graphMatrix)
{
int i;
int *visited = (int*)malloc(sizeof(int)* graphMatrix->size);
for (i = 0; i < graphMatrix->size; i++)
visited[i] = 0;
for (i = 0; i < graphMatrix->size; i++)
if (@@[!visited[i]|visited[i]==0](3))
@@[DFS(graphMatrix, visited, i)](3);
}
int main()
{
GraphMatrix *graphMatrix = NULL;
graphMatrix = InitGraph(7);
ReadGraph(graphMatrix);
DFSGraphMatrix(graphMatrix);
return 0;
}
```
答案：
第1空：DFS(graphMatrix, visited, j)
第2空：!visited[i]|visited[i]==0
第3空：DFS(graphMatrix, visited, i)
本题中图的表示采用邻接矩阵表示方法。
```c
#include
#include
#include
typedef struct GRAPHMATRIX_STRU
{
int size; //图中结点的个数
int **graph; //二维数组保存图
}GraphMatrix;
GraphMatrix* InitGraph(int num)
{
int i;
int j;
GraphMatrix* graphMatrix = (GraphMatrix*)malloc(sizeof(GraphMatrix));
graphMatrix->size = num;
graphMatrix->graph = (int**)malloc(sizeof(int*)* graphMatrix->size);
for (i = 0; i
{
graphMatrix->graph[i] = (int*)malloc(sizeof(int)* graphMatrix->size);
}
for (i = 0; i
{
for (j = 0; j
{
graphMatrix->graph[i][j] = INT_MAX;
}
}
return graphMatrix;
}
void ReadGraph(GraphMatrix* graphMatrix)
{
int vex1, vex2, weight;
//输入方式为点 点 权值，权值为0，则输入结束
scanf("%d %d %d", &vex1, &vex2, &weight);
while (weight != 0)
{
graphMatrix->graph[vex1][vex2] = weight;
scanf("%d %d %d", &vex1, &vex2, &weight);
}
}
/*从结点i开始深度优先遍历 */
void DFS(GraphMatrix* graphMatrix, int * visited, int i)
{
int j;
visited[i] = 1;
printf("%d ", i);
for (j = 0; j < graphMatrix->size; j++)
{
if (graphMatrix->graph[i][j] != INT_MAX && !visited[j])
@@[DFS(graphMatrix, visited, j)](3);
}
}
/*图的深度优先遍历*/
void DFSGraphMatrix(GraphMatrix* graphMatrix)
{
int i;
int *visited = (int*)malloc(sizeof(int)* graphMatrix->size);
for (i = 0; i < graphMatrix->size; i++)
visited[i] = 0;
for (i = 0; i < graphMatrix->size; i++)
if (@@[!visited[i]|visited[i]==0](3))
@@[DFS(graphMatrix, visited, i)](3);
}
int main()
{
GraphMatrix *graphMatrix = NULL;
graphMatrix = InitGraph(7);
ReadGraph(graphMatrix);
DFSGraphMatrix(graphMatrix);
return 0;
}
```
答案：
第1空：DFS(graphMatrix, visited, j)
第2空：!visited[i]|visited[i]==0
第3空：DFS(graphMatrix, visited, i)
