数据结构第13节 无向图

无向图是图论中的一个基本概念，它是数学和计算机科学中用来描述一组对象（顶点）以及它们之间的成对关系（边）的结构。在无向图中，边是没有方向的，这意味着边所连接的两个顶点可以互相访问。

定义

无向图 ( G ) 可以定义为一个有序对 ( G=(V,E) )，其中：

• ( V ) 是顶点的集合，也称作节点的集合。
• ( E ) 是边的集合，边是 ( V ) 中顶点的无序对，表示两个顶点之间的连接。

术语

• 顶点：图中的基本单位，通常用字母 ( v ) 或 ( u ) 表示。
• 边：连接顶点的线段，表示两个顶点之间的关系，通常用 ( e ) 表示。
• 度数：一个顶点的度数是与该顶点相邻的所有边的数量。
• 路径：一系列顶点和边，使得每个边都连接路径中的连续两个顶点。
• 简单路径：路径中不重复经过任何顶点。
• 环：闭合路径，起点和终点相同。
• 连通性：如果图中任意两个顶点之间都存在路径，则称该图为连通图。
• 连通分量：无向图中的最大连通子图，彼此之间没有边相连。

图的表示

无向图可以用以下几种方式表示：

• 邻接矩阵：一个 ( |V| \times |V| ) 的矩阵，其中第 ( i ) 行第 ( j ) 列的元素为 1 如果顶点 ( i ) 和顶点 ( j ) 之间有一条边，否则为 0。
• 邻接列表：对于每个顶点，维护一个链表，包含与之直接相连的所有顶点。

应用

无向图在许多领域有应用，如：

• 社交网络：顶点可以代表人，边可以代表朋友关系。
• 互联网：网页作为顶点，超链接作为边。
• 电路设计：顶点可以是电路元件，边可以是连接导线。
• 地图和道路网络：顶点可以是城市或交叉口，边可以是道路。
• 化学分子结构：顶点可以是原子，边可以是化学键。

算法

处理无向图的一些常见算法包括：

• 深度优先搜索 (DFS)：从某个顶点开始，尽可能深入地探索每条路径。
• 广度优先搜索 (BFS)：从某个顶点开始，探索所有离起点等距离的顶点。
• 最小生成树算法：如Prim算法或Kruskal算法，用于在加权图中找到一棵包含所有顶点的最小权重的树。
• 连通性检测：确定图是否连通，或找出所有连通分量。

无向图是理解和解决许多复杂问题的基础工具。在实际应用中，无向图可以转化为有向图或加权图以适应更复杂的关系和需求。

在Java中，我们可以使用邻接矩阵或邻接列表来表示无向图。下面是一个使用邻接列表的例子：

import java.util.*;

public class Graph {
    private final int V;   // Number of vertices
    private LinkedList<Integer> adj[]; //Adjacency List

    // Constructor
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    //Function to add an edge into the graph
    void addEdge(int v,int w) {
        adj[v].add(w); // Add w to v’s list.
        adj[w].add(v); // Since graph is undirected, add v to w's list too
    }

    // Function to print the graph
    void printGraph() {
        for (int v = 0; v < V; ++v) {
            System.out.println("Adjacency list of vertex "+ v);
            System.out.print("head ");
            Iterator<Integer> it = adj[v].listIterator();
            while (it.hasNext())
                System.out.print(" -> " + it.next());
            System.out.println("\n");
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(5);

        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);

        g.printGraph();
    }
}

在这个例子中，我们首先定义了一个Graph类，它有两个私有变量：V（顶点的数量）和adj（邻接列表）。然后我们在构造函数中初始化这些变量。

我们定义了一个addEdge方法来添加边。由于这是一个无向图，所以我们需要在两个顶点的邻接列表中都添加对方。

最后，我们定义了一个printGraph方法来打印图的邻接列表表示。

在main方法中，我们创建了一个Graph对象，并添加了一些边，然后打印出了这个图。

当然，让我们再看一个使用邻接矩阵表示无向图的例子。邻接矩阵是一种二维数组，用于表示图中顶点之间的连接关系。如果图中的两个顶点u和v之间存在一条边，那么邻接矩阵中的元素A[u][v]和A[v][u]的值为1，否则为0。

