24考研数据结构-图的基本操作_图的时间复杂度删除节点

6.6. 图的基本操作

无向图

有向图==（稀疏图也挺方便）==

1. Adjacent(G,x,y)边的存在

（无向边）<有向边>

• 思路：
  ①无向图：邻接矩阵，判断aij是否为1，邻接表，i点的邻接表是否有j点；
  ②有向图类似

• 时间复杂度
  

2. Neighbors(G,x):列出图G中与结点x邻接的边

• 思路：
  ①无向图：邻接矩阵，罗列出x点的行为1的所有点，邻接表，遍历x的链表的所有结点；
  ②有向图：邻接矩阵，出边遍历行，入边遍历列，邻接表，(出边)遍历x的链表，(入边)遍历所有的结点查看哪个结点值是x。
• 时间复杂度
  

3. InsertVertex(G,x):在图G中插入顶点x

• 思路：
  ① 无向图：邻接矩阵，给矩阵增加一个x行增加一个x列；邻接表，给表的最后一行增加x项，不接任何一个结点，指向NULL。
  ② 有向图：类似
• 时间复杂度
  

4. DeleteVertex(G,x):从图G中删除顶点x

• 思路：
  ① 无向图：邻接矩阵，将x的所有行列全部清空为-1，在顶点集中x的值表示为-1或false；邻接表，将所有与x有关的信息删除，需要遍历所有的结点。
  ② 有向图：邻接矩阵，与无向图类似，邻接表，删出边需要将x的链表都删除，删入边，需要遍历所有的结点。
• 时间复杂度
  

5. AddEdge(G,x,y):若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边。

• 思路：
  ① 无向图，邻接矩阵，将axy的值由0改为1=，邻接表，将x的链表后或前加上结点y==，最好使用头插法。
  ② 有向图，类似。
• 时间复杂度

6. FirstNeighbor(G,x):求图G中顶点的第一个邻接点

• 思路
  ① 无向图：邻接矩阵，扫描x的一行第一个为1的元素，可能第一个就是也可能到最后一个都没有；邻接表，查看x链表的第一个结点。
  ② 有向图：邻接矩阵，找x有关的行列（出边入边），也就是出边入边的第一个邻接点，邻接表，出边寻找简单，但是入边需要遍历所有的边。
• 时间复杂度
  

7. NextNeighbor(G,x,y):

假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

8. get_edge_value,set

其他操作总结

图是一种重要的数据结构，用于表示不同对象之间的关系。图由节点（也称为顶点）和边组成，节点表示对象，边表示对象之间的连接关系。图的基础操作包括节点的添加、删除，边的添加、删除，以及图的遍历等。

1. 添加节点（顶点）

向图中添加一个新节点（顶点）。节点的添加是一个简单的操作，只需要将新节点添加到节点集合中即可。

适合处理的数据：图适合处理对象之间具有关系的数据，例如社交网络中的用户和用户之间的关注关系，地图中的城市和城市之间的道路连接等。

时间复杂度：添加节点的时间复杂度为O(1)，因为只需在节点集合中添加一个节点。

代码示例：

class Graph:
    def __init__(self):
        self.nodes = set()
    
    def add_node(self, node):
        self.nodes.add(node)
1
2
3
4
5
6

2. 删除节点（顶点）

从图中删除一个节点。删除节点时，需要同时删除与该节点相关联的所有边。

适合处理的数据：图适合处理对象之间具有关系的数据，删除节点可能涉及删除一些关联的边，例如社交网络中删除一个用户可能涉及删除其与其他用户的关注关系。

时间复杂度：删除节点的时间复杂度取决于与该节点相关联的边的数量，假设为O(E)，其中E为边的数量。

代码示例：

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
    
    def add_node(self, node):
        self.nodes.add(node)
    
    def remove_node(self, node):
        if node in self.nodes:
            self.nodes.remove(node)
            if node in self.edges:
                del self.edges[node]
            for key in self.edges:
                if node in self.edges[key]:
                    self.edges[key].remove(node)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 添加边

