【数据结构】图论入门 - ToB企服应用市场:ToB评测及商务社交产业平台

为1，防止被多次访问
深度优先搜索（DFS）

方法：

在访问图中某一起始顶点v后，由v出发，访问它的任一毗邻顶点w1
再由w1出发访问与w1毗邻，但还未被访问过的顶点w2
然后再从w2出发进行雷同的访问…
如此进行下去，直至到达所有的毗邻顶点都被访问过的顶点u为止
接着退回一步退到前一次刚访问过的顶点，看是否还有其他没有被访问的毗邻顶点
如果有则访问此顶点，之后再从此顶点出发，进行与之前雷同的访问
如果没有就再退回一步进行搜索，重复上述过程，直到连通图中所有顶点都被访问过为止

留意：

稠密图适于在毗邻矩阵上进行深度遍历
稀疏图适于在毗连表上进行深度遍历

对于毗邻矩阵的代码演示：

public class GraphAdjacencyMatrix {
private int V; // 顶点的数量
private int[][] matrix; // 邻接矩阵
private boolean[] visited;
// 构造函数
public GraphAdjacencyMatrix(int v) {
V = v;
matrix = new int[v][v];
visited = new boolean[v];
for (int i = 0; i < v; i++) {
visited[i] = false;
}
}
// 添加边
public void addEdge(int v, int w, int weight) {
matrix[v][w] = weight; // 因为是无向图，所以需要添加两个方向的边
matrix[w][v] = weight;
}
//深度优先遍历
private void DFS(int v) {
visited[v] = true;
System.out.print(v + " ");
for (int i = 0; i < V; i++) {
if (matrix[v][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
// 遍历所有顶点（如果顶点未访问，则进行DFS）
public void DFSTraversal() {
for (int i = 0; i < V; i++) {
if (!visited[i]) {
DFS(i); // 从顶点i开始DFS
}
}
}
// 打印图
public void printGraph() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (matrix[i][j] == 0) {
System.out.print("0 ");
} else {
System.out.print(matrix[i][j] + " ");
}
}
System.out.println();
}
}
}

复制代码

public class linjiejuzhen {
public static void main(String[] args) {
GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(4);
graph.addEdge(0, 1, 10); // 添加边 0-1 权重为 10
graph.addEdge(0, 2, 6);
graph.addEdge(1, 2, 4);
graph.addEdge(2, 3, 1);
System.out.println("Adjacency Matrix:");
graph.printGraph();
System.out.println("Depth First Traversal starting from vertex 0: ");
graph.DFSTraversal(); //0 1 2 3
}
}

复制代码

Adjacency Matrix:
0 10 6 0
10 0 4 0
6 4 0 1
0 0 1 0
Depth First Traversal starting from vertex 0:
0 1 2 3

复制代码

对于毗邻表代码演示：

import java.util.Iterator;
import java.util.LinkedList;
public class DirectedGraphAdjacencyList {
private int V; // 顶点的数量
private LinkedList<Integer> adj[];
private boolean visited[]; // 邻接表
// 构造函数
public DirectedGraphAdjacencyList(int v) {
V = v;
adj = new LinkedList[v];
visited = new boolean[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
visited[i] = false;
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w); // 添加从顶点v到顶点w的有向边
}
// 打印图
public void printGraph() {
for (int i = 0; i < V; i++) {
System.out.print("Vertex " + i + ":");
Iterator<Integer> it = adj[i].iterator();
while (it.hasNext()) {
System.out.print(" -> " + it.next());
}
System.out.println();
}
}
private void DFS(int v) {
visited[v] = true;
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
DFS(n); // 递归访问未访问的邻接顶点
}
}
}
// 遍历所有顶点执行DFS
public void DFSTraversal() {
for (int i = 0; i < V; i++) {
if (!visited[i]) {
DFS(i); // 从顶点i开始DFS
}
}
}
}

复制代码

public class DirectedGraphAdjacency {
public static void main(String[] args) {
DirectedGraphAdjacencyList graph = new DirectedGraphAdjacencyList(6);
// 添加有向边
graph.addEdge(5, 0);
graph.addEdge(5, 3);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
graph.addEdge(1, 3);
System.out.println("Adjacency List Representation of Directed Graph:");
graph.printGraph();
System.out.println("Depth First Traversal starting from vertex 0: ");
graph.DFSTraversal(); //0 1 3 2 4 5
}
}

复制代码

Adjacency List Representation of Directed Graph:
Vertex 0:
Vertex 1: -> 3
Vertex 2: -> 3
Vertex 3: -> 1
Vertex 4: -> 0 -> 1
Vertex 5: -> 0 -> 3
Depth First Traversal starting from vertex 0:
0 1 3 2 4 5

复制代码

广度优先搜索（BFS）

