無向圖的構(gòu)建
我的目標(biāo)是輸入頂點個數(shù)以及一系列的邊來構(gòu)建出無向圖万皿。
表示圖的方法有鄰接矩陣摧找，鄰接表，以及邊的列表
設(shè)計Graph類牢硅，該類中包含V蹬耘，E，以及鄰接表adj减余。
public Graph(int V, int[][] edges) {
// 輸入?yún)?shù).一個是頂點的個數(shù)综苔，接下來是n條邊
this.V = V;
this.adj = (ArrayList<Integer>[]) new ArrayList[this.V];
for (int i = 0; i < this.V; i++) {
this.adj[i] = new ArrayList<>();
}
for (int i = 0; i < edges.length; i++) {
int from = edges[i][0];
int to = edges[i][1];
this.adj[from].add(to);
this.adj[to].add(from);
this.E++;
}
}
DFS
無向圖的深度優(yōu)先遍歷總是遞歸尋找到該節(jié)點對應(yīng)的鏈表所有可能的節(jié)點。代碼如下：
public void dfs(int v) {
boolean[] marked = new boolean[this.V];
int[] edgeTo=new int[this.V];
dfs(marked,edgeTo, v);
System.out.println(Arrays.toString(edgeTo));
}
private void dfs(boolean[] marked,int[] edgeTo, int v) {
marked[v] = true;
System.out.println("v:" + v);
for (int i : this.adj[v]) {
if (!marked[i]) {
edgeTo[i]=v;
dfs(marked,edgeTo, i);
}
}
}
marked表示該節(jié)點是否被訪問過位岔，edgeTo表示從點v開始到任意一點的路徑如筛，如果要輸出路徑，可以通過如下途徑輸出（倒置）：
int temp=v2;
System.out.print("path: ");
while(temp!=v1){
System.out.print(temp+",");
temp=edgeTo[temp];
}
System.out.println(v1);
BFS
廣度優(yōu)先遍歷通過隊列的方式進行（和二叉樹的層次遍歷相同）
public void bfs(int v){
boolean[] marked=new boolean[this.V];
int[] edgeTo=new int[this.V];
bfs(marked, edgeTo, v);
}
public void bfs(boolean[] marked,int[] edgeTo,int v){
Queue<Integer> queue=new LinkedList<>();
queue.add(v);
marked[v]=true;
while(!queue.isEmpty()){
int a=queue.poll();
System.out.println("v:"+a);
for(int w:this.adj[a]){
if(!marked[w]){
marked[w]=true;
edgeTo[w]=a;
queue.add(w);
}
}
}
System.out.println(Arrays.toString(edgeTo));
}
