有向图是一种边具有方向性的图结构,图中的边从一个顶点指向另一个顶点。有向图广泛应用于网络流量分析、社交网络关系建模、任务依赖关系等场景。
有向图(Directed Graph,也称为Digraph)是图论中的一种基本图类型,其中每条边都有明确的方向。在有向图中,边由一个顶点(称为起点或源点)指向另一个顶点(称为终点或目标点)。这种有方向性的连接让有向图特别适合表示具有单向关系的各种现实问题。
有向图中的关键概念:
▼Java复制代码import java.util.*; // 有向图的边表示 class DirectedEdge { int source; // 边的起点 int destination; // 边的终点 public DirectedEdge(int source, int destination) { this.source = source; this.destination = destination; } @Override public String toString() { return source + " -> " + destination; } } // 带权重的有向边 class WeightedDirectedEdge { int source; // 边的起点 int destination; // 边的终点 int weight; // 边的权重 public WeightedDirectedEdge(int source, int destination, int weight) { this.source = source; this.destination = destination; this.weight = weight; } @Override public String toString() { return source + " -> " + destination + " (" + weight + ")"; } } // 使用边列表实现的有向图 class DirectedGraph { private int V; // 顶点数量 private List<DirectedEdge> edges; // 边列表 private Map<Integer, List<Integer>> outEdges; // 每个顶点的出边列表 private Map<Integer, List<Integer>> inEdges; // 每个顶点的入边列表 public DirectedGraph(int V) { this.V = V; this.edges = new ArrayList<>(); this.outEdges = new HashMap<>(); this.inEdges = new HashMap<>(); // 初始化顶点 for (int i = 0; i < V; i++) { outEdges.put(i, new ArrayList<>()); inEdges.put(i, new ArrayList<>()); } } // 添加有向边 public void addEdge(int source, int destination) { // 确保顶点有效 if (source < 0 || source >= V || destination < 0 || destination >= V) { throw new IllegalArgumentException("顶点索引无效"); } // 添加到边列表 edges.add(new DirectedEdge(source, destination)); // 更新出边和入边列表 outEdges.get(source).add(destination); inEdges.get(destination).add(source); } // 获取图中的顶点数 public int getVertexCount() { return V; } // 获取图中的边数 public int getEdgeCount() { return edges.size(); } // 获取顶点的出度 public int getOutDegree(int vertex) { validateVertex(vertex); return outEdges.get(vertex).size(); } // 获取顶点的入度 public int getInDegree(int vertex) { validateVertex(vertex); return inEdges.get(vertex).size(); } // 获取从指定顶点出发的所有边 public List<Integer> getOutEdges(int vertex) { validateVertex(vertex); return new ArrayList<>(outEdges.get(vertex)); } // 获取指向指定顶点的所有边 public List<Integer> getInEdges(int vertex) { validateVertex(vertex); return new ArrayList<>(inEdges.get(vertex)); } // 判断从顶点u到顶点v是否存在有向边 public boolean hasEdge(int u, int v) { validateVertex(u); validateVertex(v); return outEdges.get(u).contains(v); } // 检查顶点是否有效 private void validateVertex(int v) { if (v < 0 || v >= V) { throw new IllegalArgumentException("顶点 " + v + " 不在有效范围内"); } } // 打印图的所有边 public void printEdges() { System.out.println("图中的所有有向边:"); for (DirectedEdge edge : edges) { System.out.println(edge); } } // 使用DFS判断从顶点source到顶点target是否可达 public boolean isReachable(int source, int target) { validateVertex(source); validateVertex(target); boolean[] visited = new boolean[V]; Stack<Integer> stack = new Stack<>(); stack.push(source); visited[source] = true; while (!stack.isEmpty()) { int current = stack.pop(); if (current == target) { return true; } for (int neighbor : outEdges.get(current)) { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } } } return false; } }
▼Python复制代码class DirectedEdge: """有向图的边表示""" def __init__(self, source, destination): self.source = source # 边的起点 self.destination = destination # 边的终点 def __str__(self): return f"{self.source} -> {self.destination}" class WeightedDirectedEdge: """带权重的有向边""" def __init__(self, source, destination, weight): self.source = source # 边的起点 self.destination = destination # 边的终点 self.weight = weight # 边的权重 def __str__(self): return f"{self.source} -> {self.destination} ({self.weight})" class DirectedGraph: """使用边列表实现的有向图""" def __init__(self, V): self.V = V # 顶点数量 self.edges = [] # 边列表 self.out_edges = {} # 每个顶点的出边列表 self.in_edges = {} # 每个顶点的入边列表 # 初始化顶点 for i in range(V): self.out_edges[i] = [] self.in_edges[i] = [] def add_edge(self, source, destination): """添加有向边""" # 确保顶点有效 if source < 0 or source >= self.V or destination < 0 or destination >= self.V: raise ValueError("顶点索引无效") # 添加到边列表 self.edges.append(DirectedEdge(source, destination)) # 更新出边和入边列表 self.out_edges[source].append(destination) self.in_edges[destination].append(source) def get_vertex_count(self): """获取图中的顶点数""" return self.V def get_edge_count(self): """获取图中的边数""" return len(self.edges) def get_out_degree(self, vertex): """获取顶点的出度""" self._validate_vertex(vertex) return len(self.out_edges[vertex]) def get_in_degree(self, vertex): """获取顶点的入度""" self._validate_vertex(vertex) return len(self.in_edges[vertex]) def get_out_edges(self, vertex): """获取从指定顶点出发的所有边""" self._validate_vertex(vertex) return self.out_edges[vertex].copy() def get_in_edges(self, vertex): """获取指向指定顶点的所有边""" self._validate_vertex(vertex) return self.in_edges[vertex].copy() def has_edge(self, u, v): """判断从顶点u到顶点v是否存在有向边""" self._validate_vertex(u) self._validate_vertex(v) return v in self.out_edges[u] 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_reachable(self, source, target): """使用DFS判断从顶点source到顶点target是否可达""" self._validate_vertex(source) self._validate_vertex(target) visited = [False] * self.V stack = [source] visited[source] = True while stack: current = stack.pop() if current == target: return True for neighbor in self.out_edges[current]: if not visited[neighbor]: visited[neighbor] = True stack.append(neighbor) return False
▼Javascript复制代码class DirectedEdge { /** * 有向图的边表示 * @param {number} source - 边的起点 * @param {number} destination - 边的终点 */ constructor(source, destination) { this.source = source; this.destination = destination; } toString() { return `${this.source} -> ${this.destination}`; } } class WeightedDirectedEdge { /** * 带权重的有向边 * @param {number} source - 边的起点 * @param {number} destination - 边的终点 * @param {number} weight - 边的权重 */ constructor(source, destination, weight) { this.source = source; this.destination = destination; this.weight = weight; } toString() { return `${this.source} -> ${this.destination} (${this.weight})`; } } class DirectedGraph { /** * 使用边列表实现的有向图 * @param {number} V - 顶点数量 */ constructor(V) { this.V = V; // 顶点数量 this.edges = []; // 边列表 this.outEdges = new Map(); // 每个顶点的出边列表 this.inEdges = new Map(); // 每个顶点的入边列表 // 初始化顶点 for (let i = 0; i < V; i++) { this.outEdges.set(i, []); this.inEdges.set(i, []); } } /** * 添加有向边 * @param {number} source - 边的起点 * @param {number} destination - 边的终点 */ addEdge(source, destination) { // 确保顶点有效 if (source < 0 || source >= this.V || destination < 0 || destination >= this.V) { throw new Error("顶点索引无效"); } // 添加到边列表 this.edges.push(new DirectedEdge(source, destination)); // 更新出边和入边列表 this.outEdges.get(source).push(destination); this.inEdges.get(destination).push(source); } /** * 获取图中的顶点数 * @returns {number} 顶点数 */ getVertexCount() { return this.V; } /** * 获取图中的边数 * @returns {number} 边数 */ getEdgeCount() { return this.edges.length; } /** * 获取顶点的出度 * @param {number} vertex - 顶点 * @returns {number} 出度 */ getOutDegree(vertex) { this.validateVertex(vertex); return this.outEdges.get(vertex).length; } /** * 获取顶点的入度 * @param {number} vertex - 顶点 * @returns {number} 入度 */ getInDegree(vertex) { this.validateVertex(vertex); return this.inEdges.get(vertex).length; } /** * 获取从指定顶点出发的所有边 * @param {number} vertex - 顶点 * @returns {number[]} 相邻顶点列表 */ getOutEdges(vertex) { this.validateVertex(vertex); return [...this.outEdges.get(vertex)]; } /** * 获取指向指定顶点的所有边 * @param {number} vertex - 顶点 * @returns {number[]} 相邻顶点列表 */ getInEdges(vertex) { this.validateVertex(vertex); return [...this.inEdges.get(vertex)]; } /** * 判断从顶点u到顶点v是否存在有向边 * @param {number} u - 起点 * @param {number} v - 终点 * @returns {boolean} 是否存在边 */ hasEdge(u, v) { this.validateVertex(u); this.validateVertex(v); return this.outEdges.get(u).includes(v); } /** * 检查顶点是否有效 * @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()); } } /** * 使用DFS判断从顶点source到顶点target是否可达 * @param {number} source - 起点 * @param {number} target - 终点 * @returns {boolean} 是否可达 */ isReachable(source, target) { this.validateVertex(source); this.validateVertex(target); const visited = new Array(this.V).fill(false); const stack = [source]; visited[source] = true; while (stack.length > 0) { const current = stack.pop(); if (current === target) { return true; } for (const neighbor of this.outEdges.get(current)) { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } } } return false; } }
▼Go复制代码package main import ( "errors" "fmt" ) // DirectedEdge 有向图的边表示 type DirectedEdge struct { Source int // 边的起点 Destination int // 边的终点 } // String 返回边的字符串表示 func (e DirectedEdge) String() string { return fmt.Sprintf("%d -> %d", e.Source, e.Destination) } // WeightedDirectedEdge 带权重的有向边 type WeightedDirectedEdge struct { Source int // 边的起点 Destination int // 边的终点 Weight int // 边的权重 } // String 返回带权重边的字符串表示 func (e WeightedDirectedEdge) String() string { return fmt.Sprintf("%d -> %d (%d)", e.Source, e.Destination, e.Weight) } // DirectedGraph 使用边列表实现的有向图 type DirectedGraph struct { V int // 顶点数量 Edges []DirectedEdge // 边列表 OutEdges map[int][]int // 每个顶点的出边列表 InEdges map[int][]int // 每个顶点的入边列表 } // NewDirectedGraph 创建新的有向图 func NewDirectedGraph(v int) *DirectedGraph { outEdges := make(map[int][]int) inEdges := make(map[int][]int) // 初始化顶点 for i := 0; i < v; i++ { outEdges[i] = []int{} inEdges[i] = []int{} } return &DirectedGraph{ V: v, Edges: []DirectedEdge{}, OutEdges: outEdges, InEdges: inEdges, } } // AddEdge 添加有向边 func (g *DirectedGraph) AddEdge(source, destination int) error { // 确保顶点有效 if source < 0 || source >= g.V || destination < 0 || destination >= g.V { return errors.New("顶点索引无效") } // 添加到边列表 g.Edges = append(g.Edges, DirectedEdge{ Source: source, Destination: destination, }) // 更新出边和入边列表 g.OutEdges[source] = append(g.OutEdges[source], destination) g.InEdges[destination] = append(g.InEdges[destination], source) return nil } // GetVertexCount 获取图中的顶点数 func (g *DirectedGraph) GetVertexCount() int { return g.V } // GetEdgeCount 获取图中的边数 func (g *DirectedGraph) GetEdgeCount() int { return len(g.Edges) } // GetOutDegree 获取顶点的出度 func (g *DirectedGraph) GetOutDegree(vertex int) (int, error) { if err := g.validateVertex(vertex); err != nil { return 0, err } return len(g.OutEdges[vertex]), nil } // GetInDegree 获取顶点的入度 func (g *DirectedGraph) GetInDegree(vertex int) (int, error) { if err := g.validateVertex(vertex); err != nil { return 0, err } return len(g.InEdges[vertex]), nil } // GetOutEdges 获取从指定顶点出发的所有边 func (g *DirectedGraph) GetOutEdges(vertex int) ([]int, error) { if err := g.validateVertex(vertex); err != nil { return nil, err } // 创建副本以避免外部修改 outEdges := make([]int, len(g.OutEdges[vertex])) copy(outEdges, g.OutEdges[vertex]) return outEdges, nil } // GetInEdges 获取指向指定顶点的所有边 func (g *DirectedGraph) GetInEdges(vertex int) ([]int, error) { if err := g.validateVertex(vertex); err != nil { return nil, err } // 创建副本以避免外部修改 inEdges := make([]int, len(g.InEdges[vertex])) copy(inEdges, g.InEdges[vertex]) return inEdges, nil } // HasEdge 判断从顶点u到顶点v是否存在有向边 func (g *DirectedGraph) HasEdge(u, v int) (bool, error) { if err := g.validateVertex(u); err != nil { return false, err } if err := g.validateVertex(v); err != nil { return false, err } // 检查v是否在u的出边列表中 for _, dest := range g.OutEdges[u] { if dest == v { return true, nil } } return false, nil } // validateVertex 检查顶点是否有效 func (g *DirectedGraph) validateVertex(v int) error { if v < 0 || v >= g.V { return fmt.Errorf("顶点 %d 不在有效范围内", v) } return nil } // PrintEdges 打印图的所有边 func (g *DirectedGraph) PrintEdges() { fmt.Println("图中的所有有向边:") for _, edge := range g.Edges { fmt.Println(edge) } } // IsReachable 使用DFS判断从顶点source到顶点target是否可达 func (g *DirectedGraph) IsReachable(source, target int) (bool, error) { if err := g.validateVertex(source); err != nil { return false, err } if err := g.validateVertex(target); err != nil { return false, err } // 已访问的顶点 visited := make([]bool, g.V) stack := []int{source} visited[source] = true for len(stack) > 0 { // 弹出栈顶元素 n := len(stack) current := stack[n-1] stack = stack[:n-1] if current == target { return true, nil } // 访问所有未访问的邻居 for _, neighbor := range g.OutEdges[current] { if !visited[neighbor] { visited[neighbor] = true stack = append(stack, neighbor) } } } return false, nil }
▼C++复制代码#include <iostream> #include <vector> #include <unordered_map> #include <stack> #include <queue> #include <stdexcept> #include <string> // 有向图的边表示 class DirectedEdge { public: int source; // 边的起点 int destination; // 边的终点 DirectedEdge(int source, int destination) : source(source), destination(destination) {} std::string toString() const { return std::to_string(source) + " -> " + std::to_string(destination); } }; // 带权重的有向边 class WeightedDirectedEdge { public: int source; // 边的起点 int destination; // 边的终点 int weight; // 边的权重 WeightedDirectedEdge(int source, int destination, int weight) : source(source), destination(destination), weight(weight) {} std::string toString() const { return std::to_string(source) + " -> " + std::to_string(destination) + " (" + std::to_string(weight) + ")"; } }; // 使用边列表实现的有向图 class DirectedGraph { private: int V; // 顶点数量 std::vector<DirectedEdge> edges; // 边列表 std::unordered_map<int, std::vector<int>> outEdges; // 每个顶点的出边列表 std::unordered_map<int, std::vector<int>> inEdges; // 每个顶点的入边列表 // 检查顶点是否有效 void validateVertex(int v) const { if (v < 0 || v >= V) { throw std::invalid_argument("顶点 " + std::to_string(v) + " 不在有效范围内"); } } public: // 构造函数 DirectedGraph(int V) : V(V) { // 初始化顶点 for (int i = 0; i < V; i++) { outEdges[i] = std::vector<int>(); inEdges[i] = std::vector<int>(); } } // 添加有向边 void addEdge(int source, int destination) { // 确保顶点有效 if (source < 0 || source >= V || destination < 0 || destination >= V) { throw std::invalid_argument("顶点索引无效"); } // 添加到边列表 edges.push_back(DirectedEdge(source, destination)); // 更新出边和入边列表 outEdges[source].push_back(destination); inEdges[destination].push_back(source); } // 获取图中的顶点数 int getVertexCount() const { return V; } // 获取图中的边数 int getEdgeCount() const { return edges.size(); } // 获取顶点的出度 int getOutDegree(int vertex) const { validateVertex(vertex); return outEdges.at(vertex).size(); } // 获取顶点的入度 int getInDegree(int vertex) const { validateVertex(vertex); return inEdges.at(vertex).size(); } // 获取从指定顶点出发的所有边 std::vector<int> getOutEdges(int vertex) const { validateVertex(vertex); return outEdges.at(vertex); } // 获取指向指定顶点的所有边 std::vector<int> getInEdges(int vertex) const { validateVertex(vertex); return inEdges.at(vertex); } // 判断从顶点u到顶点v是否存在有向边 bool hasEdge(int u, int v) const { validateVertex(u); validateVertex(v); const auto& neighbors = outEdges.at(u); for (int neighbor : neighbors) { if (neighbor == v) { return true; } } return false; } // 打印图的所有边 void printEdges() const { std::cout << "图中的所有有向边:" << std::endl; for (const DirectedEdge& edge : edges) { std::cout << edge.toString() << std::endl; } } // 使用DFS判断从顶点source到顶点target是否可达 bool isReachable(int source, int target) const { validateVertex(source); validateVertex(target); std::vector<bool> visited(V, false); std::stack<int> stack; stack.push(source); visited[source] = true; while (!stack.empty()) { int current = stack.top(); stack.pop(); if (current == target) { return true; } for (int neighbor : outEdges.at(current)) { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } } } return false; } // 广度优先搜索从顶点s开始访问图 void bfs(int s) const { validateVertex(s); std::vector<bool> visited(V, false); std::queue<int> queue; visited[s] = true; queue.push(s); std::cout << "BFS遍历(从顶点" << s << "开始):"; while (!queue.empty()) { int v = queue.front(); queue.pop(); std::cout << v << " "; for (int w : outEdges.at(v)) { if (!visited[w]) { visited[w] = true; queue.push(w); } } } std::cout << std::endl; } // 深度优先搜索从顶点s开始访问图 void dfs(int s) const { validateVertex(s); std::vector<bool> visited(V, false); std::cout << "DFS遍历(从顶点" << s << "开始):"; dfsUtil(s, visited); std::cout << std::endl; } private: // DFS辅助函数 void dfsUtil(int v, std::vector<bool>& visited) const { visited[v] = true; std::cout << v << " "; for (int w : outEdges.at(v)) { if (!visited[w]) { dfsUtil(w, visited); } } } };
优点:
缺点:
有向图在现实中有着广泛的应用,它能够准确地表示具有方向性的关系。
比如在网络流量分析中,数据包的传输方向是单向的,通过有向图可以更精确地表示和分析网络拓扑。在社交网络中,"关注"关系通常是单向的,例如A关注B并不意味着B也关注A,这种关系很自然地用有向图表示。
软件工程领域的依赖关系管理也是有向图的典型应用。模块A依赖模块B,但B可能不依赖A,这种依赖关系可以通过有向图进行建模和分析,帮助开发人员理解代码结构并识别潜在的循环依赖问题。
在任务调度系统中,任务之间的前后顺序关系形成了一个有向无环图(DAG),通过对这个图进行拓扑排序,可以得到一个合理的任务执行顺序。GPS导航系统中的道路网络也常用有向图表示,因为许多道路是单行道,只能按一个方向行驶。
在状态机设计、工作流引擎、资源分配算法等领域有向图都发挥着不可替代的作用。
有向无环图(Directed Acyclic Graph, DAG)是一种没有环的有向图。DAG具有许多特殊性质,在计算机科学中有广泛应用:
DAG的Java实现可以扩展基本的有向图实现,添加环检测和拓扑排序功能:
▼Java复制代码// 有向无环图(DAG)的实现扩展 public class DirectedAcyclicGraph extends DirectedGraph { public DirectedAcyclicGraph(int V) { super(V); } // 重写添加边的方法,确保不会形成环 @Override public void addEdge(int source, int destination) { // 检查添加此边是否会形成环 if (isReachable(destination, source)) { throw new IllegalArgumentException("添加此边将形成环,DAG不允许有环"); } super.addEdge(source, destination); } // 拓扑排序 - Kahn算法 public List<Integer> topologicalSort() { int V = getVertexCount(); int[] inDegree = new int[V]; List<Integer> result = new ArrayList<>(); // 计算每个顶点的入度 for (int v = 0; v < V; v++) { inDegree[v] = getInDegree(v); } // 创建一个队列,将所有入度为0的顶点加入队列 Queue<Integer> queue = new LinkedList<>(); for (int v = 0; v < V; v++) { if (inDegree[v] == 0) { queue.add(v); } } // 处理队列中的顶点 while (!queue.isEmpty()) { // 从队列中取出一个顶点并添加到结果中 int u = queue.poll(); result.add(u); // 对于从u出发的每条边(u,v),将v的入度减1 for (int v : getOutEdges(u)) { // 将v的入度减1 inDegree[v]--; // 如果v的入度变为0,则将其加入队列 if (inDegree[v] == 0) { queue.add(v); } } } // 如果结果中的顶点数小于图中的顶点数,说明图中有环 if (result.size() != V) { throw new IllegalStateException("图中存在环,无法进行拓扑排序"); } return result; } }
在有向图中,强连通分量(Strongly Connected Component, SCC)是指图中的一个子图,其中任意两个顶点之间都存在相互可达的路径。强连通分量是理解有向图结构的重要概念,也是许多图算法的基础。
Kosaraju算法和Tarjan算法是寻找有向图中强连通分量的经典算法。这些算法可以在线性时间内找出所有强连通分量,为有向图分析提供了强大工具。
测验答案
- A可以直接到达3个其他顶点,有2个顶点可以直接到达A。
- 一个有n个顶点的有向图最多可以有n(n-1)条边,对于5个顶点就是5×4=20条边。这种情况下,图中任意两个不同顶点之间都有一条有向边,称为完全有向图。
- 源点(source)是指入度为0的顶点,即没有边指向该顶点;汇点(sink)是指出度为0的顶点,即没有从该顶点出发的边。它们分别代表了信息流的起点和终点。
- 拓扑排序只能应用于有向无环图(DAG)。因为如果图中存在环,那么环上的顶点之间存在循环依赖关系,无法确定它们的先后顺序,因此无法得到一个有效的拓扑序列。