无向图是一种边没有方向的图结构,图中的边表示两个顶点之间的双向连接。无向图广泛应用于社交网络、地图导航、电路设计等场景。
无向图(Undirected Graph)是图论中最基础的图结构之一,其中的边没有方向性,表示节点之间的双向连接关系。在无向图中,如果顶点A和顶点B之间有一条边,那么可以从A到达B,也可以从B到达A。这种对称的连接关系使无向图成为表示许多现实世界中双向关系的理想模型。
无向图中的关键概念包括:
出于篇幅考虑,Java之外的语言实现删掉了遍历方法,需要的小伙伴可以参考Java实现自行补充。
▼Java复制代码import java.util.*; // 无向图的边表示 class UndirectedEdge { int vertex1; // 边的一个顶点 int vertex2; // 边的另一个顶点 public UndirectedEdge(int vertex1, int vertex2) { this.vertex1 = vertex1; this.vertex2 = vertex2; } @Override public String toString() { return vertex1 + " -- " + vertex2; } } // 带权重的无向边 class WeightedUndirectedEdge { int vertex1; // 边的一个顶点 int vertex2; // 边的另一个顶点 int weight; // 边的权重 public WeightedUndirectedEdge(int vertex1, int vertex2, int weight) { this.vertex1 = vertex1; this.vertex2 = vertex2; this.weight = weight; } @Override public String toString() { return vertex1 + " -- " + vertex2 + " (" + weight + ")"; } } // 使用边列表实现的无向图 class UndirectedGraph { private int V; // 顶点数量 private List<UndirectedEdge> edges; // 边列表 private Map<Integer, List<Integer>> adjacencyList; // 邻接表 public UndirectedGraph(int V) { this.V = V; this.edges = new ArrayList<>(); this.adjacencyList = new HashMap<>(); // 初始化顶点 for (int i = 0; i < V; i++) { adjacencyList.put(i, new ArrayList<>()); } } // 添加无向边 public void addEdge(int vertex1, int vertex2) { // 确保顶点有效 if (vertex1 < 0 || vertex1 >= V || vertex2 < 0 || vertex2 >= V) { throw new IllegalArgumentException("顶点索引无效"); } // 添加到边列表 edges.add(new UndirectedEdge(vertex1, vertex2)); // 更新邻接表(无向图需要双向添加) adjacencyList.get(vertex1).add(vertex2); adjacencyList.get(vertex2).add(vertex1); } // 获取图中的顶点数 public int getVertexCount() { return V; } // 获取图中的边数 public int getEdgeCount() { return edges.size(); } // 获取顶点的度 public int getDegree(int vertex) { validateVertex(vertex); return adjacencyList.get(vertex).size(); } // 获取与指定顶点相邻的所有顶点 public List<Integer> getNeighbors(int vertex) { validateVertex(vertex); return new ArrayList<>(adjacencyList.get(vertex)); } // 判断两个顶点之间是否存在边 public boolean hasEdge(int v1, int v2) { validateVertex(v1); validateVertex(v2); return adjacencyList.get(v1).contains(v2); } // 检查顶点是否有效 private void validateVertex(int v) { if (v < 0 || v >= V) { throw new IllegalArgumentException("顶点 " + v + " 不在有效范围内"); } } // 打印图的所有边 public void printEdges() { System.out.println("图中的所有无向边:"); for (UndirectedEdge edge : edges) { System.out.println(edge); } } // 使用BFS判断两个顶点之间是否存在路径(检查连通性) public boolean isConnected(int start, int end) { validateVertex(start); validateVertex(end); if (start == end) return true; boolean[] visited = new boolean[V]; Queue<Integer> queue = new LinkedList<>(); visited[start] = true; queue.offer(start); while (!queue.isEmpty()) { int current = queue.poll(); for (int neighbor : adjacencyList.get(current)) { if (neighbor == end) { return true; } if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return false; } // 使用DFS遍历图(从指定顶点开始) public void dfs(int start) { validateVertex(start); boolean[] visited = new boolean[V]; System.out.print("DFS遍历(从顶点" + start + "开始):"); dfsUtil(start, visited); System.out.println(); } private void dfsUtil(int vertex, boolean[] visited) { // 标记当前顶点为已访问并打印 visited[vertex] = true; System.out.print(vertex + " "); // 递归处理所有未访问的邻居 for (int neighbor : adjacencyList.get(vertex)) { if (!visited[neighbor]) { dfsUtil(neighbor, visited); } } } // 使用BFS遍历图(从指定顶点开始) public void bfs(int start) { validateVertex(start); boolean[] visited = new boolean[V]; Queue<Integer> queue = new LinkedList<>(); visited[start] = true; queue.offer(start); System.out.print("BFS遍历(从顶点" + start + "开始):"); while (!queue.isEmpty()) { int current = queue.poll(); System.out.print(current + " "); for (int neighbor : adjacencyList.get(current)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } System.out.println(); } // 计算图中的连通分量数量 public int countConnectedComponents() { boolean[] visited = new boolean[V]; int count = 0; for (int v = 0; v < V; v++) { if (!visited[v]) { // 对未访问的顶点执行DFS dfsForComponents(v, visited); count++; } } return count; } private void dfsForComponents(int vertex, boolean[] visited) { visited[vertex] = true; for (int neighbor : adjacencyList.get(vertex)) { if (!visited[neighbor]) { dfsForComponents(neighbor, visited); } } } }
▼Python复制代码class UndirectedEdge: """无向图的边表示""" def __init__(self, vertex1, vertex2): self.vertex1 = vertex1 # 边的一个顶点 self.vertex2 = vertex2 # 边的另一个顶点 def __str__(self): return f"{self.vertex1} -- {self.vertex2}" class WeightedUndirectedEdge: """带权重的无向边""" def __init__(self, vertex1, vertex2, weight): self.vertex1 = vertex1 # 边的一个顶点 self.vertex2 = vertex2 # 边的另一个顶点 self.weight = weight # 边的权重 def __str__(self): return f"{self.vertex1} -- {self.vertex2} ({self.weight})" class UndirectedGraph: """使用边列表实现的无向图""" def __init__(self, V): self.V = V # 顶点数量 self.edges = [] # 边列表 self.adjacency_list = {} # 邻接表 # 初始化顶点 for i in range(V): self.adjacency_list[i] = [] def add_edge(self, vertex1, vertex2): """添加无向边""" # 确保顶点有效 if vertex1 < 0 or vertex1 >= self.V or vertex2 < 0 or vertex2 >= self.V: raise ValueError("顶点索引无效") # 添加到边列表 self.edges.append(UndirectedEdge(vertex1, vertex2)) # 更新邻接表(无向图需要双向添加) self.adjacency_list[vertex1].append(vertex2) self.adjacency_list[vertex2].append(vertex1) def get_vertex_count(self): """获取图中的顶点数""" return self.V def get_edge_count(self): """获取图中的边数""" return len(self.edges) def get_degree(self, vertex): """获取顶点的度""" self._validate_vertex(vertex) return len(self.adjacency_list[vertex]) def get_neighbors(self, vertex): """获取与指定顶点相邻的所有顶点""" self._validate_vertex(vertex) return self.adjacency_list[vertex].copy() def has_edge(self, v1, v2): """判断两个顶点之间是否存在边""" self._validate_vertex(v1) self._validate_vertex(v2) return v2 in self.adjacency_list[v1] def _validate_vertex(self, v): """检查顶点是否有效""" if v < 0 or v >= self.V: raise ValueError(f"顶点 {v} 不在有效范围内") def print_edges(self): """打印图的所有边""" print("图中的所有无向边:") for edge in self.edges: print(edge) def is_connected(self, start, end): """使用BFS判断两个顶点之间是否存在路径(检查连通性)""" self._validate_vertex(start) self._validate_vertex(end) if start == end: return True visited = [False] * self.V queue = [start] visited[start] = True while queue: current = queue.pop(0) for neighbor in self.adjacency_list[current]: if neighbor == end: return True if not visited[neighbor]: visited[neighbor] = True queue.append(neighbor) return False def count_connected_components(self): """计算图中的连通分量数量""" visited = [False] * self.V count = 0 for v in range(self.V): if not visited[v]: # 对未访问的顶点执行DFS self._dfs_for_components(v, visited) count += 1 return count def _dfs_for_components(self, vertex, visited): """用于计算连通分量的DFS辅助方法""" visited[vertex] = True for neighbor in self.adjacency_list[vertex]: if not visited[neighbor]: self._dfs_for_components(neighbor, visited)
▼Javascript复制代码class UndirectedEdge { /** * 无向图的边表示 * @param {number} vertex1 - 边的一个顶点 * @param {number} vertex2 - 边的另一个顶点 */ constructor(vertex1, vertex2) { this.vertex1 = vertex1; this.vertex2 = vertex2; } toString() { return `${this.vertex1} -- ${this.vertex2}`; } } class WeightedUndirectedEdge { /** * 带权重的无向边 * @param {number} vertex1 - 边的一个顶点 * @param {number} vertex2 - 边的另一个顶点 * @param {number} weight - 边的权重 */ constructor(vertex1, vertex2, weight) { this.vertex1 = vertex1; this.vertex2 = vertex2; this.weight = weight; } toString() { return `${this.vertex1} -- ${this.vertex2} (${this.weight})`; } } class UndirectedGraph { /** * 使用边列表实现的无向图 * @param {number} V - 顶点数量 */ constructor(V) { this.V = V; // 顶点数量 this.edges = []; // 边列表 this.adjacencyList = new Map(); // 邻接表 // 初始化顶点 for (let i = 0; i < V; i++) { this.adjacencyList.set(i, []); } } /** * 添加无向边 * @param {number} vertex1 - 边的一个顶点 * @param {number} vertex2 - 边的另一个顶点 */ addEdge(vertex1, vertex2) { // 确保顶点有效 if (vertex1 < 0 || vertex1 >= this.V || vertex2 < 0 || vertex2 >= this.V) { throw new Error("顶点索引无效"); } // 添加到边列表 this.edges.push(new UndirectedEdge(vertex1, vertex2)); // 更新邻接表(无向图需要双向添加) this.adjacencyList.get(vertex1).push(vertex2); this.adjacencyList.get(vertex2).push(vertex1); } /** * 获取图中的顶点数 * @returns {number} 顶点数 */ getVertexCount() { return this.V; } /** * 获取图中的边数 * @returns {number} 边数 */ getEdgeCount() { return this.edges.length; } /** * 获取顶点的度 * @param {number} vertex - 顶点 * @returns {number} 度 */ getDegree(vertex) { this.validateVertex(vertex); return this.adjacencyList.get(vertex).length; } /** * 获取与指定顶点相邻的所有顶点 * @param {number} vertex - 顶点 * @returns {number[]} 相邻顶点列表 */ getNeighbors(vertex) { this.validateVertex(vertex); return [...this.adjacencyList.get(vertex)]; } /** * 判断两个顶点之间是否存在边 * @param {number} v1 - 第一个顶点 * @param {number} v2 - 第二个顶点 * @returns {boolean} 是否存在边 */ hasEdge(v1, v2) { this.validateVertex(v1); this.validateVertex(v2); return this.adjacencyList.get(v1).includes(v2); } /** * 检查顶点是否有效 * @param {number} v - 顶点 */ validateVertex(v) { if (v < 0 || v >= this.V) { throw new Error(`顶点 ${v} 不在有效范围内`); } } /** * 打印图的所有边 */ printEdges() { console.log("图中的所有无向边:"); for (const edge of this.edges) { console.log(edge.toString()); } } /** * 使用BFS判断两个顶点之间是否存在路径(检查连通性) * @param {number} start - 起点 * @param {number} end - 终点 * @returns {boolean} 是否连通 */ isConnected(start, end) { this.validateVertex(start); this.validateVertex(end); if (start === end) return true; const visited = new Array(this.V).fill(false); const queue = [start]; visited[start] = true; while (queue.length > 0) { const current = queue.shift(); for (const neighbor of this.adjacencyList.get(current)) { if (neighbor === end) { return true; } if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } } } return false; } /** * 计算图中的连通分量数量 * @returns {number} 连通分量数量 */ countConnectedComponents() { const visited = new Array(this.V).fill(false); let count = 0; for (let v = 0; v < this.V; v++) { if (!visited[v]) { // 对未访问的顶点执行DFS this._dfsForComponents(v, visited); count++; } } return count; } /** * 用于计算连通分量的DFS辅助方法 * @param {number} vertex - 当前顶点 * @param {boolean[]} visited - 访问标记数组 */ _dfsForComponents(vertex, visited) { visited[vertex] = true; for (const neighbor of this.adjacencyList.get(vertex)) { if (!visited[neighbor]) { this._dfsForComponents(neighbor, visited); } } } }
▼Go复制代码package main import ( "errors" "fmt" ) // UndirectedEdge 无向图的边表示 type UndirectedEdge struct { Vertex1 int // 边的一个顶点 Vertex2 int // 边的另一个顶点 } // String 返回边的字符串表示 func (e UndirectedEdge) String() string { return fmt.Sprintf("%d -- %d", e.Vertex1, e.Vertex2) } // WeightedUndirectedEdge 带权重的无向边 type WeightedUndirectedEdge struct { Vertex1 int // 边的一个顶点 Vertex2 int // 边的另一个顶点 Weight int // 边的权重 } // String 返回带权重边的字符串表示 func (e WeightedUndirectedEdge) String() string { return fmt.Sprintf("%d -- %d (%d)", e.Vertex1, e.Vertex2, e.Weight) } // UndirectedGraph 使用边列表实现的无向图 type UndirectedGraph struct { V int // 顶点数量 Edges []UndirectedEdge // 边列表 AdjacencyMap map[int][]int // 邻接表 } // NewUndirectedGraph 创建新的无向图 func NewUndirectedGraph(v int) *UndirectedGraph { adjacencyMap := make(map[int][]int) // 初始化顶点 for i := 0; i < v; i++ { adjacencyMap[i] = []int{} } return &UndirectedGraph{ V: v, Edges: []UndirectedEdge{}, AdjacencyMap: adjacencyMap, } } // AddEdge 添加无向边 func (g *UndirectedGraph) AddEdge(vertex1, vertex2 int) error { // 确保顶点有效 if vertex1 < 0 || vertex1 >= g.V || vertex2 < 0 || vertex2 >= g.V { return errors.New("顶点索引无效") } // 添加到边列表 g.Edges = append(g.Edges, UndirectedEdge{ Vertex1: vertex1, Vertex2: vertex2, }) // 更新邻接表(无向图需要双向添加) g.AdjacencyMap[vertex1] = append(g.AdjacencyMap[vertex1], vertex2) g.AdjacencyMap[vertex2] = append(g.AdjacencyMap[vertex2], vertex1) return nil } // GetVertexCount 获取图中的顶点数 func (g *UndirectedGraph) GetVertexCount() int { return g.V } // GetEdgeCount 获取图中的边数 func (g *UndirectedGraph) GetEdgeCount() int { return len(g.Edges) } // GetDegree 获取顶点的度 func (g *UndirectedGraph) GetDegree(vertex int) (int, error) { if err := g.validateVertex(vertex); err != nil { return 0, err } return len(g.AdjacencyMap[vertex]), nil } // GetNeighbors 获取与指定顶点相邻的所有顶点 func (g *UndirectedGraph) GetNeighbors(vertex int) ([]int, error) { if err := g.validateVertex(vertex); err != nil { return nil, err } // 创建副本以避免外部修改 neighbors := make([]int, len(g.AdjacencyMap[vertex])) copy(neighbors, g.AdjacencyMap[vertex]) return neighbors, nil } // HasEdge 判断两个顶点之间是否存在边 func (g *UndirectedGraph) HasEdge(v1, v2 int) (bool, error) { if err := g.validateVertex(v1); err != nil { return false, err } if err := g.validateVertex(v2); err != nil { return false, err } // 检查v2是否在v1的邻居列表中 for _, neighbor := range g.AdjacencyMap[v1] { if neighbor == v2 { return true, nil } } return false, nil } // validateVertex 检查顶点是否有效 func (g *UndirectedGraph) validateVertex(v int) error { if v < 0 || v >= g.V { return fmt.Errorf("顶点 %d 不在有效范围内", v) } return nil } // PrintEdges 打印图的所有边 func (g *UndirectedGraph) PrintEdges() { fmt.Println("图中的所有无向边:") for _, edge := range g.Edges { fmt.Println(edge) } } // IsConnected 使用BFS判断两个顶点之间是否存在路径(检查连通性) func (g *UndirectedGraph) IsConnected(start, end int) (bool, error) { if err := g.validateVertex(start); err != nil { return false, err } if err := g.validateVertex(end); err != nil { return false, err } if start == end { return true, nil } // 已访问的顶点 visited := make([]bool, g.V) queue := []int{start} visited[start] = true for len(queue) > 0 { // 取出队列中的第一个元素 current := queue[0] queue = queue[1:] // 检查所有邻居 for _, neighbor := range g.AdjacencyMap[current] { if neighbor == end { return true, nil } if !visited[neighbor] { visited[neighbor] = true queue = append(queue, neighbor) } } } return false, nil } // CountConnectedComponents 计算图中的连通分量数量 func (g *UndirectedGraph) CountConnectedComponents() int { visited := make([]bool, g.V) count := 0 for v := 0; v < g.V; v++ { if !visited[v] { // 对未访问的顶点执行DFS g.dfsForComponents(v, visited) count++ } } return count } // dfsForComponents 用于计算连通分量的DFS辅助方法 func (g *UndirectedGraph) dfsForComponents(vertex int, visited []bool) { visited[vertex] = true for _, neighbor := range g.AdjacencyMap[vertex] { if !visited[neighbor] { g.dfsForComponents(neighbor, visited) } } }
▼C++复制代码#include <iostream> #include <vector> #include <unordered_map> #include <queue> #include <stdexcept> #include <string> // 无向图的边表示 class UndirectedEdge { public: int vertex1; // 边的一个顶点 int vertex2; // 边的另一个顶点 UndirectedEdge(int v1, int v2) : vertex1(v1), vertex2(v2) {} std::string toString() const { return std::to_string(vertex1) + " -- " + std::to_string(vertex2); } }; // 带权重的无向边 class WeightedUndirectedEdge { public: int vertex1; // 边的一个顶点 int vertex2; // 边的另一个顶点 int weight; // 边的权重 WeightedUndirectedEdge(int v1, int v2, int w) : vertex1(v1), vertex2(v2), weight(w) {} std::string toString() const { return std::to_string(vertex1) + " -- " + std::to_string(vertex2) + " (" + std::to_string(weight) + ")"; } }; // 使用边列表实现的无向图 class UndirectedGraph { private: int V; // 顶点数量 std::vector<UndirectedEdge> edges; // 边列表 std::unordered_map<int, std::vector<int>> adjacencyList; // 邻接表 // 检查顶点是否有效 void validateVertex(int v) const { if (v < 0 || v >= V) { throw std::invalid_argument("顶点 " + std::to_string(v) + " 不在有效范围内"); } } // 用于计算连通分量的DFS辅助方法 void dfsForComponents(int vertex, std::vector<bool>& visited) { visited[vertex] = true; for (int neighbor : adjacencyList.at(vertex)) { if (!visited[neighbor]) { dfsForComponents(neighbor, visited); } } } public: // 构造函数 UndirectedGraph(int V) : V(V) { // 初始化顶点 for (int i = 0; i < V; i++) { adjacencyList[i] = std::vector<int>(); } } // 添加无向边 void addEdge(int vertex1, int vertex2) { // 确保顶点有效 if (vertex1 < 0 || vertex1 >= V || vertex2 < 0 || vertex2 >= V) { throw std::invalid_argument("顶点索引无效"); } // 添加到边列表 edges.push_back(UndirectedEdge(vertex1, vertex2)); // 更新邻接表(无向图需要双向添加) adjacencyList[vertex1].push_back(vertex2); adjacencyList[vertex2].push_back(vertex1); } // 获取图中的顶点数 int getVertexCount() const { return V; } // 获取图中的边数 int getEdgeCount() const { return edges.size(); } // 获取顶点的度 int getDegree(int vertex) const { validateVertex(vertex); return adjacencyList.at(vertex).size(); } // 获取与指定顶点相邻的所有顶点 std::vector<int> getNeighbors(int vertex) const { validateVertex(vertex); return adjacencyList.at(vertex); } // 判断两个顶点之间是否存在边 bool hasEdge(int v1, int v2) const { validateVertex(v1); validateVertex(v2); const auto& neighbors = adjacencyList.at(v1); for (int neighbor : neighbors) { if (neighbor == v2) { return true; } } return false; } // 打印图的所有边 void printEdges() const { std::cout << "图中的所有无向边:" << std::endl; for (const UndirectedEdge& edge : edges) { std::cout << edge.toString() << std::endl; } } // 使用BFS判断两个顶点之间是否存在路径(检查连通性) bool isConnected(int start, int end) const { validateVertex(start); validateVertex(end); if (start == end) { return true; } std::vector<bool> visited(V, false); std::queue<int> queue; visited[start] = true; queue.push(start); while (!queue.empty()) { int current = queue.front(); queue.pop(); for (int neighbor : adjacencyList.at(current)) { if (neighbor == end) { return true; } if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } } } return false; } // 计算图中的连通分量数量 int countConnectedComponents() { std::vector<bool> visited(V, false); int count = 0; for (int v = 0; v < V; v++) { if (!visited[v]) { // 对未访问的顶点执行DFS dfsForComponents(v, visited); count++; } } return count; } };
优点:
缺点:
无向图特别适合表示双向或对等的关系:
社交网络中的"朋友"关系常用无向图建模,因为朋友关系通常是双向的。如果A是B的朋友,那么B也是A的朋友。
道路网络中,如果没有单行道限制,车辆可以在同一条道路上双向通行,这种情况下使用无向图建模更为自然。同样,电信网络中的通信链路、电力网络中的电力线路等,如果允许双向传输,也适合用无向图表示。
计算机网络拓扑中,如果两台设备之间可以互相通信,则它们之间的连接可以用无向边表示。互联网骨干网络的结构通常被建模为无向图,以便分析路由和连通性问题。
分子结构和化学键也常用无向图表示,其中原子是顶点,化学键是边。这种表示方法帮助化学家分析分子的结构特性和性质。
最小生成树(Minimum Spanning Tree, MST)是无向图中的一个重要概念,指连接图中所有顶点的一棵权重最小的树。对于带权无向图,最小生成树有着重要的应用价值:
求解最小生成树的两个经典算法是Kruskal算法和Prim算法:
▼Java复制代码// Kruskal算法实现最小生成树 public class KruskalMST { private List<WeightedUndirectedEdge> mst = new ArrayList<>(); // 最小生成树的边 private int weight = 0; // 最小生成树的总权重 public KruskalMST(UndirectedWeightedGraph G) { // 边列表 List<WeightedUndirectedEdge> edges = G.getAllEdges(); int V = G.getVertexCount(); // 按权重排序 Collections.sort(edges, Comparator.comparingInt(e -> e.weight)); // 并查集,用于检测环 UnionFind uf = new UnionFind(V); // 贪心选择边 for (WeightedUndirectedEdge edge : edges) { int v = edge.vertex1; int w = edge.vertex2; // 如果添加此边不会形成环 if (uf.find(v) != uf.find(w)) { uf.union(v, w); // 合并集合 mst.add(edge); // 添加到最小生成树 weight += edge.weight; // 更新总权重 // 如果已经有V-1条边,MST构建完成 if (mst.size() == V - 1) { break; } } } } // 获取最小生成树的边 public List<WeightedUndirectedEdge> edges() { return mst; } // 获取最小生成树的总权重 public int weight() { return weight; } // 并查集实现 private class UnionFind { private int[] parent; private int[] rank; public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } } // 查找 public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; } // 合并 public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 按秩合并 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } } }
在无向图中,连通分量(Connected Component)是指图中的一个极大连通子图,其中任意两个顶点之间都存在路径。寻找图中的连通分量对于分析网络结构和数据聚类有重要意义。
测验答案
- 最多可以有10×(10-1)/2 = 45条边。这样的图被称为完全图(Complete Graph),其中任意两个顶点之间都有一条边连接。
- 至少需要n-1条边。这种情况下,图的结构是一棵树(Tree),即恰好连通且没有环的无向图。
- 桥是指图中的一条边,如果删除这条边,会导致图中的连通分量数量增加。换句话说,桥是连接图中两个连通分量的唯一边,移除桥会导致这两个部分不再连通。
- 如果用边列表表示,无向图的边列表长度与有向图表示相同连接关系时的边列表长度相比,通常会更短。这是因为在有向图中,两个顶点之间的双向连接需要用两条有向边表示,而在无向图中只需要一条无向边。