基本概念
圖的定義
一個圖是由點集V={vi}和 VV 中元素的無序對的一個集合E={ek} 所構成的二元組，記為G=(V,E)，V中的元素vi叫做頂點，E中的元素 ek叫做邊。
對於V中的兩點 u,v，如果邊(u,v) 屬於E，則稱 u,v兩點相鄰，u,v稱為邊(u,v)的端點。
我們可以用m(G)=|E| 表示圖G中的邊數，用n(G)=|V|表示圖G中的頂點個數。
無向圖的定義
對E中的任一條邊(vi,vj)，如果邊(vi,vj) 端點無序，則它是無向邊，此時圖G稱為無向圖。無向圖是最簡單的圖模型，下圖顯示了同一幅無向圖，頂點使用圓圈表示，邊則是頂點之間的連線，沒有箭頭（圖片來自於《演算法第四版》）：
無向圖的API
對於一個無向圖，我們關心圖的頂點數、邊數、每個頂點的相鄰頂點和邊的新增操作，所以介面如下所示：
package com.zhiyiyo.graph;
/**
* 无向图
*/
public interface Graph {
/**
* 返回图中的顶点数
*/
int V();
/**
* 返回图中的边数
*/
int E();
/**
* 向图中添加一条边
* @param v 顶点 v
* @param w 顶点 w
*/
void addEdge(int v, int w);
/**
* 返回所有相邻顶点
* @param v 顶点 v
* @return 所有相邻顶点
*/
Iterable<Integer> adj(int v);
}無向圖的實作方式
鄰接矩陣
以矩陣表示圖對研究圖的性質及應用常常是比較方便的，對於各種圖有各種矩陣表示方式，例如權矩陣和鄰接矩陣，這裡我們只關注鄰接矩陣。它的定義為：
對於圖G=(V,E)，|V|=n，建構一個矩陣 A=(aij)n×n ，其中：
則稱矩陣A為圖G的鄰接矩陣。
由定義可知，我們可以使用一個二維的布林數組 A 來實現鄰接矩陣，當 A[i][j] = true 說明頂點 i 和 j 相鄰。
對於 n個頂點的圖 G，鄰接矩陣需要消耗的空間為 n2個布林值的大小，對於稀疏圖來說會造成很大的浪費，當頂點數很大時所消耗的空間會是個天文數字。同時當圖比較特殊，存在自環以及平行邊時，鄰接矩陣的表示方式是無能為力的。 《演算法》中給出了存在這兩種情況的圖：
邊的陣列
對於無向圖，我們可以實作一個類別 Edge，裡面只用兩個實例變數用來儲存兩個頂點 u和 v，接著在一個陣列裡面保存所有 Edge 即可。這樣做有一個很大的問題，就是在取得頂點 v的所有相鄰頂點時必須遍歷整個陣列才能得到，時間複雜度是O(|E|)，由於取得相鄰頂點是很常用的操作，所以這種表示法也不太行。
鄰接表數組
如果我們把頂點表示為整數，取值範圍為0∼|V|−1，那麼就可以用一個長度為|V| 的數組的索引表示每一個頂點，然後將每個陣列元素設定為一個鍊錶，上面掛著索引所代表的的頂點相鄰的其他頂點。圖一所示的無向圖可以用下圖所示的鄰接表數組表示出來：
#使用鄰接表實現無向圖的程式碼如下所示，由於鄰接表數組中的每個鍊錶都會保存與頂點相鄰的頂點，所以將邊添加到圖中時需要對數組中的兩個鍊錶進行添加節點的操作：
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.stack.LinkStack;
/**
* 使用邻接表实现的无向图
*/
public class LinkGraph implements Graph {
private final int V;
private int E;
private LinkStack<Integer>[] adj;
public LinkGraph(int V) {
this.V = V;
adj = (LinkStack<Integer>[]) new LinkStack[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkStack<>();
}
}
@Override
public int V() {
return V;
}
@Override
public int E() {
return E;
}
@Override
public void addEdge(int v, int w) {
adj[v].push(w);
adj[w].push(v);
E++;
}
@Override
public Iterable<Integer> adj(int v) {
return adj[v];
}
}這裡用到的堆疊程式碼如下所示，堆疊的實作不是這篇部落格的重點，所以這裡不做過多解釋：
package com.zhiyiyo.collection.stack;
import java.util.EmptyStackException;
import java.util.Iterator;
/**
* 使用链表实现的堆栈
*/
public class LinkStack<T> {
private int N;
private Node first;
public void push(T item) {
first = new Node(item, first);
N++;
}
public T pop() throws EmptyStackException {
if (N == 0) {
throw new EmptyStackException();
}
T item = first.item;
first = first.next;
N--;
return item;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
public Iterator<T> iterator() {
return new ReverseIterator();
}
private class Node {
T item;
Node next;
public Node() {
}
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
private class ReverseIterator implements Iterator<T> {
private Node node = first;
@Override
public boolean hasNext() {
return node != null;
}
@Override
public T next() {
T item = node.item;
node = node.next;
return item;
}
@Override
public void remove() {
}
}
}無向圖的遍歷
給定下面一幅圖，現在要求找到每個頂點到頂點0 的路徑，該如何實現？或簡單點，給定頂點 0 和 4，要求判斷從頂點 0 開始走，能否到達頂點 4，如何實現？這就要用到兩種圖的遍歷方式：深度優先搜尋和廣度優先搜尋。
在介紹這兩種遍歷方式之前，先給解決上述問題所需實現的 API：
package com.zhiyiyo.graph;
public interface Search {
/**
* 起点 s 和 顶点 v 之间是否连通
* @param v 顶点 v
* @return 是否连通
*/
boolean connected(int v);
/**
* 返回与顶点 s 相连通的顶点个数（包括 s）
*/
int count();
/**
* 是否存在从起点 s 到顶点 v 的路径
* @param v 顶点 v
* @return 是否存在路径
*/
boolean hasPathTo(int v);
/**
* 从起点 s 到顶点 v 的路径，不存在则返回 null
* @param v 顶点 v
* @return 路径
*/
Iterable<Integer> pathTo(int v);
}深度优先搜索
深度优先搜索的思想类似树的先序遍历。我们从顶点 0 开始，将它的相邻顶点 2、1、5 加到栈中。接着弹出栈顶的顶点 2，将它相邻的顶点 0、1、3、4 添加到栈中，但是写到这你就会发现一个问题：顶点 0 和 1明明已经在栈中了，如果还把他们加到栈中，那这个栈岂不是永远不会变回空。所以还需要维护一个数组 boolean[] marked，当我们将一个顶点 i 添加到栈中时，就将 marked[i] 置为 true，这样下次要想将顶点 i 加入栈中时，就得先检查一个 marked[i] 是否为 true，如果为 true 就不用再添加了。重复栈顶节点的弹出和节点相邻节点的入栈操作，直到栈为空，我们就完成了顶点 0 可达的所有顶点的遍历。
为了记录每个顶点到顶点 0 的路径，我们还需要一个数组 int[] edgeTo。每当我们访问到顶点 u 并将其一个相邻顶点 i 压入栈中时，就将 edgeTo[i] 设置为 u，说明要想从顶点i 到达顶点 0，需要先回退顶点 u，接着再从顶点 edgeTo[u] 处获取下一步要回退的顶点直至找到顶点 0。
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;
public class DepthFirstSearch implements Search {
private boolean[] marked;
private int[] edgeTo;
private Graph graph;
private int s;
private int N;
public DepthFirstSearch(Graph graph, int s) {
this.graph = graph;
this.s = s;
marked = new boolean[graph.V()];
edgeTo = new int[graph.V()];
dfs();
}
/**
* 递归实现的深度优先搜索
*
* @param v 顶点 v
*/
private void dfs(int v) {
marked[v] = true;
N++;
for (int i : graph.adj(v)) {
if (!marked[i]) {
edgeTo[i] = v;
dfs(i);
}
}
}
/**
* 堆栈实现的深度优先搜索
*/
private void dfs() {
Stack<Integer> vertexes = new LinkStack<>();
vertexes.push(s);
marked[s] = true;
while (!vertexes.isEmpty()) {
Integer v = vertexes.pop();
N++;
// 将所有相邻顶点加到堆栈中
for (Integer i : graph.adj(v)) {
if (!marked[i]) {
edgeTo[i] = v;
marked[i] = true;
vertexes.push(i);
}
}
}
}
@Override
public boolean connected(int v) {
return marked[v];
}
@Override
public int count() {
return N;
}
@Override
public boolean hasPathTo(int v) {
return connected(v);
}
@Override
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new LinkStack<>();
int vertex = v;
while (vertex != s) {
path.push(vertex);
vertex = edgeTo[vertex];
}
path.push(s);
return path;
}
}广度优先搜索
广度优先搜索的思想类似树的层序遍历。与深度优先搜索不同，从顶点 0 出发，广度优先搜索会先处理完所有与顶点 0 相邻的顶点 2、1、5 后，才会接着处理顶点 2、1、5 的相邻顶点。这个搜索过程就是一圈一圈往外扩展、越走越远的过程，所以可以用来获取顶点 0 到其他节点的最短路径。只要将深度优先搜索中的堆换成队列，就能实现广度优先搜索：
package com.zhiyiyo.graph;
import com.zhiyiyo.collection.queue.LinkQueue;
public class BreadthFirstSearch implements Search {
private boolean[] marked;
private int[] edgeTo;
private Graph graph;
private int s;
private int N;
public BreadthFirstSearch(Graph graph, int s) {
this.graph = graph;
this.s = s;
marked = new boolean[graph.V()];
edgeTo = new int[graph.V()];
bfs();
}
private void bfs() {
LinkQueue<Integer> queue = new LinkQueue<>();
marked[s] = true;
queue.enqueue(s);
while (!queue.isEmpty()) {
int v = queue.dequeue();
N++;
for (Integer i : graph.adj(v)) {
if (!marked[i]) {
edgeTo[i] = v;
marked[i] = true;
queue.enqueue(i);
}
}
}
}
}队列的实现代码如下：
package com.zhiyiyo.collection.queue;
import java.util.EmptyStackException;
public class LinkQueue<T> {
private int N;
private Node first;
private Node last;
public void enqueue(T item) {
Node node = new Node(item, null);
if (++N == 1) {
first = node;
} else {
last.next = node;
}
last = node;
}
public T dequeue() throws EmptyStackException {
if (N == 0) {
throw new EmptyStackException();
}
T item = first.item;
first = first.next;
if (--N == 0) {
last = null;
}
return item;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private class Node {
T item;
Node next;
public Node() {
}
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}以上是如何用Java實現無向圖？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
如何將Maven或Gradle用於高級Java項目管理，構建自動化和依賴性解決方案？Mar 17, 2025 pm 05:46 PM本文討論了使用Maven和Gradle進行Java項目管理，構建自動化和依賴性解決方案，以比較其方法和優化策略。
如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫（JAR文件）？Mar 17, 2025 pm 05:45 PM本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫（JAR文件）的創建和使用。
如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存？Mar 17, 2025 pm 05:44 PM本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置，集成和績效優勢，以及配置和驅逐政策管理最佳PRA
如何將JPA（Java持久性API）用於具有高級功能（例如緩存和懶惰加載）的對象相關映射？Mar 17, 2025 pm 05:43 PM本文討論了使用JPA進行對象相關映射，並具有高級功能，例如緩存和懶惰加載。它涵蓋了設置，實體映射和優化性能的最佳實踐，同時突出潛在的陷阱。[159個字符]
Java的類負載機制如何起作用，包括不同的類載荷及其委託模型？Mar 17, 2025 pm 05:35 PMJava的類上載涉及使用帶有引導，擴展程序和應用程序類負載器的分層系統加載，鏈接和初始化類。父代授權模型確保首先加載核心類別，從而影響自定義類LOA
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
SublimeText3漢化版
中文版，非常好用
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合，這些清單在安全評估過程中經常使用，而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表，幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上，他就可以存取所需的每種類型的清單。
Dreamweaver Mac版
視覺化網頁開發工具
PhpStorm Mac 版本
最新（2018.2.1 ）專業的PHP整合開發工具
