图的遍历,深度优先与广度优先详解
程序员文章站
2022-05-21 23:21:43
...
图的遍历,深度优先与广度优先详解
图采用邻接矩阵实现,深度优先搜索采用栈来实现,广度优先遍历采用队列来实现.附上代码详解.
图的实现
1.邻接矩阵实现
简单来说就是用一个二维数组来存储图之间的联通情况,比如有5个点,就可以用一个 5*5的 矩阵来存储 两点间是否联通.
比如上图 false 表示不连通, true表示连通.
public class Graph {
private boolean[][] map ;
private int length;
public Graph(int length)//生成图
{
this.length = length;
map = new boolean[length][length];
}
public void addEdge(int i,int j)//加边
{
if (map == null)
{
if (i>j)
{
map = new boolean[i][i];
length = i;
}
else
{
map = new boolean[j][j];
length = j;
}
}
map[i][j] = true;
map[j][i] = true;
}
public void removeEdge(int i,int j)//去边
{
if (map == null || j>=length||i>=length)
return;
else {
map[i][j] = false;
map[j][i] = false;
}
}
public boolean isEdge(int i,int j)//判断是否联通
{
if (map==null||i>=length||j>=length)
return false;
else
return true;
}
}
这个为无向图,若为有向图,则生成的边只有一个就好,即只有A到B.
2.邻接链表实现
采用一个一维链表数组用来存储每个点.若这个节点与其他节点有联通,则与它相连通的子节点构成一个链表.
import java.util.ArrayList;
/**
* Created by max on 17-5-9.
*/
public class ListGraph {
ListNode[] listNodes;
int length ;
ArrayList<Integer> vertices;
public ListGraph(int lenght)
{
this.length = lenght;
listNodes = new ListNode[length];
vertices = new ArrayList<>();
for (int i=0;i<length;i++)
{
listNodes[i] = new ListNode();
vertices.add(i);
}
}
public void addEdge(int start,int end)
{
int i = vertices.indexOf(start);
int j = vertices.indexOf(end);
if (j!=-1&&i!=-1)
{
listNodes[i].insertAtBeginning(j);
listNodes[j].insertAtBeginning(i);
}
}
}
DFS深度优先搜索
思路是采用栈的用来存储访问的节点,而先进后出的机制刚好满足深度搜索的需求.给每个节点添加一个boolean属性,用于判断是否被访问过.
import java.util.ArrayList;
import java.util.Stack;
/**
* Created by max on 17-5-9.
*/
public class DFS {
private class Vertics
{
public char label;
public boolean visited;
public Vertics(char label)
{
this.label = label;
visited = false;
}
}
private class Graph
{
private boolean[][] map;
private ArrayList<Vertics> vertices;
private int countVertices;
private Stack<Integer> stack;
public Graph(int length)
{
stack = new Stack<>();
countVertices = 0;
vertices = new ArrayList<>();
map = new boolean[length][length];
}
public Graph()
{
stack = new Stack<>();
int length =20;
countVertices = 0;
vertices = new ArrayList<>();
map = new boolean[length][length];
}
public void addVertice(char label)
{
vertices.add(new Vertics(label));
countVertices++;
}
public void addEdge(int i,int j)
{
map[i][j] = true;
map[j][i] = true;
}
public void removeEdge(int i ,int j)
{
map[i][j] = false;
map[j][i] = false;
}
public void showLabel(int i)
{
System.out.print(" "+vertices.get(i).label);
}
public void dfs()
{
showLabel(0);
vertices.get(0).visited = true;
stack.push(0);
while(!stack.isEmpty())
{
int v =getNextNode(stack.peek());
if (v==-1)
{
stack.pop();
}
else
{
vertices.get(v).visited=true;
showLabel(v);
stack.push(v);
}
}
for (int i = 0 ;i<countVertices;i++)
vertices.get(i).visited=false;
}
private int getNextNode(int peek) {
for (int i = 0; i < countVertices; i++)
{
if (map[peek][i]==true&&vertices.get(i).visited==false)
return i;
}
return -1;
}
}
}
BFS广度优先搜索
广度优先搜索主要是通过队列的先进先出的机制来实现. 以JAVA中的ArrayQueue实现.
public void bfs()
{
showLabel(0);
vertices.get(0).visited = false;
queue.add(0);
int ans;
int deal;
while(!queue.isEmpty())
{
deal = (int) queue.remove();
while ((ans = getNextNode(deal))!=-1)
{
vertices.get(ans).visited=true;
showLabel(ans);
queue.add(ans);
}
}
for (int i = 0 ;i<countVertices;i++)
vertices.get(i).visited=false;
}
以上是笔主自己对 深搜广搜的理解与笔记,欢迎交流撕逼.
上一篇: 图的遍历:深度优先搜索与广度优先搜索
下一篇: 图的深度优先遍历与广度优先遍历