package org.structure.graph
;
import java.util.*
;
/**
* 图 深度优先算法 广度优先遍历
* @author cjj_1
* @date 2020-09-03 11:10
*/
public class GraphDemo
{
ArrayList
<String
> vertexList
;
LinkedList
<Integer
> queue
;
Map
<String,Integer
> vertexMap
;
boolean
[] isVisited
;
int
[][] edges
;
int numOfEdges
;
public static void main
(String
[] args
) {
GraphDemo demo
= new GraphDemo
(5
);
String
[] vertex
= {"A",
"B",
"C",
"D",
"E"};
for
(String s:vertex
){
demo.inertVertex
(s
);
}
demo.addEdges
(demo.vertexMap.get
("A"),demo.vertexMap.get
("B"),1
);
demo.addEdges
(demo.vertexMap.get
("B"),demo.vertexMap.get
("C"),1
);
demo.addEdges
(demo.vertexMap.get
("A"),demo.vertexMap.get
("D"),1
);
demo.addEdges
(demo.vertexMap.get
("A"),demo.vertexMap.get
("E"),1
);
demo.addEdges
(demo.vertexMap.get
("B"),demo.vertexMap.get
("C"),1
);
demo.addEdges
(demo.vertexMap.get
("D"),demo.vertexMap.get
("C"),1
);
demo.printEdges
();
// demo.dfs
();//深度优先
demo.bfs
();//广度优先算法
}
public GraphDemo
(int n
){
vertexList
= new ArrayList
<>(n
);
queue
= new LinkedList
<Integer
>();
vertexMap
= new HashMap
<String,Integer
>(n
);
edges
= new int
[n
][n
];
isVisited
= new boolean
[n
];
numOfEdges
=0
;
}
/**
* 一个节点的广度优先遍历
* @param index
*/
public void bfs
(int index
){
System.out.print
(vertexList.get
(index
)+
"=>");
//加入队列
queue.add
(index
);
isVisited
[index
]=true
;
int
v;//当前节点
int w
;//下驱
while (!queue.isEmpty
()){
v = queue.removeFirst
();
w
= getFisrtNear
(v
);
while (w
!=-1
){
if
(!isVisited
[w
]){
System.out.print
(vertexList.get
(w
)+
">=");
isVisited
[w
]=true
;
queue.addLast
(w
);
}
w
= getNextNear
(v,w
);
}
}
}
public void bfs
(){
for (int i
=0
;i
<vertexList.size
();i++
){
if
(!isVisited
[i
]){
bfs
(i
);
}
}
}
/**
* 一个节点的深度优先遍历
* @param index
*/
public void dfs
(int index
){
System.out.print
(vertexList.get
(index
)+
"->");
isVisited
[index
]= Boolean.TRUE
;
int w
=getFisrtNear
(index
);
while (w
!=-1
){
if
(!isVisited
[w
]){
dfs
(w
);
}
w
= getNextNear
(index,w
);
}
}
public void dfs
(){
for (int i
=0
;i
<vertexList.size
();i++
){
if
(!isVisited
[i
]){
dfs
(i
);
}
}
}
/**
* 获取当前节点的第一个临节点
* @param index
* @return
*/
public int getFisrtNear
(int index
){
for (int j
=0
;j
<vertexList.size
();j++
){
if
(edges
[index
][j
]>0
){
return j
;
}
}
return -1
;
}
/**
* 获取当前节点的下一个节点的下标
* @param index
* @param now
* @return
*/
public int getNextNear
(int index,int now
) {
for
(int j
= now+1
;j
<vertexList.size
();j++
){
if
(edges
[index
][j
]>0
){
return j
;
}
}
return -1
;
}
/**
* 增加节点
* @param vertex
*/
public void inertVertex
(String vertex
){
vertexMap.put
(vertex,vertexMap.size
());
vertexList.add
(vertex
);
}
/**
* 增加边
* @param n
* @param m
* @param weigth
*/
public void addEdges
(int n,int m,int weigth
){
edges
[n
][m
] = weigth
;
edges
[m
][n
] = weigth
;
numOfEdges++
;
}
public int getVertexNum
(){
return vertexList.size
();
}
public int getEdges
(){
return numOfEdges
;
}
/**
* 打印最后的矩阵
*/
public void printEdges
(){
for (int row
=0
;row
<edges.length
;row++
){
for (int col
=0
;col
<edges
[row
].length
;col++
){
System.out.printf
("%d\t",edges
[row
][col
]);
}
System.out.println
();
}
}
}