方法：
从图的某一结点出发，首先依次访问该结点的所有毗邻结点 Vi1、Vi2……Vin，再按这些顶点被访问的先后次序依次访问与他们相毗邻的所有未被访问的顶点。重复此过程，直至所有顶点均被访问为止
对于毗邻矩阵的代码演示

import java.util.LinkedList;
import java.util.Queue;
public class DirectedGraphAdjacencyMatrix {
private int V; // 顶点的数量
private int[][] matrix; // 邻接矩阵
private boolean[] visited;
// 构造函数
public DirectedGraphAdjacencyMatrix(int v) {
V = v;
matrix = new int[v][v];
visited = new boolean[v];
// 初始化矩阵，所有元素都设置为0，表示没有边
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
matrix[i][j] = 0;
}
visited[i] = false;
}
}
// 添加边
public void addEdge(int v, int w, int weight) {
matrix[v][w] = weight; // 只在矩阵的对应位置添加边的权重
}
// 打印图
public void printGraph() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (matrix[i][j] == 0) {
System.out.print(" 0 ");
} else {
System.out.print(" " + matrix[i][j] + " ");
}
}
System.out.println();
}
}
//广度优先搜索
public void BFS(int start) {
Queue<Integer> queue = new LinkedList<>();
visited[start] = true; // 标记起始顶点为已访问
queue.add(start); // 将起始顶点添加到队列中
while (!queue.isEmpty()) {
int v = queue.poll(); // 从队列中取出一个顶点
System.out.print(v + " ");
for (int i = 0; i < V; i++) {
if (matrix[v][i] != 0 && !visited[i]) {
visited[i] = true; // 标记邻接顶点为已访问
queue.add(i); // 将邻接顶点添加到队列中
}
}
}
}
}

复制代码

public class linjiejuzhenYou {
public static void main(String[] args) {
DirectedGraphAdjacencyMatrix graph = new DirectedGraphAdjacencyMatrix(4);
graph.addEdge(0, 1, 10); // 添加有向边 0->1 权重为 10
graph.addEdge(0, 2, 6);
graph.addEdge(1, 2, 4);
graph.addEdge(1, 3, 1);
graph.addEdge(2, 3, 7);
System.out.println("Directed Adjacency Matrix:");
graph.printGraph();
System.out.println("Breadth First Traversal starting from vertex 0: ");
graph.BFS(0); //0 1 2 3
}
}

复制代码

Directed Adjacency Matrix:
0 10 6 0
0 0 4 1
0 0 0 7
0 0 0 0
Breadth First Traversal starting from vertex 0:
0 1 2 3

复制代码

对于毗邻表的代码演示

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class UndirectedGraphAdjacencyList {
private int V; // 顶点的数量
private LinkedList<Integer> adj[]; // 邻接表
private boolean[] visited;
// 构造函数
public UndirectedGraphAdjacencyList(int v) {
V = v;
visited = new boolean[V];
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
visited[i] = false;
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w); // 添加从v到w的边
adj[w].add(v); // 因为是无向图，所以需要添加从w到v的边
}
// 打印图
public void printGraph() {
for (int i = 0; i < V; i++) {
System.out.print("Vertex " + i + ":");
Iterator<Integer> it = adj[i].iterator();
while (it.hasNext()) {
System.out.print(" -> " + it.next());
}
System.out.println();
}
}
public void BFS(int start) {
Queue<Integer> queue = new LinkedList<>();
visited[start] = true; // 标记起始顶点为已访问
queue.add(start); // 将起始顶点添加到队列中
while (!queue.isEmpty()) {
int v = queue.poll(); // 从队列中取出一个顶点
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true; // 标记邻接顶点为已访问
queue.add(n); // 将邻接顶点添加到队列中
}
}
}
}
}

复制代码

public class UndirectedGraphAdjacency {
public static void main(String[] args) {
UndirectedGraphAdjacencyList graph = new UndirectedGraphAdjacencyList(4);
graph.addEdge(0, 1); // 添加边 0-1
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
System.out.println("Adjacency List Representation of Undirected Graph:");
graph.printGraph();
System.out.println("Breadth First Traversal starting from vertex 0: ");
graph.BFS(0); //0 1 2 3
}
}

复制代码

Adjacency List Representation of Undirected Graph:
Vertex 0: -> 1 -> 2
Vertex 1: -> 0 -> 2
Vertex 2: -> 0 -> 1 -> 3
Vertex 3: -> 2
Breadth First Traversal starting from vertex 0:
0 1 2 3

复制代码

二者搜索的算法分析

时间复杂度：
毗邻矩阵：
对于毗邻矩阵表现的图，时间复杂度重要受两个因素影响：

矩阵大小：毗邻矩阵的大小为

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4