java - 如何在 Java 中实现二分图？

Question

更新

到目前为止，一些答案建议使用邻接列表。Java 中的邻接表是什么样子的？...没有正确的指针:)

---

我正在尝试在 Java 中实现一个二分图，以将文件中的信息分类为 2 组。我找到了这个例子，它确实完成了这项工作：

http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html

但是，我想实现我自己的版本...如果您查看我以前的帖子，您就会明白我为什么要自己做这个。

所以我必须读取一个文件，从中我可以很容易地得到顶点的数量，但边的数量并不那么容易。一个示例行是"PersonA PersonB"，可以读作"PersonA says PersonB"。所以阅读这些行...

"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"

...产生这个分组：

{A,D,C} and {B,E}.

我将如何实现这个二分图？什么是这项任务的好资源？在创建 BipartiteGraph 类时，我应该考虑和考虑哪些事情（算法）......也许是遍历/排序算法？

Answer 1

使用邻接列表实现应该非常简单。如果它是一个无向二分图，我可能会建议使用关联矩阵。

因此，对于每个节点，您将拥有一个链表数组，或者某种动态分配列表的数组。它应该使添加边缘相当自然，例如在您的示例中，您有一个边缘：

人A->人B

然后你会去对应于 Person A 的数组索引并推回对应于 Persona B 的索引：

[A 人]= B 人

那么也许你会获得另一个优势

角色 A-> 角色 C

然后您的索引将如下所示：

[人物 A]= 人物 B ，人物 C

作为最后一个示例，这将是示例图的邻接列表：

[甲]乙

[乙] 丁

[C]乙

[D B

[E] A,C

每个索引都有一个可从该节点到达的节点列表。

“在创建 BipartiteGraph 类时，我应该考虑和考虑哪些事情（算法）......也许是遍历/排序算法？”

这真的取决于你想用图表做什么......

供参考：Sun 论坛上与代码类似的问题

有向加权图的邻接列表

Answer 2

试试这个： -

Bipartite.java

/*************************************************************************
 *  Compilation:  javac Bipartite.java
 *  Dependencies: Graph.java 
 *
 *  Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
 *  Runs in O(E + V) time.
 *
 *
 *************************************************************************/

/**
 *  The <tt>Bipartite</tt> class represents a data type for 
 *  determining whether an undirected graph is bipartite or whether
 *  it has an odd-length cycle.
 *  The <em>isBipartite</em> operation determines whether the graph is
 *  bipartite. If so, the <em>color</em> operation determines a
 *  bipartition; if not, the <em>oddCycle</em> operation determines a
 *  cycle with an odd number of edges.
 *  <p>
 *  This implementation uses depth-first search.
 *  The constructor takes time proportional to <em>V</em> + <em>E</em>
 *  (in the worst case),
 *  where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
 *  Afterwards, the <em>isBipartite</em> and <em>color</em> operations
 *  take constant time; the <em>oddCycle</em> operation takes time proportional
 *  to the length of the cycle.
 */
public class Bipartite {
    private boolean isBipartite;   // is the graph bipartite?
    private boolean[] color;       // color[v] gives vertices on one side of bipartition
    private boolean[] marked;      // marked[v] = true if v has been visited in DFS
    private int[] edgeTo;          // edgeTo[v] = last edge on path to v
    private Stack<Integer> cycle;  // odd-length cycle

    /**
     * Determines whether an undirected graph is bipartite and finds either a
     * bipartition or an odd-length cycle.
     * @param G the graph
     */
    public Bipartite(Graph G) {
        isBipartite = true;
        color  = new boolean[G.V()];
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];

        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
        assert check(G);
    }

    private void dfs(Graph G, int v) { 
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if odd-length cycle found
            if (cycle != null) return;

            // found uncolored vertex, so recur
            if (!marked[w]) {
                edgeTo[w] = v;
                color[w] = !color[v];
                dfs(G, w);
            } 

            // if v-w create an odd-length cycle, find it
            else if (color[w] == color[v]) {
                isBipartite = false;
                cycle = new Stack<Integer>();
                cycle.push(w);  // don't need this unless you want to include start vertex twice
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
            }
        }
    }

    /**
     * Is the graph bipartite?
     * @return <tt>true</tt> if the graph is bipartite, <tt>false</tt> otherwise
     */
    public boolean isBipartite() {
        return isBipartite;
    }

    /**
     * Returns the side of the bipartite that vertex <tt>v</tt> is on.
     * param v the vertex
     * @return the side of the bipartition that vertex <tt>v</tt> is on; two vertices
     *    are in the same side of the bipartition if and only if they have the same color
     * @throws UnsupportedOperationException if this method is called when the graph
     *    is not bipartite
     */
    public boolean color(int v) {
        if (!isBipartite)
            throw new UnsupportedOperationException("Graph is not bipartite");
        return color[v];
    }

    /**
     * Returns an odd-length cycle if the graph is not bipartite, and
     * <tt>null</tt> otherwise.
     * @return an odd-length cycle (as an iterable) if the graph is not bipartite
     *    (and hence has an odd-length cycle), and <tt>null</tt> otherwise
     */
    public Iterable<Integer> oddCycle() {
        return cycle; 
    }

    private boolean check(Graph G) {
        // graph is bipartite
        if (isBipartite) {
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (color[v] == color[w]) {
                        System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                        return false;
                    }
                }
            }
        }

        // graph has an odd-length cycle
        else {
            // verify cycle
            int first = -1, last = -1;
            for (int v : oddCycle()) {
                if (first == -1) first = v;
                last = v;
            }
            if (first != last) {
                System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                return false;
            }
        }

        return true;
    }

    /**
     * Unit tests the <tt>Bipartite</tt> data type.
     */
    public static void main(String[] args) {
        // create random bipartite graph with V vertices and E edges; then add F random edges
        int V = Integer.parseInt(args[0]);
        int E = Integer.parseInt(args[1]);
        int F = Integer.parseInt(args[2]);

        Graph G = new Graph(V);
        int[] vertices = new int[V];
        for (int i = 0; i < V; i++) vertices[i] = i;
        StdRandom.shuffle(vertices);
        for (int i = 0; i < E; i++) {
            int v = StdRandom.uniform(V/2);
            int w = StdRandom.uniform(V/2);
            G.addEdge(vertices[v], vertices[V/2 + w]);
        }

        // add F extra edges
        for (int i = 0; i < F; i++) {
            int v = (int) (Math.random() * V);
            int w = (int) (Math.random() * V);
            G.addEdge(v, w);
        }

        StdOut.println(G);

        Bipartite b = new Bipartite(G);
        if (b.isBipartite()) {
            StdOut.println("Graph is bipartite");
            for (int v = 0; v < G.V(); v++) {
                StdOut.println(v + ": " + b.color(v));
            }
        }
        else {
            StdOut.print("Graph has an odd-length cycle: ");
            for (int x : b.oddCycle()) {
                StdOut.print(x + " ");
            }
            StdOut.println();
        }
    }
}

