如何列出非连接图的连接顶点

Question

示例 - 有一个不连通的图，顶点
A - B - C - D 和 E - F - G。（连字符表示它们是连通的）。
下面的代码使用的是深度优先遍历，我需要修改它以显示所有连接的顶点。例如：
列表 0：ABCD
列表 1：EFG
ETC... 我不明白如何实现这个。

public class Graph {
    private final int MAX_VERTS = 20;
    private Vertex vertexList[];
    private int matrix[][];
    private int countV;
    private StackX theStack;

    // ------------------------------------------------------------
    public Graph() {
        vertexList = new Vertex[MAX_VERTS];
        matrix = new int[MAX_VERTS][MAX_VERTS];
        countV = 0;
        for (int x = 0; x < MAX_VERTS; x++)
            for (int y = 0; y < MAX_VERTS; y++)
                matrix[x][y] = 0;
        theStack = new StackX();
    }

    // -------------------------------------------------------------
    public void addVertex(char label) {
        vertexList[countV++] = new Vertex(label);
    }

    // -------------------------------------------------------------
    public void addEdge(int x, int y) {
        matrix[x][y] = 1;
        matrix[y][x] = 1;
    }

    // -------------------------------------------------------------
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label);
    }

    public void dfs() {

        vertexList[0].wasVisited = true;
        displayVertex(0);
        theStack.push(0);


        while (!theStack.isEmpty()) {
            int v = getUnvisitedVertex(theStack.peek());
            if (v == -1)
                theStack.pop();
            else
            {
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }

        for (int j = 0; j < countV; j++)
            vertexList[j].wasVisited = false;
    }

    // ------------------------------------------------------------
    public int getUnvisitedVertex(int vertex) {
        for (int j = 0; j < countV; j++)
            if (matrix[vertex][j] == 1 && !vertexList[j].wasVisited) {
                return j;
            }

        return -1;
    }
}

Answer 1

你的DFS不需要修改。它需要放在一个循环中，以便每次通过都会发现您正在寻找的连接节点列表之一

LOOP
    Select arbitrary vertex
    DFS, saving each visited vertex in list.
    LOOP over visited vertices
       remove from graph
    LOOP END
    IF all vertices removed
       BREAK out of loop
    Start new list
LOOP END
Output lists

如何列出非连接图的连接顶点

How to list connected vertices of a non-connected graph

java

graph-theory