3.在上述例题中，如改用邻接表的方式存储图，试编一程序实现上述算法。 顶点表nodelist的每个元素包含四个字段： infomarkpreout 其中mark为布尔类型，用来标记顶点是否被访问过。开始时，所有元素的mark字段为false，每访问过一个顶点，则mark字段置为true。info为顶点值，pre为访问路径上该顶点的前驱顶点的序号，out指向该顶点的出边表。

### 回答1：
题目中要求修改用邻接表存储图的方式，然后实现一个算法。顶点表nodelist的每个元素包含四个字段：infomarkpreout，其中mark为布尔类型，用来标记顶点是否被访问过。开始时，所有元素的mark字段都为false。每访问一个顶点，就将其对应的mark字段置为true。info为顶点值，pre为访问该顶点的前驱顶点在路径上的序号，out指向以该顶点为起点的第一条边在边集数组中的序号。

题目给定的其中一个元素的infomarkpreout中mark为布尔类型，用来标记布尔类型，用来标记顶点是否被访问过，其中mark为布尔类型，用来标记顶点是否被访问过。如果开始时，元素的mark字段为false，则每访问过一个顶点，就将其对应的mark字段置为true。如果某个顶点的mark字段为true，则说明该顶点已被访问过。info为顶点值，pre为访问该顶点的前驱顶点在路径上的序号，out指向以该顶点为起点的第一条边在边集数组中的序号。顶点表中每个元素所包含的字段的含义如上所述。

算法实现时，先将起点的infomarkpreout的mark字段置为true，然后将起点作为当前顶点，并将其加入队列中。之后，对于队列中每个顶点的每一个邻接点，先检查邻接点的mark字段是否为false，如果为false，则将其mark字段置为true，然后将邻接点加入队列中，并设置其pre字段和out字段。重复上述过程，直到队列为空，或者找到终点为止。如果队列为空，说明没有从起点找到终点；如果找到了终点，就可以通过倒序遍历每个顶点的pre字段，即可求得从起点到终点的路径。路径上的每个顶点的out字段就是该顶点在路径上的下一个邻接点在邻接表中的位置。

### 回答2：
邻接表是一种常用的图的存储方式，可以用较小的空间存储大型图。邻接表由顶点表和边表组成，其中顶点表存储顶点的信息，边表包含每个顶点的出边。在深度优先搜索算法中，使用邻接表可以较方便地实现该算法。

对于给定的图G=(V,E)，我们可以定义邻接表Adj为长度为|V|的数组，其中每个元素adj[i]（0≤i<|V|）是一个链表，用于存储顶点i的出边。链表中的每个节点表示一条边，其包含两个字段：邻接顶点w和边的权值（如果有的话）。如果顶点i没有出边，则链表为空。

维护顶点信息的数据结构是顶点表，每个节点包含四个字段：信息（info）、前驱（pre）、是否被访问（mark）、出边（out）。其中，信息info指定了该顶点的值，前驱pre表示访问路径上该顶点的前驱顶点的序号，mark是布尔类型，用来标记顶点是否被访问过，out是指向该顶点的出边表。

深度优先搜索算法的核心是递归函数，函数名为DFS，算法流程如下：

（1）首先将起点v0压入栈中，将其mark字段置为true，然后输出v0。

（2）从v0的出边表中找到一个未访问过的顶点v，在v的节点中将mark字段置为true，并将v压入栈中。

（3）重复步骤2，直到找不到未访问的顶点，此时需要退出递归函数。

（4）退栈，出栈的顶点作为当前顶点v，重复步骤2和步骤3，直到栈为空，算法结束。

代码如下：

#define MAX_VERTICES 100
 
typedef struct EdgeNode{  
    int adjvex;  
    struct EdgeNode *next;  
} EdgeNode;  
  
typedef struct VertexNode{  
    int info; //顶点信息  
    bool mark; //是否被访问  
    int pre; //前驱节点  
    EdgeNode *out; //出边表头指针  
} VertexNode;  
  
