Graph representation?


  • 36
    P

    Problem statement says that this is an undirected graph, but how does the adjacency list correspond to it?
    {0,1,2#1,2#2,2}
    means that adjacency list for the give graph is:

    0   1, 2
    1   2
    2   2
    

    In an undirected graph, adjacency list for 1 should contain 0 as well, and 2 should contain 0 and 1. What I would expect is:

    0   1, 2
    1   2, 0
    2   2, 0, 1
    

    The first representation looks like directed graph, because there is an edge 0->1 but not 1->0.


  • 20
    L

    I am not sure wether you understand correctly the problem or not. In this problem, the graph is not given by an adjacency list or an adjacency matrix as you are describing. We are dealing here with a graph of objects. Each object contains a list of its neighbors. So if a node node1 has node2 in its neighbors list, then node2 will also have node1 in its own neighbors list since the graph is undirected.

    You do not need to understand what {0,1,2#1,2#2,2} to solve the problem. Your code will never deal with inputs that look like that. (You have to understand it however to debug your code as the online judge will show you the inputs of the tests serialized this way.)

    {0,1,2#1,2#2,2} is the serialization of an undirected graph, it is not the concatenation of the adjacency lists. It is implied that this represents an undirected graph. 0,1,2 means that there is an edge between 0 and 1, and an edge between 0 and 2. There is no need later in serialization to encode again the edge between 1 and 0 since it has already been encoded.


  • 2
    S

    Since it is a undirected graph, it would be unnecessary to present graph like you expected. When there is an edge from node 0 to node 1, it implies the edge between these 2 nodes, no matter where it start from. In this problem, the presentation of graph defined in this way, just to help people understand the test case.


  • 6
    A

    I think part of this answer is very misleading. Yes, you do not need to understand the serialization to solve the problem. However, the statement "So if a node node1 has node2 in its neighbors list, then node2 will also have node1 in its own neighbors list since the graph is undirected." is wrong. I did a little experiment and it turns out that OJ's neighbor lists are not mutual, i.e. if node1 and node2 are neighbors and node2 is in node1's neighbor list, then node1 will not appear in node2's list.


  • 6
    W

    yup , I played around with my submission a bit, and it turns out the graph is a directed one.
    ie, if 2 is a neighbor of 1, this does not imply 1 is a neighbor of 2.


  • 2
    A

    I think the input from OJ is problematic, because some correct solution can't be accepted in this way. Please take a look at https://leetcode.com/discuss/107760/believe-undirected-graph-neighbor-should-always-contain-other


  • 0
    J

    @loick Thank you for the clear explanation


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.