无向图

无向图是一种图，其中边没有方向。在无向图中，如果存在一条从节点A到节点B的边，那么也存在一条从节点B到节点A的边。

文章目录

无向图的基本概念

顶点（Vertices） ：图中的基本单元，通常用字母表示。
边（Edges） ：连接两个顶点的线段，表示两个顶点之间的关系。在无向图中，边没有方向性。
度（Degree） ：一个顶点所连接的边的数量。

无向图的表示方法

邻接矩阵（Adjacency Matrix） ：
- 使用二维数组来表示图，其中matrix[i][j] = 1表示存在一条从节点i到节点j的边，否则为0。
- 时间复杂度：查找操作为O(1)，插入和删除操作为O(V^2)，其中V是顶点的数量。
```
# 示例：邻接矩阵表示无向图
graph_matrix = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
]
```
邻接表（Adjacency List） ：
- 使用一个列表来存储每个顶点的邻居。通常使用字典或哈希表实现。
- 时间复杂度：查找操作为O(V + E)，插入和删除操作为O(1)（平均情况下），其中E是边的数量。
```
# 示例：邻接表表示无向图
graph_list = {
    0: [1],
    1: [0, 2],
    2: [1]
}
```

常见的无向图操作

添加顶点：
- 在邻接矩阵中，增加一行和一列。
- 在邻接表中，增加一个新的键值对。
添加边：
- 在邻接矩阵中，将相应的两个位置设置为1。
- 在邻接表中，在两个节点的邻居列表中添加对方。
删除顶点：
- 在邻接矩阵中，删除对应的行和列，并更新其他行和列的值。
- 在邻接表中，删除键值对，并从其他顶点的邻居列表中移除该顶点。
删除边：
- 在邻接矩阵中，将相应的两个位置设置为0。
- 在邻接表中，在两个节点的邻居列表中移除对方。

无向图的应用场景

社交网络：朋友关系可以用无向图表示，其中顶点是用户，边表示友谊。
地图导航：城市和道路可以建模为无向图，用于路径规划。
化学分子结构：原子和化学键可以用无向图表示。

无向图的遍历

深度优先搜索（DFS） ：
- 从一个起始顶点开始，尽可能深地探索每个分支，直到不能再深入为止，然后回溯。
- 常用方法：递归或栈实现。
广度优先搜索（BFS） ：
- 从一个起始顶点开始，逐层探索邻居节点，通常使用队列来实现。
- 常用于最短路径和连通性检查。

示例代码：无向图的DFS和BFS

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs_util(self, v, visited):
        visited[v] = True
        print(v, end=" ")
        for i in self.graph[v]:
            if not visited[i]:
                self.dfs_util(i, visited)

    def dfs(self, v):
        visited = [False] * self.V
        self.dfs_util(v, visited)

    def bfs(self, s):
        visited = [False] * self.V
        queue = deque()
        queue.append(s)
        visited[s] = True

        while queue:
            s = queue.popleft()
            print(s, end=" ")
            for i in self.graph[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True

# 示例使用
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)

print("DFS starting from vertex 2:")
g.dfs(2)

print("\nBFS starting from vertex 2:")
g.bfs(2)

深度优先遍历

通过递归和非递归（使用栈）两种方式来实现无向图的深度优先搜索（DFS）

1. 递归实现

递归实现是最直观的方法，通过函数调用的栈来模拟递归的过程。

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

#define MAX_VERTICES 100

// 图的邻接表节点结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 邻接表结构
typedef struct AdjList {
    AdjListNode* head;  // 指向第一个邻居的指针
} AdjList;

// 图的结构
typedef struct Graph {
    int V;
    AdjList* array;
};

// 创建一个新的邻接表节点
AdjListNode* new_adjlist_node(int dest) {
    AdjListNode* node = (AdjListNode*)malloc(sizeof(AdjListNode));
    node->dest = dest;
    node->next = NULL;
    return node;
}

// 创建一个包含V个顶点的图
Graph* create_graph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    // 为每个顶点创建邻接表
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 向图中添加无向边
void add_edge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    AdjListNode* node = new_adjlist_node(dest);
    node->next = graph->array[src].head;
    graph->array[src].head = node;

    // 添加从dest到src的边（无向图）
    node = new_adjlist_node(src);
    node->next = graph->array[dest].head;
    graph->array[dest].head = node;
}

// 递归实现DFS
void dfs_util(Graph* graph, int v, int visited[]) {
    // 标记当前顶点为已访问
    visited[v] = 1;
    printf("%d ", v);

    // 递归访问所有相邻的未访问顶点
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        if (!visited[pCrawl->dest]) {
            dfs_util(graph, pCrawl->dest, visited);
        }
        pCrawl = pCrawl->next;
    }
}

