链接表存储图(C++注释详解): 构建表 & 深度优先遍历 (DFS)

链接表的结构体单元:

#define size 100
typedef struct node {
    int idx;//下一个节点的索引
    int wt;//权重, 也可根据实际情景存储边的信息
    struct node* next;
}Node;
Node* hd[size]; // 存储图的邻接表

链接表的的构建:

int main()
{
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < n; i++) hd[i] = NULL; // 初始化邻接表为空
    int u, v, wt;//从u到v有一条权值为wt的有向线段
    for(int i = 0; i < m; i++) // 输入边的信息
    {
        cin >> u >> v >> wt;
        Node* t_node = (Node*)malloc(sizeof(Node)); // 创建新节点
        t_node->idx = v; // 设置新节点的索引
        t_node->wt = wt; // 设置新节点的权重
        if (hd[u] == NULL) // 如果之前还没有建立节点
        {
            t_node->next = NULL;
            hd[u] = t_node; // 将新节点设置为邻接表头节点
        }
        else
        {
            t_node->next = hd[u]->next;
            hd[u]->next = t_node; // 将新节点加入邻接表
        }
    }
}

深度(DFS)优先遍历函数

void DFS(int st)
{
    Node* t_node = hd[st]; // 获取起始节点的邻接表头指针
    for (; t_node; t_node = t_node->next) // 遍历邻接表中的节点
    {
        int u = t_node->idx; // 获取相邻节点的索引
        if (!visited[u]) // 如果相邻节点未被访问过
        {
            cout << u << " "; // 输出相邻节点的索引
            visited[u] = true; // 标记相邻节点为已访问
            DFS(u); // 递归访问相邻节点
        }
    }
}

总体代码实现:

#include<bits/stdc++.h>
using namespace std;
#define size 100
 
typedef struct node {
    int idx;//下一个节点的索引
    int wt;//权重, 也可根据实际情景存储边的信息
    struct node* next;
}Node;
Node* hd[size]; // 存储图的邻接表
bool visited[size]; // 标记节点是否被访问过
 
void DFS(int st)
{
    Node* t_node = hd[st]; // 获取起始节点的邻接表头指针
    for (; t_node; t_node = t_node->next) // 遍历邻接表中的节点
    {
        int u = t_node->idx; // 获取相邻节点的索引
        if (!visited[u]) // 如果相邻节点未被访问过
        {
            cout << u << " "; // 输出相邻节点的索引
            visited[u] = true; // 标记相邻节点为已访问
            DFS(u); // 递归访问相邻节点
        }
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < n; i++) hd[i] = NULL; // 初始化邻接表为空
    int u, v, wt;
    for(int i = 0; i < m; i++) // 输入边的信息
    {
        cin >> u >> v >> wt;
        Node* t_node = (Node*)malloc(sizeof(Node)); // 创建新节点
        t_node->idx = v; // 设置新节点的索引
        t_node->wt = wt; // 设置新节点的权重
        if (hd[u] == NULL) // 如果之前还没有建立节点
        {
            t_node->next = NULL;
            hd[u] = t_node; // 将新节点设置为邻接表头节点
        }
        else
        {
            t_node->next = hd[u]->next;
            hd[u]->next = t_node; // 将新节点加入邻接表
        }
    }
     // 输入开始节点
    int st;
    cin >> st;
    // 深度优先搜索
    for (int i = 0; i < size; i++)    visited[i] = false; // 初始化visited数组为false
    cout << st << " ";
    visited[st] = true;
    DFS(st);
}

测试数据:

/*
测试数据:
5 6
1 2 4
2 5 10
1 3 5
3 2 1
3 4 2
4 5 6
*/

上述数据对应图例:

~希望对你有帮助~