一、有向圖（Directed Graph）

1. 定義

有向圖是一個(gè)由頂點(diǎn)（節(jié)點(diǎn)）和有方向的邊（弧）組成的圖。在有向圖中，每條邊都有一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的關(guān)系。

2. 特點(diǎn)

• 邊有方向：每條邊都有一個(gè)方向，通常用箭頭表示。例如，邊 A→B 表示從頂點(diǎn) A 到頂點(diǎn) B。
• 可能存在孤立點(diǎn)：有向圖中的某些頂點(diǎn)可能沒(méi)有入邊或出邊。
• 可有多個(gè)入度和出度：頂點(diǎn)的入度是指指向該頂點(diǎn)的邊數(shù)，出度是指從該頂點(diǎn)出發(fā)的邊數(shù)。

3. 優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)：

  • 能夠準(zhǔn)確表示有向關(guān)系，如網(wǎng)頁(yè)鏈接、任務(wù)調(diào)度等。
  • 適合表示不對(duì)稱(chēng)的關(guān)系。

• 缺點(diǎn)：

  • 復(fù)雜性較高，特別是在涉及遍歷和路徑尋找時(shí)。
  • 算法實(shí)現(xiàn)相對(duì)復(fù)雜，如最短路徑算法。

4. 應(yīng)用場(chǎng)景

• 網(wǎng)絡(luò)路由：表示計(jì)算機(jī)網(wǎng)絡(luò)中的連接。
• 任務(wù)調(diào)度：表示任務(wù)之間的依賴關(guān)系。
• 圖形界面：表示用戶界面元素之間的交互。

5. 示例

有向圖可以用鄰接表或鄰接矩陣表示。以下是一個(gè)有向圖的示例：

示例代碼（Java 實(shí)現(xiàn)）

import java.util.*;class DirectedGraph {private Map<String, List<String>> adjacencyList;public DirectedGraph() {adjacencyList = new HashMap<>();}public void addVertex(String vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(String from, String to) {adjacencyList.putIfAbsent(from, new ArrayList<>());adjacencyList.putIfAbsent(to, new ArrayList<>());adjacencyList.get(from).add(to);}public List<String> getNeighbors(String vertex) {return adjacencyList.get(vertex);}
}

二、無(wú)向圖（Undirected Graph）

1. 定義

無(wú)向圖是一個(gè)由頂點(diǎn)和無(wú)方向的邊組成的圖。在無(wú)向圖中，邊連接兩個(gè)頂點(diǎn)，但沒(méi)有方向。

2. 特點(diǎn)

• 邊無(wú)方向：邊表示的是兩個(gè)頂點(diǎn)之間的關(guān)系，通常用線段表示。例如，邊 A?B 表示頂點(diǎn) A 和頂點(diǎn) B 是相連的。
• 每條邊相互對(duì)稱(chēng)：如果存在邊 A?B，則同時(shí)存在邊 B?A。
• 所有頂點(diǎn)具有相同的邊關(guān)系。

3. 優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)：

  • 適合表示對(duì)稱(chēng)關(guān)系，如社交網(wǎng)絡(luò)、朋友關(guān)系。
  • 較簡(jiǎn)單的算法實(shí)現(xiàn)。

• 缺點(diǎn)：

  • 對(duì)于某些應(yīng)用，缺乏表達(dá)方向性的能力。
  • 在某些情況下，圖的結(jié)構(gòu)可能會(huì)顯得過(guò)于簡(jiǎn)單。

4. 應(yīng)用場(chǎng)景

• 社交網(wǎng)絡(luò)：表示用戶之間的朋友關(guān)系。
• 電路設(shè)計(jì)：表示電路中元件之間的連接。
• 城市交通：表示城市道路網(wǎng)絡(luò)。

5. 示例

無(wú)向圖可以用鄰接表或鄰接矩陣表示。以下是一個(gè)無(wú)向圖的示例：