下面是一个使用邻接矩阵表示无向图的Java代码示例：

public class Graph {
    private final int V;   // No. of vertices
    private int E;         // No. of edges
    private int[][] adj;   // Adjacency Matrix

    // Constructor
    Graph(int v) {
        V = v;
        E = 0;
        adj = new int[V][V];
    }

    // Method to add an edge in a graph
    public void addEdge(int v, int w) {
        if (v >= 0 && v < V && w >= 0 && w < V) {
            adj[v][w] = 1;
            adj[w][v] = 1;
            E++;
        } else {
            throw new IllegalArgumentException("Invalid vertices");
        }
    }

    // Method to print adjacency matrix
    public void printGraph() {
        for (int v = 0; v < V; v++) {
            for (int w = 0; w < V; w++) {
                System.out.print(adj[v][w] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.printGraph();
    }
}

在这个例子中，我们首先定义了一个Graph类，它有三个私有变量：V（顶点的数量），E（边的数量）和adj（邻接矩阵）。然后我们在构造函数中初始化这些变量。

我们定义了一个addEdge方法来添加边。由于这是一个无向图，所以我们需要在邻接矩阵的两个位置上都设置1。

最后，我们定义了一个printGraph方法来打印图的邻接矩阵表示。

在main方法中，我们创建了一个Graph对象，并添加了一些边，然后打印出了这个图的邻接矩阵表示。

让我们通过一个迷宫游戏的例子来理解无向图的应用。在这个游戏中，迷宫可以被看作是一个无向图，其中每个房间都是一个顶点，每个门（连接两个房间的通道）都是一条边。

假设我们有一个迷宫，它由多个房间组成，每个房间都有可能与其他房间相连。我们的目标是找到从起点到终点的路径。这个问题可以通过深度优先搜索（DFS）或广度优先搜索（BFS）在无向图中寻找路径来解决。

以下是一个使用DFS在迷宫（无向图）中寻找路径的Java代码示例：

import java.util.*;

class Maze {
    private final int V;   // Number of rooms
    private LinkedList<Integer> adj[]; //Adjacency List

    // Constructor
    Maze(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    //Function to add a door between two rooms
    void addDoor(int v, int w) {
        adj[v].add(w); // Add w to v’s list.
        adj[w].add(v); // Since maze is undirected, add v to w's list too
    }

    // A recursive function to find path from source 's' to destination 'd'
    boolean DFSUtil(int s, int d, boolean visited[]) {
        visited[s] = true;
        System.out.print(s + " ");

        if (s == d)
            return true;

        Iterator<Integer> i = adj[s].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                if (DFSUtil(n, d, visited))
                    return true;
            }
        }
        return false;
    }

    // Prints shortest path from source 's' to destination 'd'
    void findPath(int s, int d) {
        boolean visited[] = new boolean[V];

        if (DFSUtil(s, d, visited) == false)
            System.out.println("No path exists");

        System.out.println();
    }

    public static void main(String args[]) {
        Maze maze = new Maze(9); // Assume we have 9 rooms

        maze.addDoor(0, 1);
        maze.addDoor(0, 3);
        maze.addDoor(1, 2);
        maze.addDoor(1, 3);
        maze.addDoor(2, 4);
        maze.addDoor(3, 4);
        maze.addDoor(4, 5);
        maze.addDoor(5, 6);
        maze.addDoor(6, 7);
        maze.addDoor(7, 8);

        System.out.println("Path from room 0 to room 8:");
        maze.findPath(0, 8);
    }
}

在这个例子中，我们首先定义了一个Maze类，它有两个私有变量：V（房间的数量）和adj（邻接列表）。然后我们在构造函数中初始化这些变量。

我们定义了一个addDoor方法来添加门。由于这是一个无向图，所以我们需要在两个房间的邻接列表中都添加对方。

我们还定义了一个findPath方法来找到从源房间到目标房间的路径。这个方法使用了深度优先搜索（DFS）算法，并且使用了一个辅助方法DFSUtil来进行递归搜索。

在main方法中，我们创建了一个Maze对象，并添加了一些门，然后找到了从房间0到房间8的路径。