数据结构-图-Java实现:有向图 图存储(邻接矩阵),最小生成树,广度深度遍历,图的连通性,最短路径
2019年06月17日
⁄ 综合
⁄ 共 9434字 ⁄ 字号
小 中 大
-
import java.util.ArrayList;
-
-
import java.util.List;
-
-
-
-
-
-
public class AdjMatrixGraph<E> {
-
-
protected SeqList<E> vertexlist;
-
-
-
-
protected int[][] adjmatrix;
-
-
-
-
private final int MAX_WEIGHT = Integer.MAX_VALUE / 2;
-
-
-
-
-
-
-
-
-
-
public AdjMatrixGraph(int n) {
-
-
this.vertexlist = new SeqList<E>(n);
-
-
this.adjmatrix = new int[n][n];
-
-
for (int i = 0; i < n; i++)
-
-
for (int j = 0; j < n; j++)
-
-
this.adjmatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT;
-
-
-
-
}
-
-
-
-
-
-
public AdjMatrixGraph(E[] vertices, Edge[] edges) {
-
-
this(vertices.length);
-
-
for (int i = 0; i < vertices.length; i++)
-
-
insertVertex(vertices[i]);
-
-
for (int j = 0; j < edges.length; j++)
-
-
insertEdge(edges[j]);
-
-
}
-
-
-
-
-
-
public AdjMatrixGraph(SeqList<E> list, Edge[] edges) {
-
-
this(list.length());
-
-
this.vertexlist = list;
-
-
for (int j = 0; j < edges.length; j++)
-
-
insertEdge(edges[j]);
-
-
}
-
-
-
-
-
-
public int vertexCount() {
-
-
return this.vertexlist.length();
-
-
}
-
-
-
-
-
-
public E get(int i) {
-
-
return this.vertexlist.get(i);
-
-
}
-
-
-
-
public boolean insertVertex(E vertex) {
-
-
-
-
return this.vertexlist.add(vertex);
-
-
}
-
-
-
-
public boolean insertEdge(int i, int j, int weight)
-
-
-
-
{
-
-
if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount()
-
-
&& i != j && adjmatrix[i][j] == MAX_WEIGHT) {
-
-
-
-
this.adjmatrix[i][j] = weight;
-
-
return true;
-
-
}
-
-
return false;
-
-
}
-
-
-
-
public boolean insertEdge(Edge edge) {
-
-
if (edge != null)
-
-
;
-
-
return insertEdge(edge.start, edge.dest, edge.weight);
-
-
}
-
-
-
-
public String toString() {
-
-
String str = "顶点集合: " + vertexlist.toString() + "\n";
-
-
str += "邻近矩阵: \n";
-
-
int n = vertexCount();
-
-
for (int i = 0; i < n; i++) {
-
-
for (int j = 0; j < n; j++) {
-
-
if (adjmatrix[i][j] == MAX_WEIGHT)
-
-
str += " ∞";
-
-
else
-
-
str += " " + adjmatrix[i][j];
-
-
}
-
-
str += "\n";
-
-
}
-
-
return str;
-
-
}
-
-
-
-
public boolean removeEdge(int i, int j)
-
-
{
-
-
if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount()
-
-
&& i != j && this.adjmatrix[i][j] != MAX_WEIGHT) {
-
-
-
-
this.adjmatrix[i][j] = MAX_WEIGHT;
-
-
return true;
-
-
}
-
-
return false;
-
-
}
-
-
-
-
public boolean removeVertex(int v)
-
-
{
-
-
int n = vertexCount();
-
-
if (v >= 0 && v < n) {
-
-
this.vertexlist.remove(v);
-
-
for (int i = v; i < n - 1; i++)
-
-
for (int j = 0; j < n; j++)
-
-
this.adjmatrix[i][j] = this.adjmatrix[i + 1][j];
-
-
for (int j = v; j < n - 1; j++)
-
-
for (int i = 0; i < n - 1; i++)
-
-
this.adjmatrix[i][j] = this.adjmatrix[i][j + 1];
-
-
return true;
-
-
}
-
-
return false;
-
-
}
-
-
-
-
public int getFirstNeighbor(int v)
-
-
{
-
-
return getNextNeighbor(v, -1);
-
-
}
-
-
-
-
public int getNextNeighbor(int v, int w) {
-
-
if (v >= 0 && v < vertexCount() && w >= -1 && w < vertexCount()
-
-
-
-
&& v != w)
-
-
for (int j = w + 1; j < vertexCount(); j++)
-
-
-
-
if (adjmatrix[v][j] > 0 && adjmatrix[v][j] < MAX_WEIGHT)
-
-
-
-
return j;
-
-
return -1;
-
-
}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
public AdjMatrixGraph minSpanTree_prim() {
-
-
Edge[] mst = new Edge[this.vertexCount() - 1];
-
-
int un;
-
-
List<Integer> u = new ArrayList<Integer>();
-
-
u.add(0);
-
-
for (int i = 0; i < this.vertexCount() - 1; i++) {
-
-
int minweight = MAX_WEIGHT;
-
-
int minstart = MAX_WEIGHT;
-
-
int mindest = MAX_WEIGHT;
-
-
for (int j = 0; j < u.size(); j++) {
-
-
un = u.get(j);
-
-
for (int k = 0; k < this.vertexCount(); k++) {
-
-
-
-
if ((minweight > adjmatrix[un][k]) && (!u.contains(k))) {
-
-
minweight = adjmatrix[un][k];
-
-
minstart = un;
-
-
mindest = k;
-
-
}
-
-
}
-
-
}
-
-
System.out.println("一次遍历所添加的最小边:他的权值,起点,终点分别为:weight:" + minweight
-
-
+ "start:" + minstart + "dest:" + mindest);
-
-
u.add(mindest);
-
-
Edge e = new Edge(minstart, mindest, adjmatrix[minstart][mindest]);
-
-
mst[i] = e;
-
-
}
-
-
return new AdjMatrixGraph(this.vertexlist, mst);
-
-
}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
public void DFStraverse() {
-
-
int n = this.vertexCount();
-
-
boolean[] visited = new boolean[n];
-
-
for (int i = 1; i < n; i++) {
-
-
visited[i] = false;
-
-
}
-
-
-
-
for (int j = 0; j < n; j++) {
-
-
if (!visited[j]) {
-
-
System.out.println("以该顶点为" + j + "起始点的遍历:");
-
-
this.DFS(j, visited);
-
-
}
-
-
}
-
-
}
-
-
-
-
-
-
public void DFS(int v, boolean[] visited2) {
-
-
boolean[] visited = visited2;
-
-
visited[v] = true;
-
-
System.out.println("遍历顶点" + v);
-
-
for (int w = this.getFirstNeighbor(v); w >= 0; w = this
-
-
.getNextNeighbor(v, w)) {
-
-
if (!visited[w]) {
-
-
visited[w] = true;
-
-
DFS(w, visited);
-
-
}
-
-
}
-
-
}
-
-
-
-
public void BFStraverse() {
-
-
int n = this.vertexCount();
-
-
boolean[] visited = new boolean[n];
-
-
MyQueue myqueue = new MyQueue();
-
-
for (int i = 1; i < n; i++) {
-
-
visited[i] = false;
-
-
}
-
-
-
-
for (int j = 0; j < n; j++) {
-
-
if (!visited[j]) {
-
-
visited[j] = true;
-
-
System.out.println("遍历起点:" + j);
-
-
myqueue.EnQueue(j);
-
-
while (!myqueue.empty()) {
-
-
int v = (Integer) myqueue.DeQueue();
-
-
System.out.println("遍历点:" + v);
-
-
for (int w = this.getFirstNeighbor(v); w >= 0; w = this
-
-
.getNextNeighbor(v, w)) {
-
-
if (!visited[w]) {
-
-
visited[w] = true;
-
-
myqueue.EnQueue(w);
-
-
}
-
-
}
-
-
}
-
-
}
-
-
}
-
-
-
-
}
-
-
-
-
-
-
public void Dijkstra() {
-
-
int n = this.vertexCount();
-
-
int minweight = MAX_WEIGHT;
-
-
int minUn = 0;
-
-
int[] minmatrix = new int[n];
-
-
boolean[] isS = new boolean[n];
-
-
String[] route = new String[n];
-
-
for (int i = 1; i < n; i++) {
-
-
minmatrix[i] = adjmatrix[0][i];
-
-
isS[i] = false;
-
-
route[i] = "起点->" + i;
-
-
}
-
-
for (int i = 1; i < n; i++) {
-
-
-
-
for (int k = 1; k < n; k++) {
-
-
if (!isS[k]) {
-
-
if (minmatrix[k] < minweight) {
-
-
minweight = minmatrix[k];
-
-
minUn = k;
-
-
}
-
-
}
-
-
}
-
-
isS[minUn] = true;
-
-
for (int j = 1; j < n; j++) {
-
-
if (!isS[j]) {
-
-
if (minweight + adjmatrix[minUn][j] < minmatrix[j]) {
-
-
-
-
minmatrix[j] = minweight + adjmatrix[minUn][j];
-
-
route[j] = route[minUn] + "->" + j;
-
-
}
-
-
}
-
-
}
-
-
minweight = MAX_WEIGHT;
-
-
}
-
-
for (int m = 1; m < n; m++) {
-
-
System.out.println("从V0出发到达" + m + "点");
-
-
if (minmatrix[m] == MAX_WEIGHT) {
-
-
System.out.println("没有到达该点的路径");
-
-
} else {
-
-
System.out.println("当前从V0出发到达该点的最短距离:" + minmatrix[m]);
-
-
System.out.println("当前从V0出发到达该点的最短距离:" + route[m]);
-
-
-
-
}
-
-
}
-
-
}
-
-
-
-
-
-
public boolean isConnect() {
-
-
int n = this.vertexCount();
-
-
boolean[] visited = new boolean[n];
-
-
-
-
-
-
int notConnectNum = 0;
-
-
for (int j = 0; j < n; j++) {
-
-
for (int i = 0; i < n; i++) {
-
-
visited[i] = false;
-
-
}
-
-
this.DFS(j, visited);
-
-
for (int k = 0; k < n; k++) {
-
-
System.out.println(visited[k]);
-
-
if (visited[k] == false) {
-
-
notConnectNum++;
-
-
break;
-
-
}
-
-
}
-
-
}
-
-
if (notConnectNum == n) {
-
-
System.out.println("此图是不连通的");
-
-
return false;
-
-
} else {
-
-
System.out.println("此图是连通的");
-
-
return true;
-
-
}
-
-
}
-
-
-
-
-
-
public void topologicalSort() {
-
-
int n = this.vertexCount();
-
-
int[] indegree = new int[n];
-
-
MyStack mystack = new MyStack();
-
-
String route = "拓扑排序出发:";
-
-
int count = 0;
-
-
for (int i = 0; i < n; i++) {
-
-
indegree[i] = 0;
-
-
for (int j = 0; j < n; j++) {
-
-
if (adjmatrix[j][i] != 0 && adjmatrix[j][i] != MAX_WEIGHT) {
-
-
indegree[i] += 1;
-
-
}
-
-
}
-
-
if (indegree[i] == 0) {
-
-
mystack.push(i);
-
-
}
-
-
}
-
-
while (!mystack.empty()) {
-
-
int v = (Integer) mystack.pop();
-
-
route += "->" + v;
-
-
++count;
-
-
for (int w = this.getFirstNeighbor(v); w >= 0; w = this
-
-
.getNextNeighbor(v, w)) {
-
-
indegree[w] -= 1;
-
-
if (indegree[w] == 0) {
-
-
mystack.push(w);
-
-
}
-
-
}
-
-
}
-
-
if (count < n) {
-
-
System.out.println("存在回路,不满足拓扑排序的条件");
-
-
} else {
-
-
System.out.println("实现拓扑排序" + route);
-
-
-
-
}
-
-
}
-
-
-
}