1
$\begingroup$

Are there any cases when adjacency matrix should have entries other than 0 and 1?

$\endgroup$
  • 2
    $\begingroup$ This could have been answered just by looking at Wikipedia: for example, the section "variations" gives the example of $(a,b,c)$-adjacency matrices. You are expected to do some basic research before asking questions here. $\endgroup$ – David Richerby Dec 17 '14 at 9:00
7
$\begingroup$

Yes, because the (i,j)th entry simply talks about whether or not there exists an edge from vertex i to vertex j, and represents existence by a 1 and non-existence by a 0.

However, many graph representations store the edge weight instead of 1s in the matrix. This way, a single matrix can compactly represent both the edges and their weights.

$\endgroup$
  • $\begingroup$ Got it, the weights $\endgroup$ – Olórin Dec 17 '14 at 7:53
  • $\begingroup$ Note that, if you want to have an edge whose weight is zero, you can't use a single matrix to represent both the adjacencies and the weight. (Unless you represent non-edges by $-\infty$, but then you can't represent edges with weight $-\infty$ and so on.) $\endgroup$ – David Richerby Dec 17 '14 at 9:01
  • $\begingroup$ ^ Point noted. (Incidentally, I was just going through an OCW lecture where the solution to a problem involved using "dummy" zero-weight edges.) $\endgroup$ – Soham Chowdhury Dec 17 '14 at 9:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.