typedef struct{  
    VertexNode vertex[MAX_VERTICES];  
    int n; //顶点数  
} GraphAdjList;  
  
void DFS(GraphAdjList G, int v)  
{  
    printf("%d ", G.vertex[v].info);  
    G.vertex[v].mark = true;  
    EdgeNode *p = G.vertex[v].out;  
    while (p != NULL){  
        int w = p->adjvex;  
        if (!G.vertex[w].mark){  
            G.vertex[w].pre = v;  
            DFS(G, w);  
        }  
        p = p->next;  
    }  
}  
  
int main()  
{  
    GraphAdjList G;  
    int i, j, k;  
    printf("请输入顶点数：");  
    scanf("%d", &G.n);  
    for (i = 0; i < G.n; ++i){  
        printf("请输入第%d个顶点值：", i+1);  
        scanf("%d", &G.vertex[i].info);  
        G.vertex[i].mark = false;  
        G.vertex[i].pre = -1;  
        G.vertex[i].out = NULL;  
    }  
  
    printf("请输入边数：");  
    scanf("%d", &k);  
    for (i = 0; i < k; ++i){  
        int u, v;  
        printf("请输入第%d条边的顶点序号：", i+1);  
        scanf("%d%d", &u, &v);  
        if (u >= G.n || v >= G.n){  
            printf("无效边\n");  
            --i;  
            continue;  
        }  
        EdgeNode *p = (EdgeNode*)malloc(sizeof(EdgeNode));  
        p->adjvex = v;  
        p->next = G.vertex[u].out;  
        G.vertex[u].out = p;  
    }  
  
    printf("深度优先搜索终点序号：");  
    int v0;  
    scanf("%d", &v0);  
    DFS(G, v0);  
  
    return 0;  
}  

使用邻接表存储图的深度优先搜索算法是非常简单的，其时间复杂度为O(V+E)，其中V和E分别是顶点数和边数，空间复杂度为O(V+E)。相比之下，使用邻接矩阵存储图的深度优先搜索算法的时间复杂度为O(V^2)，空间复杂度为O(V^2)。因此，在大型图上使用邻接表存储是更为合适的选择。

### 回答3：
邻接表是一种存储图的方式，它将每个顶点的所有邻接点都列出来，并且将它们用一个链表连接起来。在邻接表中，每个顶点都与一条链表相关联，该链表包含该顶点所连接的所有顶点。

在使用邻接表存储图的情况下，我们需要对上述算法进行一些修改。通过遍历邻接表的方法，我们可以找到每个顶点所连接的所有顶点。在这个过程中，我们需要使用一个辅助队列来存储还未被遍历的顶点。

接下来，我们可以使用类似于BFS的算法来遍历所有顶点。我们从起始顶点开始，将其标记为已访问，并将其入队。然后，我们从队列中取出下一个顶点，并遍历其所有连接的顶点。对于每个未被访问的顶点，我们将其标记为已访问，并将其入队。我们还需要记录每个顶点的前驱节点，以便最后构建路径。

最后，我们可以遍历每个顶点的前驱节点，以生成从起始顶点到每个顶点的路径。这些路径可以被输出为最短路径算法的结果。

以下是一个使用邻接表实现最短路径算法的伪代码：

1. 初始化所有顶点的mark字段为false
2. 初始化所有顶点的pre字段为-1
3. 将起点v入队
4. 设置v的mark字段为true
5. while队列不为空
1. 取出队头元素u
2. 遍历顶点u的所有连接点v
1. 如果v未被访问过
1. 将v的mark字段设为true
2. 将v的pre字段设为u
3. 将v入队
6. 输出最短路径

在代码实现过程中，我们可以使用一个数组来存储每个顶点的信息。我们还需要一个链表来存储每个顶点的连接点。

以下是一个使用邻接表实现最短路径算法的示例代码：