示例代碼（Java 實(shí)現(xiàn)）

import java.util.*;class UndirectedGraph {private Map<String, List<String>> adjacencyList;public UndirectedGraph() {adjacencyList = new HashMap<>();}public void addVertex(String vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(String vertex1, String vertex2) {adjacencyList.putIfAbsent(vertex1, new ArrayList<>());adjacencyList.putIfAbsent(vertex2, new ArrayList<>());adjacencyList.get(vertex1).add(vertex2);adjacencyList.get(vertex2).add(vertex1); // 無(wú)向邊}public List<String> getNeighbors(String vertex) {return adjacencyList.get(vertex);}
}

三、加權(quán)圖（Weighted Graph）

1. 定義

加權(quán)圖是一個(gè)圖，其中每條邊都分配有一個(gè)權(quán)重（或成本）。權(quán)重可以表示距離、時(shí)間、費(fèi)用等多種含義。

2. 特點(diǎn)

• 每條邊有權(quán)重：邊的權(quán)重通常是一個(gè)數(shù)值，表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的代價(jià)。
• 支持最短路徑計(jì)算：適合用于計(jì)算從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑。
• 可以是有向或無(wú)向圖：加權(quán)圖可以是有向的或無(wú)向的。

3. 優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)：

  • 能夠表示復(fù)雜的關(guān)系，如交通網(wǎng)絡(luò)、物流等。
  • 可以使用多種算法（如 Dijkstra、Bellman-Ford）進(jìn)行路徑優(yōu)化。

• 缺點(diǎn)：

  • 處理復(fù)雜性較高，尤其是在大量邊和頂點(diǎn)的情況下。
  • 可能導(dǎo)致計(jì)算錯(cuò)誤，尤其在負(fù)權(quán)重情況下（如 Bellman-Ford 算法）。

4. 應(yīng)用場(chǎng)景

• 地圖導(dǎo)航：用于計(jì)算從起點(diǎn)到終點(diǎn)的最短路徑。
• 網(wǎng)絡(luò)流量：分析和優(yōu)化網(wǎng)絡(luò)數(shù)據(jù)傳輸。
• 電路分析：計(jì)算電路中元件之間的電流和電壓。

5. 示例

加權(quán)圖的表示通常使用鄰接表或鄰接矩陣。以下是一個(gè)加權(quán)圖的示例：

示例代碼（Java 實(shí)現(xiàn)）

import java.util.*;class WeightedGraph {private Map<String, List<Edge>> adjacencyList;class Edge {String destination;int weight;Edge(String destination, int weight) {this.destination = destination;this.weight = weight;}}public WeightedGraph() {adjacencyList = new HashMap<>();}public void addVertex(String vertex) {adjacencyList.putIfAbsent(vertex, new ArrayList<>());}public void addEdge(String from, String to, int weight) {adjacencyList.putIfAbsent(from, new ArrayList<>());adjacencyList.putIfAbsent(to, new ArrayList<>());adjacencyList.get(from).add(new Edge(to, weight));adjacencyList.get(to).add(new Edge(from, weight)); // 如果是無(wú)向圖}public List<Edge> getNeighbors(String vertex) {return adjacencyList.get(vertex);}
}

總結(jié)比較

圖類(lèi)型	邊的方向性	權(quán)重	適用場(chǎng)景
有向圖	有方向	無(wú)	任務(wù)調(diào)度、網(wǎng)絡(luò)路由
無(wú)向圖	無(wú)方向	無(wú)	社交網(wǎng)絡(luò)、城市交通
加權(quán)圖	有向/無(wú)向	有	地圖導(dǎo)航、網(wǎng)絡(luò)流量、電路分析

通過(guò)這些詳細(xì)的介紹，可以更清晰地理解不同圖類(lèi)型的特點(diǎn)和應(yīng)用場(chǎng)景，為具體問(wèn)題的解決選擇合適的數(shù)據(jù)結(jié)構(gòu)提供幫助。