1．采用图的数组表示法（邻接矩阵）将教材p157的图6.1中的无向图g2用计算机表示出来，并对其实现深度优先搜索。\n\n2．适当修改上述程序，使它适用于g1图（有向图），输入数据运行程序。\n\n提示：无向

这道题的要求是使用图的数组表示法（邻接矩阵）将教材P157中的图6.1中的无向图g2用计算机表示出来，并对其实现深度优先搜索。

1. 首先需要将图6.1中的g2用邻接矩阵表示出来，可以用一个二维数组来表示。将图中的节点编号从1开始，建立一个size大小为4的二维数组，其中g2[1][2] = g2[2][1] = 1, g2[1][3] = g2[3][1] = 1, g2[3][4] = g2[4][3] = 1, 表示节点1和2，节点1和3，节点3和4之间都有边连接。

2. 对于深度优先搜索的实现，可以采用递归方式实现。从图中的某个节点v开始，首先将v标记为已访问，并输出v。然后对于v的每一个未被访问的邻居u，递归调用深度优先搜索函数，继续访问u。在此过程中，需要保证对于每个节点u只访问一次，以避免出现死循环。

提示：无向图不是有向图，无向图中的任意两点之间的边都是双向的。

相关问题

无向图的邻接矩阵（数组表示法）

邻接矩阵是一种用于表示图的数据结构，适用于无向图和有向图。对于无向图，邻接矩阵是一个对称矩阵。

在邻接矩阵中，每个节点都对应矩阵中的一行和一列，如果两个节点之间有边相连，则相应的矩阵元素为1，否则为0。如果图中有权重，则可以将矩阵元素设置为它们之间的边权值。

以下是一个用数组表示法实现无向图邻接矩阵的示例代码：

#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct{
    int vertex[MAX_VERTEX_NUM]; //顶点数组
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵数组
    int vertex_num, arc_num; //顶点数和边数
}Graph;

Graph create_graph(int vertex_num, int arc_num){
    Graph g;
    g.vertex_num = vertex_num;
    g.arc_num = arc_num;
    for(int i=0; i<vertex_num; i++){
        g.vertex[i] = i; //初始化顶点数组
    }
    for(int i=0; i<vertex_num; i++){
        for(int j=0; j<vertex_num; j++){
            g.arc[i][j] = 0; //初始化邻接矩阵数组
        }
    }
    for(int k=0; k<arc_num; k++){
        int i, j;
        scanf("%d%d", &i, &j);
        g.arc[i][j] = 1; //无向图邻接矩阵设置
        g.arc[j][i] = 1; //无向图邻接矩阵设置
    }
    return g;
}

在上述代码中，create_graph函数用于创建无向图邻接矩阵。首先初始化顶点数组和邻接矩阵数组，然后按照输入的边数设置邻接矩阵数组中的元素。最后返回创建好的图结构体。

1. 建立无向图的邻接矩阵存储并输出。2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。

1. 建立无向图的邻接矩阵存储并输出：

邻接矩阵是一种常用的图的存储方式，可以用一个二维数组来表示图中各个节点之间的关系。对于无向图，邻接矩阵是一个对称矩阵，即矩阵中的第i行第j列和第j行第i列都表示节点i和节点j之间是否有边相连。

下面是一个无向图的邻接矩阵示例：

   1  2  3  4  5
1  0  1  1  0  0
2  1  0  1  1  0
3  1  1  0  0  1
4  0  1  0  0  1
5  0  0  1  1  0

其中，矩阵中的每个元素表示两个节点之间的边是否存在，1表示存在，0表示不存在。

2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历：

邻接表是另一种常用的图的存储方式，它将每个节点的所有邻居节点都存储在一个链表中。对于无向图，每个节点的邻居节点都是双向的，因此邻接表中需要存储两个方向的链表。

下面是一个无向图的邻接表示例：

1 -> 2 -> 3
2 -> 1 -> 3 -> 4
3 -> 1 -> 2 -> 5
4 -> 2 -> 5
5 -> 3 -> 4

其中，每个节点后面的箭头表示该节点的邻居节点。

在邻接表的基础上，可以实现图的深度优先遍历和广度优先遍历。深度优先遍历是一种递归的方式，从起点节点开始，先访问它的一个邻居节点，然后再递归访问该邻居节点的邻居节点，直到所有节点都被访问过。广度优先遍历则是一种迭代的方式，从起点节点开始，先访问它的所有邻居节点，然后再依次访问它们的邻居节点，直到所有节点都被访问过。