图的邻接表表示法及遍历

邻接表是一种图的表示方法，由一个由顶点列表和每个顶点对应的邻接点列表组成。

具体地，每个顶点对应一个链表，链表中存储该顶点所连接的所有顶点。例如，下面是一个无向图的邻接表表示。

0: 1->2
1: 0->2->3
2: 0->1->3
3: 1->2

表示图中有4个顶点，编号分别为0、1、2、3。顶点0连接顶点1和2，顶点1连接顶点0、2和3，以此类推。

遍历图的方式有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。

DFS从某个顶点开始，一直沿着一条路径访问下去，直到走到不能再走为止，然后回溯到前一个节点，再沿着另一条路径继续访问，直到所有节点都被访问为止。具体实现可以使用递归或栈来实现。

BFS从某个顶点开始，先访问该顶点的所有邻接顶点，然后访问这些邻接顶点的邻接顶点，依次类推，直到所有节点都被访问为止。具体实现可以使用队列来实现。

相关问题

图的邻接表表示法及遍历C语言实现

邻接表是一种图的表示方法，它以每个节点为基础，对每个节点的相邻节点进行链式存储。邻接表由一个数组和一个链表组成，数组中每个元素对应一个节点，链表中则存储与该节点相邻的节点。以下是邻接表的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 边表结构体
typedef struct ArcNode {
    int adjvex;              // 邻接点下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结构体
typedef struct {
    int data;       // 顶点信息
    ArcNode *first; // 指向第一个邻接点的指针
} VNode;

// 图结构体
typedef struct {
    VNode vertex[MAX_VERTEX_NUM]; // 顶点表
    int vexnum;                   // 顶点数
    int arcnum;                   // 边数
} ALGraph;

// 遍历图
void DFS(ALGraph *G, int v, int *visited) {
    printf("%d ", G->vertex[v].data);
    visited[v] = 1;  // 标记当前节点已被访问
    ArcNode *p = G->vertex[v].first;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {
            DFS(G, p->adjvex, visited);
        }
        p = p->nextarc;
    }
}

// 创建图
void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第 %d 个顶点信息：", i + 1);
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].first = NULL;
    }
    for (int i = 0; i < G->arcnum; i++) {
        printf("请输入第 %d 条边的起点和终点：", i + 1);
        int start, end;
        scanf("%d %d", &start, &end);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = end - 1;
        p->nextarc = G->vertex[start - 1].first;
        G->vertex[start - 1].first = p;
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    int visited[MAX_VERTEX_NUM] = {0};  // 记录节点是否被访问过的数组
    printf("DFS遍历结果为：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(&G, i, visited);
        }
    }
    return 0;
}

在上面的代码中，我们定义了两个结构体，分别是顶点表结构体和边表结构体。创建图时，我们先输入顶点数和边数，然后依次输入每个顶点的信息，再输入每条边的起点和终点，将边加入到邻接表中。遍历图时，我们使用DFS算法进行遍历，从每个未被访问过的节点开始递归遍历其相邻节点。

图的邻接表表示法及遍历代码实现

邻接表是一种表示图的数据结构，它将每个顶点与其相邻的顶点列表联系起来。邻接表通常用于表示稀疏图，因为它可以节省存储空间。下面是邻接表的实现方式：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

在这个实现中，我们创建了一个大小为`num_vertices`的空列表，用于存储每个顶点的邻居。`add_edge`方法用于将两个顶点之间的边添加到邻接表中。

接下来，我们来看一下如何遍历一个图。遍历图有两种基本方法：深度优先搜索（DFS）和广度优先搜索（BFS）。这里我们提供DFS的实现方式：

def dfs(self, start):
    visited = [False] * self.num_vertices
    self._dfs(start, visited)

def _dfs(self, curr, visited):
    visited[curr] = True
    print(curr, end=' ')
    for neighbor in self.adj_list[curr]:
        if not visited[neighbor]:
            self._dfs(neighbor, visited)

在这个实现中，我们使用了一个辅助函数`_dfs`来进行递归调用。我们首先将当前顶点标记为已访问，并将其打印出来。然后，我们遍历该顶点的所有邻居，如果邻居未被访问，则递归调用`_dfs`函数。

以下是一个完整的示例：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)
    
    def dfs(self, start):
        visited = [False] * self.num_vertices
        self._dfs(start, visited)

    def _dfs(self, curr, visited):
        visited[curr] = True
        print(curr, end=' ')
        for neighbor in self.adj_list[curr]:
            if not visited[neighbor]:
                self._dfs(neighbor, visited)

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

g.dfs(0)  # 输出: 0 1 2 3 4

在这个例子中，我们创建了一个大小为5的图，并添加了一些边。然后我们从顶点0开始进行DFS遍历，输出结果为`0 1 2 3 4`。