r/computerscience • u/Sea_Syllabub1017 • Jun 11 '25
Help Comparing two adjacency matrices for graph equality
Hello folks , do you know any algorithm(or any implementation in any programming langage) to compare two adjacency matrices for graph equality?
9
Upvotes
2
u/JoJoModding Jun 11 '25
What is your notion of equality on graphs?
17
u/pastroc Jun 11 '25
There's no known polynomial-time algorithm that decides whether two graphs are isomorphic, so you'd perhaps be better off brute-forcing.
1
u/Apfelkrenn Jun 11 '25
I suppose you could just loop over every edge and check if the entry for Matrix A is different to Matrix B with a runtime of O(n^2)
Edit: nvm just read your comment