向图中添加一条边，将两个节点之间建立连接。边可以是有向的（箭头指向一个方向）或无向的（没有箭头，表示双向连接）。

适合处理的数据：图适合处理对象之间具有关系的数据，添加边可以表示对象之间的连接关系，例如社交网络中用户之间的关注关系。

时间复杂度：添加边的时间复杂度为O(1)，因为只需要在边集合中添加一条边。

代码示例：

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
    
    def add_node(self, node):
        self.nodes.add(node)
    
    def add_edge(self, node1, node2):
        if node1 not in self.edges:
            self.edges[node1] = set()
        self.edges[node1].add(node2)
1
2
3
4
5
6
7
8
9
10
11
12

4. 删除边

从图中删除一条边，断开两个节点之间的连接。

适合处理的数据：图适合处理对象之间具有关系的数据，删除边可以断开对象之间的连接关系，例如社交网络中取消用户之间的关注关系。

时间复杂度：删除边的时间复杂度为O(1)，因为只需要在边集合中删除一条边。

代码示例：

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
    
    def add_node(self, node):
        self.nodes.add(node)
    
    def add_edge(self, node1, node2):
        if node1 not in self.edges:
            self.edges[node1] = set()
        self.edges[node1].add(node2)
    
    def remove_edge(self, node1, node2):
        if node1 in self.edges and node2 in self.edges[node1]:
            self.edges[node1].remove(node2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

图的遍历

图的遍历是一种查看图中所有节点和边的方法。常见的图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

DFS是一种递归的遍历算法，它从图中的某个节点开始，递归地访问该节点的所有邻居节点，然后再递归地访问邻居节点的邻居节点，依此类推。DFS能够遍历图中的所有节点和边，但是可能会陷入死循环，因此需要设置一个访问标记来避免重复访问。

时间复杂度：DFS的时间复杂度取决于图的大小，假设为O(V+E)，其中V为节点数量，E为边数量。

代码示例：

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
    
    def add_node(self, node):
        self.nodes.add(node)
    
    def add_edge(self, node1, node2):
        if node1 not in self.edges:
            self.edges[node1] = set()
        self.edges[node1].add(node2)
    
    def dfs(self, node, visited):
        if node not in visited:
            visited.add(node)
            print(node)
            if node in self.edges:
                for neighbor in self.edges[node]:
                    self.dfs(neighbor, visited)
    
    def depth_first_search(self):
        visited = set()
        for node in self.nodes:
            self.dfs(node, visited)
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

广度优先搜索（BFS）

BFS是一种使用队列的遍历算法，它从图中的某个节点开始，依次访问该节点的所有邻居节点，然后将邻

居节点入队，再依次访问队列中的节点的邻居节点，依此类推。BFS能够遍历图中的所有节点和边，且不会陷入死循环。

时间复杂度：BFS的时间复杂度取决于图的大小，假设为O(V+E)，其中V为节点数量，E为边数量。

代码示例：

from collections import deque

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}
    
    def add_node(self, node):
        self.nodes.add(node)
    
    def add_edge(self, node1, node2):
        if node1 not in self.edges:
            self.edges[node1] = set()
        self.edges[node1].add(node2)
    
    def breadth_first_search(self, start):
        visited = set()
        queue = deque([start])
        while queue:
            node = queue.popleft()
            if node not in visited:
                visited.add(node)
                print(node)
                if node in self.edges:
                    queue.extend(self.edges[node])
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

时间与空间复杂度

• 添加节点：时间复杂度为O(1)，空间复杂度为O(1)。
• 删除节点：时间复杂度为O(E)，空间复杂度为O(1)。
• 添加边：时间复杂度为O(1)，空间复杂度为O(1)。
• 删除边：时间复杂度为O(1)，空间复杂度为O(1)。
• 图的遍历（DFS和BFS）：时间复杂度为O(V+E)，空间复杂度为O(V)。

图是一种非常重要的数据结构，在实际应用中有着广泛的应用。通过合理选择数据结构和算法，可以高效地处理图中的数据，实现各种复杂的操作。无论是在社交网络、地图导航还是其他领域，图的基础操作都是构建更高级功能的关键。