图的常见算法包括深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法(Dijkstra算法和Bellman-Ford算法)、最大流算法(Ford-Fulkerson算法和Edmonds-Karp算法)等。下面给出这些算法的Java示例。
1、深度优先搜索(DFS)
java">public void dfs(int v, boolean[] visited, List<List<Integer>> adjList) {
visited[v] = true;
System.out.print(v + " ");
for (int i = 0; i < adjList.get(v).size(); i++) {
int u = adjList.get(v).get(i);
if (!visited[u]) {
dfs(u, visited, adjList);
}
}
}
2、广度优先搜索(BFS)
java">public void bfs(int s) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[V];
visited[s] = true;
queue.offer(s);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int u : adjList[v]) {
if (!visited[u]) {
visited[u] = true;
queue.offer(u);
}
}
}
}
3、最短路径算法(Dijkstra算法)
java">public double[] dijkstra(int s) {
double[] dist = new double[V];
for (int i = 0; i < V; i++) {
dist[i] = Double.POSITIVE_INFINITY;
}
dist[s] = 0;
boolean[] visited = new boolean[V];
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(s, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int v = node.v;
if (visited[v]) {
continue;
}
visited[v] = true;
for (int u : adjList[v]) {
double d = dist[v] + weight(v, u);
if (dist[u] > d) {
dist[u] = d;
pq.offer(new Node(u, d));
}
}
}
return dist;
}
4、最短路径算法(Bellman-Ford算法)
java">public void bellmanFord(int s) {
double[] dist = new double[V];
for (int i = 0; i < V; i++) {
dist[i] = Double.POSITIVE_INFINITY;
}
dist[s] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < V; j++) {
for (int k = 0; k < adjList[j].size(); k++) {
int u = adjList[j].get(k);
double d = dist[j] + weight(j, u);
if (dist[u] > d) {
dist[u] = d;
} else if (dist[u] == d && rand.nextDouble() < 0.5) { // 处理负权环问题,随机选择一个路径即可。
dist[u] = d;
}
}
}
}
}