// 执行DFS，从顶点v开始
void dfs(Graph* graph, int v) {
    // 访问标记数组
    int visited[MAX_VERTICES] = {0};
    dfs_util(graph, v, visited);
}

int main() {
    Graph* graph = create_graph(5);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 2);
    add_edge(graph, 1, 3);
    add_edge(graph, 1, 4);

    printf("DFS starting from vertex 0:\n");
    dfs(graph, 0);

    return 0;
}

2. 非递归实现（使用栈）

非递归实现通过显式地使用栈来模拟递归过程，避免了函数调用的开销。

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

#define MAX_VERTICES 100

// 图的邻接表节点结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 邻接表结构
typedef struct AdjList {
    AdjListNode* head;  // 指向第一个邻居的指针
} AdjList;

// 图的结构
typedef struct Graph {
    int V;
    AdjList* array;
};

// 创建一个新的邻接表节点
AdjListNode* new_adjlist_node(int dest) {
    AdjListNode* node = (AdjListNode*)malloc(sizeof(AdjListNode));
    node->dest = dest;
    node->next = NULL;
    return node;
}

// 创建一个包含V个顶点的图
Graph* create_graph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    // 为每个顶点创建邻接表
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 向图中添加无向边
void add_edge(Graph* graph, int src, int dest) {
    // 添加从src到dest的边
    AdjListNode* node = new_adjlist_node(dest);
    node->next = graph->array[src].head;
    graph->array[src].head = node;

    // 添加从dest到src的边（无向图）
    node = new_adjlist_node(src);
    node->next = graph->array[dest].head;
    graph->array[dest].head = node;
}

// 执行DFS，从顶点v开始
void dfs_non_recursive(Graph* graph, int v) {
    // 访问标记数组
    int visited[MAX_VERTICES] = {0};
    // 使用栈来模拟递归
    int stack[MAX_VERTICES];
    int top = -1;

    // 将起始顶点入栈
    stack[++top] = v;
    visited[v] = 1;

    while (top >= 0) {
        // 弹出栈顶元素并打印
        int current = stack[top--];
        printf("%d ", current);

        // 遍历当前顶点的所有相邻顶点
        AdjListNode* pCrawl = graph->array[current].head;
        while (pCrawl) {
            if (!visited[pCrawl->dest]) {
                visited[pCrawl->dest] = 1;
                stack[++top] = pCrawl->dest;
            }
            pCrawl = pCrawl->next;
        }
    }
}

int main() {
    Graph* graph = create_graph(5);
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 2);
    add_edge(graph, 1, 3);
    add_edge(graph, 1, 4);

    printf("DFS starting from vertex 0:\n");
    dfs_non_recursive(graph, 0);

    return 0;
}

广度优先遍历

广度优先搜索（BFS）是一种用于图的遍历算法，它从起始顶点开始，逐层探索邻居节点，并使用队列来实现。下面是一个用C语言实现的无向图的BFS示例：

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

#define MAX_VERTICES 100

// 邻接表节点结构体
struct Node {
    int vertex;
    struct Node* next;
};

// 图结构体
struct Graph {
    int numVertices;
    struct Node** adjLists;
    int* visited;
};

// 创建新节点
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    // 为每个顶点分配邻接表
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; ++i)
        graph->adjLists[i] = NULL;

    // 初始化访问数组
    graph->visited = (int*)malloc(vertices * sizeof(int));
    for (int i = 0; i < vertices; ++i)
        graph->visited[i] = 0;

    return graph;
}

// 添加边到图中
void addEdge(struct Graph* graph, int src, int dest) {
    // 在src的邻接表中添加dest节点
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 由于是无向图，所以在dest的邻接表中也添加src节点
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 广度优先搜索函数
void bfs(struct Graph* graph, int startVertex) {
    struct Node* temp;
    int queue[MAX_VERTICES], front = -1, rear = -1;

    // 初始化队列并将起始顶点入队
    queue[++rear] = startVertex;
    graph->visited[startVertex] = 1;

    while (front != rear) {
        front++;
        temp = graph->adjLists[queue[front]];

        printf("Visited %d\n", queue[front]);

        // 访问所有邻接顶点
        while (temp) {
            int adjVertex = temp->vertex;
            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = 1;
                queue[++rear] = adjVertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    struct Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);

    printf("BFS starting from vertex 2:\n");
    bfs(graph, 2);

    return 0;
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30