Undirected Graph, get list of all nodes that can be visited

Question

I am new into graph theory I have this, problem I have a graph that will be diferent each time, I want to know if there is an algorithm to know from a random node which nodes I can visit, this question came after I read this artcle. text

Example:

	A	B	C	D	E
A	0	0	0	1	0
B	0	0	1	0	0
C	0	1	0	0	0
D	1	0	0	0	1
E	0	0	0	1	0

I want to get the vectors or some way to know that A, D & Eare connected and B & C are conected

I’m really new on the matter hope you can write the answer in a mathematical way or if not in Python, C#, C++ or Javascript

Answer 1

You're looking for finding the components of the graph.

You can use a depth-first traversal and keep track of which nodes you've already marked as belonging to a component.

The algorithm will be more efficient if you represent the graph with an adjacency list, but it can be done with the adjacency matrix you presented in the question.

Here is Python code that assigns to each vertex a component number. Vertices with the same number belong to the same component:

def components(adjacency):
    components = [0] * len(adjacency)
    component = 1

    def findcomponent(vertex):
        if components[vertex] == 0:
            components[vertex] = component
            for neighbor, connected in enumerate(adjacency[vertex]):
                if connected:
                    findcomponent(neighbor)
        
    for vertex, row in enumerate(adjacency):
        for neighbor, connected in enumerate(row):
            if connected and components[neighbor] == 0:
                findcomponent(vertex)
                component += 1

    return components

Here is how you would use that function for your example graph:

adjacency = [
    [0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 1, 0]
]
result = components(adjacency)
print(result)

# If we want to use the names "A", "B",... for the nodes, then:
vertices = [*"ABCDE"]
print(dict(zip(vertices, result)))

The output of the above code will be:

[1, 2, 2, 1, 1]
{'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1}

Both outputs map vertices to their component number: the first just uses the index of each vertex, the second the name of each vertex.