如何在 Java 中实现二部图？

How do I implement a Bipartite Graph in Java?

提问by Hristo

UPDATE

更新

Some answers so far have suggested using an adjacency list. How would an adjacency list look like in Java? ... no pointers right :)

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

---

---

I'm trying to implement a Bipartite Graph in Java to sort into 2 groups information from a file. I found this example and it actually does the job:

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

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

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

However, I would like to implement my own version... if you look at a previous post of mine, you'd understand why I want to do this myself.

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

So I have to read a file from which I can get the number of vertices easily, but the number of edges not so easily. An example line would be "PersonA PersonB", which can be read as "PersonA says PersonB". So reading these lines...

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

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

... produces this grouping:

...产生这个分组：

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

How would I go about implementing this bipartite graph? What is a good resource for this task? What things (algorithms) should I be considering and thinking about when creating the BipartiteGraph class... perhaps traversing/sorting algorithms?

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

采纳答案by JSchlather

It should be pretty straight forward to implement with an adjacency list. If it were an undirected bipartite graph I might suggest using an incidence matrix.

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

So you'd have an array of linked lists then, or an array of some sort of dynamically allocated list, for each node. It should make adding edges fairly natural, for instance in your example you have an edge:

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

Person A-> Person B

人 A-> 人 B

Then you'd go the array index corresponding to Person A and push back the index corresponding to Persona B:

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

[Person A]= Person B

[A 人]= B 人

Then maybe you get another edge

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

Persona A-> Person C

人物A->人物C

Then your index there would look like:

然后你的索引看起来像：

[Persona A]= Person B , Person C

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

As one last example this would be the adjacency list for your example graph:

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

[A] B

[A] 乙

[B] D

[乙] 丁

[C] B

[C] 乙

[D] B

[D B

[E] A,C

[E] A,C

Each index has a list of the nodes reachable from that node.

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

" What things (algorithms) should I be considering and thinking about when creating the BipartiteGraph class... perhaps traversing/sorting algorithms?"

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

It really depends on what you want to do with the graph...

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

For Reference: Similar Question with Code on Sun Forums

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

adjacency-list-of-a-directed-weighted-graph

有向加权图的邻接表

回答by Saumil Patel

TRY THIS:--

试试这个： -

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();
        }
    }
}

回答by Kartik

This is c# implementation but the concept can be used in Java also. I used Adjacency Matrix to represent graph. Checking if there is a cycle an odd cycle in the graph.

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

A Graph is called Bipartite if there exist a partition in that graph say u and v where (u union v) = Graph and (u intersection v ) = null if you consider the picture below 1,2,3,4,5,6,7 are the vertices in the graph G. lets consider the vertices on the left (1,4,5,6) as U and on the right (2,3,7) as V

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

Consider there is no red connection in the graph for now. You could see there is a connection from u to v and v to u as its a undirected graph. but there is no connection with in the partition. That is the concept am going to use.

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

Consider the graph as shown below its the same graph above, except its drawn more like a tree structure. In this case if you can see the nodes present on the alternate levels 1,3,5 can together form a partition and 2,4 can form another partition. So we could easily say the graph is BiPartite. What if there is a red edge between the elements on the same level? then the graph is not bipartite.If you are could modify the BFS algorithm we can achieve this.

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

Here is the code for that.

这是代码。

   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;

    }

回答by Emanuel Saringan

1.) Choose random node. Put it in the "left" side of the bipartite graph.

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

2.) Choose all nodes adjacent to the node you selected in 1 and put them all at the "right" side.

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

3.) The remaining nodes all belong to the "left" side of the bipartite graph.

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

END

结尾

回答by Feanor

A directed graph is one in which an edge connecting nodes A and B has a direction; if there is an edge from A to B, this does not mean there is an edge from B to A. In your example, the edges have direction. (B to D would be two edges, one from B to D and one from D to B.)

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

One way to implement this would be in a similar way to a linked list, with nodes having references to each other as appropriate. Referring back to your example, nodeAwould have a reference to nodeB, but not the reverse. nodeEwould have a reference to nodeAand nodeC, and so on. You're really creating a (sort of) data structure, which has a notion of nodes and perhaps edges. There are a number of ways you could go about it.

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

A possible Java implementation would be having a class called AdjacencyListthat has a Map<Vertex, List<Vertex>>containing a vertex and its adjacent vertices. AdjacencyListwould then have the ability to perform operations on its Map.

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

As for algorithms and things to keep in mind, take a look at the properties of bipartite graphs on Wikipedia, particularly

至于算法和要记住的事情，看看维基百科上二部图的属性，特别是

• A graph is bipartite if and only if it does not contain an odd cycle. Therefore, a bipartite graph cannot contain a clique of size 3 or more.
• Every tree is bipartite.
• Cycle graphs with an even number of vertices are bipartite.

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

A good test would be implementing a 2-coloring algorithm to confirm that the graph is indeed bipartite. Depth first search, breadth first search are good exercises of the implementation.

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