程序填空题：本题要求实现对图的深度优先遍历（邻接表表示图）
本题要求实现对图的深度优先遍历。
本题中图的表示采用邻接表表示
```c
#include
#include
typedef struct GRAPHLISTNODE_STRU
{
int nodeno; /*图中结点的编号 */
struct GRAPHLISTNODE_STRU* next; /*指向下一个结点的指针 */
}GraphListNode;
typedef struct GRAPHLIST_STRU
{
int size; /* 图中结点的个数 */
GraphListNode* graphListArray; /*图的邻接表 */
}GraphList;
GraphList* InitGraph(int num)
{
int i;
GraphList *graphList = (GraphList *)malloc(sizeof(GraphList));
graphList->size = num;
graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode)*num);
for (i = 0; i {
graphList->graphListArray[i].next = NULL;
graphList->graphListArray[i].nodeno = i;
}
return graphList;
}
void ReadGraph(GraphList* graphList)
{
int vex1, vex2;
GraphListNode *tempNode = NULL;
/** 输入方式为点 点 ，点为-1，则输入结束 **/
scanf("%d %d", &vex1, &vex2);
while (vex1 >= 0 && vex2 >= 0)
{
tempNode = (GraphListNode*)malloc(sizeof(GraphListNode));
tempNode->nodeno = vex2;
//tempNode->next = NULL;
/**采用头插法**/
@@[tempNode->next = graphList->graphListArray[vex1].next](3);
@@[graphList->graphListArray[vex1].next = tempNode](3);
scanf("%d %d", &vex1, &vex2);
}
}
/*从节点i开始深度优先遍历*/
void DFS(GraphList* graphList, int * visited, int i)
{
int j;
GraphListNode *tempNode = NULL;
visited[i] = 1;
printf("%d ", i);
tempNode = graphList->graphListArray[i].next;
while (tempNode != NULL)
{
if (!visited[tempNode->nodeno])
@@[DFS(graphList, visited, tempNode->nodeno)](3);
@@[tempNode = tempNode->next](3);
}
}
/*图的深度优先遍历*/
void DFSGraphList(GraphList* graphList)
{
int i;
/* 用于记录图中哪些结点已经被访问了 */
int *visited = (int*)malloc(sizeof(int)* graphList->size);
/* 初始化为点都没有被访问 */
for (i = 0; i < graphList->size; i++)
visited[i] = 0;
for (i = 0; i < graphList->size; i++)
if (!visited[i])
DFS(graphList, visited, i);
}
int main()
{
GraphList *graphList = NULL;
graphList = InitGraph(6);
ReadGraph(graphList);
DFSGraphList(graphList);
return 0;
}
```
答案：
第1空：tempNode->next = graphList->graphListArray[vex1].next
第2空：graphList->graphListArray[vex1].next = tempNode
第3空：DFS(graphList, visited, tempNode->nodeno)
第4空：tempNode = tempNode->next
本题中图的表示采用邻接表表示
```c
#include
#include
typedef struct GRAPHLISTNODE_STRU
{
int nodeno; /*图中结点的编号 */
struct GRAPHLISTNODE_STRU* next; /*指向下一个结点的指针 */
}GraphListNode;
typedef struct GRAPHLIST_STRU
{
int size; /* 图中结点的个数 */
GraphListNode* graphListArray; /*图的邻接表 */
}GraphList;
GraphList* InitGraph(int num)
{
int i;
GraphList *graphList = (GraphList *)malloc(sizeof(GraphList));
graphList->size = num;
graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode)*num);
for (i = 0; i
graphList->graphListArray[i].next = NULL;
graphList->graphListArray[i].nodeno = i;
}
return graphList;
}
void ReadGraph(GraphList* graphList)
{
int vex1, vex2;
GraphListNode *tempNode = NULL;
/** 输入方式为点 点 ，点为-1，则输入结束 **/
scanf("%d %d", &vex1, &vex2);
while (vex1 >= 0 && vex2 >= 0)
{
tempNode = (GraphListNode*)malloc(sizeof(GraphListNode));
tempNode->nodeno = vex2;
//tempNode->next = NULL;
/**采用头插法**/
@@[tempNode->next = graphList->graphListArray[vex1].next](3);
@@[graphList->graphListArray[vex1].next = tempNode](3);
scanf("%d %d", &vex1, &vex2);
}
}
/*从节点i开始深度优先遍历*/
void DFS(GraphList* graphList, int * visited, int i)
{
int j;
GraphListNode *tempNode = NULL;
visited[i] = 1;
printf("%d ", i);
tempNode = graphList->graphListArray[i].next;
while (tempNode != NULL)
{
if (!visited[tempNode->nodeno])
@@[DFS(graphList, visited, tempNode->nodeno)](3);
@@[tempNode = tempNode->next](3);
}
}
/*图的深度优先遍历*/
void DFSGraphList(GraphList* graphList)
{
int i;
/* 用于记录图中哪些结点已经被访问了 */
int *visited = (int*)malloc(sizeof(int)* graphList->size);
/* 初始化为点都没有被访问 */
for (i = 0; i < graphList->size; i++)
visited[i] = 0;
for (i = 0; i < graphList->size; i++)
if (!visited[i])
DFS(graphList, visited, i);
}
int main()
{
GraphList *graphList = NULL;
graphList = InitGraph(6);
ReadGraph(graphList);
DFSGraphList(graphList);
return 0;
}
```
答案：
第1空：tempNode->next = graphList->graphListArray[vex1].next
第2空：graphList->graphListArray[vex1].next = tempNode
第3空：DFS(graphList, visited, tempNode->nodeno)
第4空：tempNode = tempNode->next
