> For the complete documentation index, see [llms.txt](https://eric-zhang-seattle.gitbook.io/leetcode-1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://eric-zhang-seattle.gitbook.io/leetcode-1/data-structures/graph.md). # graph * [Graph](#graph) * [Edge list vs Adjacent list vs Adjacent matrix](#edge-list-vs-adjacent-list-vs-adjacent-matrix) * [Build graph](#build-graph) * [Detect cycles inside undirected graph](#detect-cycles-inside-undirected-graph) * [Detect cycles inside directed graph](#detect-cycles-inside-directed-graph) ## [Graph](https://github.com/wisdompeak/LeetCode/tree/master/Graph/) ### Edge list vs Adjacent list vs Adjacent matrix * Time complexity comparison between different graph representation * Use cases for different representations * Edge list is usually not used because looping through neighbor of a vertex is too expensive. This makes it really appropriate for many graph algo (bfs, dfs). * Adjacent matrix is usually used for dense graph, where vertexes are seldomly added or removed. * Adjacent list is usually used for sparse graph to save space. * Adjacent list representation is the most commonly used graph representation in an interview setting. There are two common ways to realize this. One typical classical way is to define class GraphNode and then graph can be defined as List < GraphNode >. The other way is to define graph as Map\> graph. Map\ ```java // first way, more official // but if there are redundant edges in input, might need to implement hashcode() and equal() methods to avoid add redundant nodes into neighbors. Kind of overkilling in an interview setting class GraphNode { int val; int status; // used for track visiting status in DFS List neighbor; // ... } List graph =...; // second way, graph itself is more concise. But need additional data structures like Set visited and Set discovered to track dfs traverse status Map> graph ``` ### Build graph * it is will be less error-prone to separate the phase of building vertexes and edges. When they are merged together, it is easy to forget about the isolated vertexes. In a common setting, usually asked to build a graph given the number of vertex int n and an array of edges. ```java public Map> buildGraph( int n, int[][] edges ) { Map> graph = new HashMap<>(); // build vertex for ( int i = 0; i < n; i++ ) { graph.put( i, new HashSet<>() ); } // build edges for ( int[] edge : edges ) { // undirected graph needs to add the edge twice graph.get( edge[0] ).add( edge[1] ); graph.get( edge[1] ).add( edge[0] ); } } ``` ### Detect cycles inside undirected graph ```java // Graph is represented by class GraphNode class GraphNode { int nodeIndex; List neighbors; } private boolean hasCycle( GraphNode root ) { return hasCycle( root, new HashSet<>() ); } private boolean hasCycle( GraphNode root, Set isDiscovered ) { if ( isDiscovered.contains( root ) ) { return true; } isDiscovered.add( root ); for ( List neighbor : root.neighbors ) { if ( hasCycle( neighbor, isVisited ) ) { return true; } } return false; } ``` ### Detect cycles inside directed graph ```java // Graph is represented by class GraphNode class GraphNode { int nodeIndex; List neighbors; } private boolean hasCycle( GraphNode root ) { Set isDiscovered = new HashSet<>(); Set isVisited = new HashSet<>(); return hasCycle( root, isDiscovered, isVisited ); } private boolean hasCycle( GraphNode root, Set isDiscovered, Set isVisited ) { if ( isVisited.contains( root ) ) { return false; } if ( isDiscovered.contains( root ) && !isVisited.contains( root ) ) { return true; } isDiscovered.add( root ); for ( List neighbor : root.neighbors ) { if ( hasCycle( neighbor, isDiscovered, isVisited ) ) { return true; } } isVisited.add( root ); return false; } ``` [332.Reconstruct-Itinerary](https://github.com/wisdompeak/LeetCode/tree/master/DFS/332.Reconstruct-Itinerary) (H)\ [753.Cracking-the-Safe](https://github.com/wisdompeak/LeetCode/tree/master/Hash/753.Cracking-the-Safe) (H)\ [1059.All-Paths-from-Source-Lead-to-Destination](https://github.com/wisdompeak/LeetCode/tree/master/Graph/1059.All-Paths-from-Source-Lead-to-Destination) (H)\ [1192.Critical-Connections-in-a-Network](https://github.com/wisdompeak/LeetCode/tree/master/DFS/1192.Critical-Connections-in-a-Network) (H)\ 1334.Find-the-City-With-the-Smallest-Number-of-Neighbors-at-a-Threshold-Distance (TBD)\ 1361.Validate-Binary-Tree-Nodes (TBD)\ [1719.Number-Of-Ways-To-Reconstruct-A-Tree](https://github.com/wisdompeak/LeetCode/tree/master/Graph/1719.Number-Of-Ways-To-Reconstruct-A-Tree) (H+)\ [1761.Minimum-Degree-of-a-Connected-Trio-in-a-Graph](https://github.com/wisdompeak/LeetCode/tree/master/Graph/1761.Minimum-Degree-of-a-Connected-Trio-in-a-Graph) (M+)\ [1782.Count-Pairs-Of-Nodes](https://github.com/wisdompeak/LeetCode/tree/master/Graph/1782.Count-Pairs-Of-Nodes) (H)\ [1820.Maximum-Number-of-Accepted-Invitations](https://github.com/wisdompeak/LeetCode/tree/master/Graph/1820.Maximum-Number-of-Accepted-Invitations) (H) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://eric-zhang-seattle.gitbook.io/leetcode-1/data-structures/graph.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.