通过邻接表进行前序遍历
Preorder traversal through Adjacency List
我正在尝试将我的 EdgeList
转换为 Adjacency List
,然后 preorder traverse
通过它。我很确定到 Adjacency List
的转换工作正常,但我在 preorder traversing
上遇到了麻烦。我试图用 DFS
来做,但它给了我错误的结果。
这是我的优势:
{index1=0, index2=2}
{index1=3, index2=4}
{index1=1, index2=4}
{index1=0, index2=5}
{index1=2, index2=6}
{index1=1, index2=5}
{index1=2, index2=7}
这就是链表的样子。
0 - 2 - 5
1 - 4 - 5
2 - 6 - 7
3 - 4
或
linked[2, 5]
linked[4, 5]
linked[6, 7]
linked[4]
现在我想预序遍历图,得到结果0 - 2 - 6 - 7 - 5 - 1 - 4 - 3
。
0
2 5
6 7 1
4
3
我已经尝试在我的 AdjacencyListGraph
中使用 DFS
,但这是我使用此代码 0 2 6 7 5
得到的结果:
public class AdjacencyListGraph {
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
AdjacencyListGraph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
}
// A function used by DFS
void DFSUtil(int v,boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v+" ");
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
// System.out.println(i.toString());
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
}
// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS(int v)
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
DFSUtil(v, visited);
}
public static void main(String[] args) {
AdjacencyListGraph graph = new AdjacencyListGraph(8);
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 6);
graph.addEdge(2, 7);
graph.addEdge(3, 4);
graph.DFS(0);
}
}
我也试过使用:
void DFS()
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i=0; i<V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}
而不是上面提到的那个,它遍历了所有 nodes
,但它 returns 结果顺序错误。
我哪里做错了,我应该如何或使用什么来获得预期的结果?
试试这张图:
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 4);
graph.addEdge(5, 1); // different direction than original
graph.addEdge(2, 6);
graph.addEdge(2, 7);
graph.addEdge(4, 3); // different direction than original
或者,对程序中的 addEdge
方法稍作修改:
//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
adj[w].add(v); // Add v to w's list.
}
我正在尝试将我的 EdgeList
转换为 Adjacency List
,然后 preorder traverse
通过它。我很确定到 Adjacency List
的转换工作正常,但我在 preorder traversing
上遇到了麻烦。我试图用 DFS
来做,但它给了我错误的结果。
这是我的优势:
{index1=0, index2=2}
{index1=3, index2=4}
{index1=1, index2=4}
{index1=0, index2=5}
{index1=2, index2=6}
{index1=1, index2=5}
{index1=2, index2=7}
这就是链表的样子。
0 - 2 - 5
1 - 4 - 5
2 - 6 - 7
3 - 4
或
linked[2, 5]
linked[4, 5]
linked[6, 7]
linked[4]
现在我想预序遍历图,得到结果0 - 2 - 6 - 7 - 5 - 1 - 4 - 3
。
0
2 5
6 7 1
4
3
我已经尝试在我的 AdjacencyListGraph
中使用 DFS
,但这是我使用此代码 0 2 6 7 5
得到的结果:
public class AdjacencyListGraph {
private int V; // No. of vertices
// Array of lists for Adjacency List Representation
private LinkedList<Integer> adj[];
// Constructor
AdjacencyListGraph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
}
// A function used by DFS
void DFSUtil(int v,boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v+" ");
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> i = adj[v].listIterator();
// System.out.println(i.toString());
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n,visited);
}
}
// The function to do DFS traversal. It uses recursive DFSUtil()
void DFS(int v)
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
DFSUtil(v, visited);
}
public static void main(String[] args) {
AdjacencyListGraph graph = new AdjacencyListGraph(8);
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 4);
graph.addEdge(1, 5);
graph.addEdge(2, 6);
graph.addEdge(2, 7);
graph.addEdge(3, 4);
graph.DFS(0);
}
}
我也试过使用:
void DFS()
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for (int i=0; i<V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}
而不是上面提到的那个,它遍历了所有 nodes
,但它 returns 结果顺序错误。
我哪里做错了,我应该如何或使用什么来获得预期的结果?
试试这张图:
graph.addEdge(0, 2);
graph.addEdge(0, 5);
graph.addEdge(1, 4);
graph.addEdge(5, 1); // different direction than original
graph.addEdge(2, 6);
graph.addEdge(2, 7);
graph.addEdge(4, 3); // different direction than original
或者,对程序中的 addEdge
方法稍作修改:
//Function to add an edge into the graph
void addEdge(int v, int w) {
adj[v].add(w); // Add w to v's list.
adj[w].add(v); // Add v to w's list.
}