有方向带权重图-邻接矩阵:
- 出度看行
- 入度看列
无向带权图-邻接矩阵:
- 对称阵
- 主对角线上全为0
package xcrj.kchalgorithm.bruteForce.graph;
public class DFS {
static int n = 5;
static int[] visited = new int[n];
static void dfs(MGraph mGraph, int vertex) {
// 访问 再 置于访问标识
// System.out.println(" 点:" + vertex + " ");
visited[vertex] = 1;
// 获取这个点的所有邻接点&&没有访问的点 再 递归
for (int i = 0; i < mGraph.getN(); i++) {
if (mGraph.getEdges()[vertex][i] > 0 && mGraph.getEdges()[vertex][i] < Float.MAX_VALUE && visited[i] == 0) {
System.out.println(" 点" + vertex + "-权值" + mGraph.getEdges()[vertex][i] + "->点" + i);
dfs(mGraph, i);
}
}
}
public static void directedWeightedGraph() {
int n = DFS.n;
int e = 6;
MVertex[] mVertices = new MVertex[n];
for (int i = 0; i < n; i++) {
mVertices[i] = new MVertex(i, (char) i);
}
int[][] edges = new int[n][n];
edges[0][4] = 6;
edges[1][0] = 9;
edges[1][2] = 3;
edges[2][0] = 2;
edges[2][3] = 5;
edges[3][4] = 1;
MGraph mGraph = new MGraph(n, e, mVertices, edges);
// 有方向带权值连通图
for (int i = 0; i < n; i++) {
System.out.println("从" + i + "出发");
dfs(mGraph, i);
}
}
public static void undirectedWeightedGraph() {
int n = DFS.n;
int e = 6;
MVertex[] mVertices = new MVertex[n];
for (int i = 0; i < n; i++) {
mVertices[i] = new MVertex(i, (char) i);
}
int[][] edges = new int[n][n];
edges[0][4] = 6;
edges[4][0] = 6;
edges[0][1] = 9;
edges[1][0] = 9;
edges[1][2] = 3;
edges[2][1] = 3;
edges[0][2] = 2;
edges[2][0] = 2;
edges[2][3] = 5;
edges[3][2] = 5;
edges[3][4] = 1;
edges[4][3] = 1;
MGraph mGraph = new MGraph(n, e, mVertices, edges);
// 有方向带权值连通图
for (int i = 0; i < n; i++) {
System.out.println("从" + i + "出发");
dfs(mGraph, i);
}
}
public static void main(String[] args) {
directedWeightedGraph();
// undirectedWeightedGraph();
}
}



