[数据结构与算法]（基于Java）算法笔记——数据结构(图)

数据结构(图)算法简略记录

1、引言

图是树的升级版（树是相连无相无环图）

• 有向图
• 无向图
• 有循环
• 无循环
• 所有节点相连
• 所有节点不相连

图通常有两种表示方法，假设图中有n个节点，m条边

• 邻接矩阵：
  • 建立一个 n x n矩阵G，如果第i个节点连向第j个节点，则G[i][j]=1，反之为0
  • 如果图是无向的，则该邻接矩阵一定是对称矩阵，即G[i][j]=G[j][i]
• 邻接链表：
  • 建立一个大小为n的数组，每个位置i储存一个数组或链表，表示第i个节点连向其他节点
• 邻接矩阵 比 邻接链表 空间开销大，但是支持快速查找 i 和 j 是否相连

2、二分图

二分图算法也称为染色法，是一种广度优先搜索

• 若可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么图为二分
• 特点：所有点将被分成独立的集合；每条边两端的点一定属于不同集合；可能存在孤点

① LeetCode 785 判断二分图

解题思路

• 将判断是否为二分图转换为给图上色
• 进行遍历，判断当前顶点的邻点是否上色；是否与当前顶点的颜色相同

Java解答

// 深度遍历
class Solution {
    public static final int UNCOLORED = 0;
    public static final int RED = 1;
    public static final int GREEN = 2;
    private int[] color;
    private boolean valid;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        valid = true;
        color = new int[n];
        Arrays.fill(color, UNCOLORED);
        for (int i = 0; i < n && valid; i++) {
            if (color[i] == UNCOLORED) {
                dfs(i, RED, graph);
            }
        }
        return valid;
    }

        private void dfs(int node, int c, int[][] graph) {
            color[node] = c;
            int cNei = c == RED ? GREEN : RED;
            for (int neighbor : graph[node]) {
                if (color[neighbor] == UNCOLORED) {
                    dfs(neighbor, cNei, graph);
                    if (!valid) {
                        return;
                    }
                } else if (color[neighbor] != cNei) {
                    valid = false;
                    return;
                }
            }
        }
    }

// 广度遍历
class Solution {
    public static final int UNCOLORED = 0;
    public static final int RED = 1;
    public static final int GREEN = 2;
    private int[] color;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new int[n];
        Arrays.fill(color, UNCOLORED);
        for (int i = 0; i < n; i++) {
            if (color[i] == UNCOLORED) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                color[i] = RED;
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    int cNei = color[node] == RED ? GREEN : RED;
                    for (int neighbor : graph[node]) {
                        if (color[neighbor] == UNCOLORED) {
                            queue.offer(neighbor);
                            color[neighbor] = cNei;
                        } else if (color[neighbor] != cNei) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

3、拓扑排序

拓扑排序（Topological sort）：对有向无环图排序的算法，将图中N个节点排序成一个线性序列。

① LeetCode 210 课程表 II

解题思路

• 拓扑排序，可以进行遍历，判断每个节点的入度、出度数，入度最少的在最前面

Java解答

// 广度遍历
class Solution {
      // 存储有向图
      List<List<Integer>> edges;
      // 存储每个节点的入度
      int[] indeg;
      // 存储答案
      int[] result;
      // 答案下标
      int index;

      public int[] findOrder(int numCourses, int[][] prerequisites) {
          edges = new ArrayList<List<Integer>>();
          for (int i = 0; i < numCourses; ++i) {
              edges.add(new ArrayList<Integer>());
          }
          indeg = new int[numCourses];
          result = new int[numCourses];
          index = 0;
          for (int[] info : prerequisites) {
              edges.get(info[1]).add(info[0]);
              ++indeg[info[0]];
          }

          Queue<Integer> queue = new LinkedList<Integer>();
          // 将所有入度为 0 的节点放入队列中
          for (int i = 0; i < numCourses; ++i) {
              if (indeg[i] == 0) {
                  queue.offer(i);
              }
          }

          while (!queue.isEmpty()) {
              // 从队首取出一个节点
              int u = queue.poll();
              // 放入答案中
              result[index++] = u;
              for (int v: edges.get(u)) {
                  --indeg[v];
                  // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                  if (indeg[v] == 0) {
                      queue.offer(v);
                  }
              }
          }

          if (index != numCourses) {
              return new int[0];
          }
          return result;
      }
  }