Answer 3

这是 c# 实现，但这个概念也可以在 Java 中使用。我使用邻接矩阵来表示图形。检查图中是否有一个循环奇数循环。

如果您考虑下图 1,2,3,4,5,6，则如果该图中存在分区说 u 和 v 其中 (u union v) = Graph 并且 (u intersection v) = null ，则该图称为 Bipartite ,7 是图 G 中的顶点。让我们将左侧 (1,4,5,6) 的顶点视为 U，将右侧 (2,3,7) 的顶点视为 V

考虑现在图表中没有红色连接。您可以看到从 u 到 v 和从 v 到 u 的连接是一个无向图。但在分区中没有任何联系。这就是我要使用的概念。

考虑如下所示的图表，它与上面的图表相同，只是它的绘制更像树形结构。在这种情况下，如果您可以看到交替级别上存在的节点 1、3、5 可以一起形成一个分区，而 2,4 可以形成另一个分区。所以我们可以很容易地说这个图是 BiPartite。如果同一级别的元素之间存在红边怎么办？那么图不是二分图。如果你可以修改 BFS 算法，我们可以实现这一点。

这是代码。

   int[,] BPGraph = new int[7,7]{
                                    {0,1,0,1,0,0,0},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {1,0,1,0,1,1,0},
                                    {0,1,0,1,0,0,1},
                                    {0,1,0,1,0,0,1},
                                    {0,0,1,0,1,1,0}
                                };

    int[] BPArray = new int[7] { 0, 0, 0, 0, 0, 0, 0 };

    public Boolean BiPartite()
    {
        Queue<int> VertexQueue = new Queue<int>();
        int level = 0;
        int nextlevel=0;
        Boolean BPFlg = true;

        VertexQueue.Enqueue(0);

        while(VertexQueue.Count!=0)
        {
            int current = VertexQueue.Dequeue();
            level = BPArray[current];

            if (level == 0)
                level = 1;

            if (level == 2)
                nextlevel=1;
            else
                nextlevel=2;

            if(BPArray[current]==0) 
                BPArray[current] = level;

            for (int i = 0; i < 7; i++)
            {
                if (BPGraph[current, i] == 1)
                {
                    if (BPArray[i] == 0)
                    {
                        BPArray[i] = nextlevel;
                        VertexQueue.Enqueue(i);
                    }
                    else if (BPArray[i] == level)
                    {
                        BPFlg = false;
                        break;
                    }
                }
            }
            if (!BPFlg)
                break;
        }
        return BPFlg;

    }

Answer 4

有向图是连接节点 A 和 B 的边有方向的图。如果从 A 到 B 有一条边，这并不意味着从 B 到 A 有一条边。在您的示例中，边有方向。（B 到 D 将是两条边，一条从 B 到 D，一条从 D 到 B。）

实现这一点的一种方法是与链表类似的方式，节点在适当时相互引用。回顾您的示例，nodeA将引用nodeB，但不是相反。nodeE将引用nodeAand nodeC，依此类推。您实际上是在创建一种（某种）数据结构，它具有节点的概念，可能还有边。有很多方法可以解决。

一个可能的 Java 实现将有一个名为的类AdjacencyList，该类Map<Vertex, List<Vertex>>包含一个顶点及其相邻顶点。 AdjacencyList然后将有能力在其地图上执行操作。

至于算法和要记住的事情，请查看Wikipedia上二分图的属性，特别是

• 一个图是二分的当且仅当它不包含奇数循环。因此，二分图不能包含大小为 3 或更大的团。
• 每棵树都是二分的。
• 具有偶数个顶点的循环图是二分的。

一个很好的测试是实现一个 2-coloring 算法来确认图确实是二分的。深度优先搜索、广度优先搜索是很好的实现练习。

Answer 5

1.) 选择随机节点。把它放在二分图的“左边”。

2.）选择与您在1中选择的节点相邻的所有节点，并将它们全部放在“右侧”。

3.）其余节点都属于二分图的“左侧”。

结尾