如何在Java中实现两部分图?

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中实现一个两部分的图，从一个文件中对两组信息进行排序。我找到了这个例子，它确实做了这个工作:

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...

所以我必须读取一个文件，我可以很容易地得到顶点的数目，但是边的数目不那么容易。一个示例行是“PersonB”，可以将其解读为“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?

如何实现这个偶图?什么是这个任务的好资源?什么东西(算法)我应该考虑和考虑什么时候创建两部分的类…也许穿越/排序算法?

5 个解决方案

#1

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:

然后你就会得到对应于A的数组索引并将对应于角色B的索引向后推:

[Person A]= Person B

[A]= B

Then maybe you get another edge

也许你会有另一个优势。

Persona A-> Person C

角色- >人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

[一]B

[B] D

[B]D

[C] B

[C]B

[D] B

[D]B

[E] A,C

[E],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?"

“什么东西(算法)我应该考虑和考虑什么时候创建两部分的类……”也许穿越/排序算法?”

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

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

#2

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

#3

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联盟v)=图和(u路口v)= null如果你认为下图1,2,3,4,5,6,7图g的顶点允许考虑左边的顶点(1,4,5,6)右边u和v(2、3、7)

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可以形成另一个分区。所以我们可以很容易地说，这个图是两部分的。如果在相同级别的元素之间有一个红色的边，该怎么办?那么这个图不是两部分。如果你可以修改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;

    }

#4

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, nodeA would have a reference to nodeB, but not the reverse. nodeE would have a reference to nodeA and 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会引用nodeA和nodeC，等等。实际上，您正在创建一个(某种)数据结构，它具有节点和可能边缘的概念。有很多方法可以解决这个问题。

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

一个可能的Java实现将会有一个叫做邻接表的类，它有一个Map <顶点，列表<顶点> >，包含一个顶点和它的相邻顶点。然后，邻接表将有能力在其地图上执行操作。

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

至于算法和要记住的东西，我们来看一下Wikipedia上的两部分图的属性。

• 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.
• 一个图是两部分的，如果且仅当它不包含一个奇循环。因此，两部分图不能包含大小为3或更多的小集团。
• Every tree is bipartite.
• 每棵树是由两部分构成的。
• Cycle graphs with an even number of vertices are bipartite.
• 具有偶数个顶点的循环图是两部分的。

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色算法来确认图形确实是两部分的。深度优先搜索，广度优先搜索是良好的执行实践。

#5

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)。选择所有与您选择的节点相邻的节点，并将它们全部放在“右侧”。

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

3)。其余的节点都属于两部分图的“左”边。

END

结束