图是由定点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中G表示一个图，V是图G中顶点的边集，E是图中边的集合。
图按照有无方向分为有向图和无向图。无向图由顶点和边构成，有向图由顶点和弧构成。开始点为弧尾，结束点为弧头。
图按照边的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫做有向完全图。若无重复的边或顶点到自身的边叫做简单图。
图的边或弧相关的数叫做权，这种带权的图通称为网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
———————————————————图的存储结构—————————————————
1.邻接矩阵
用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息
/**
* 一维数组，存储顶点
*/
private Object[] elementData;
/**
* 二维数组存储边
*/
private int[][] edges;
/**
* 顶点数量
*/
private int size;
public AdjacencyMatrixGraph(int initSize) {
size = 0;
elementData = new Object[initSize];
edges = new int[initSize][initSize];
visited = new Boolean[initSize];
}
//插入顶点
public void insertV(Object o) {
visited[size] = false;
elementData[size] = o;
size++;
}
//删除顶点
public void deleteV(Object o) {
int index = indexOf(o);
if (index == -1) {
throw new RuntimeException("顶点数据不存在");
}
/**
* 查找存在包含该顶点的边
*/
for (int i = 0; i < size; i++) {
deleteEdge(i, index);
deleteEdge(index, i);
}
visited[index] = false;
size--;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {
return i;
}
}
return -1;
}
//删除边
public void deleteEdge(int v1, int v2) {
judge(v1, v2);
edges[v1][v2] = 0;
edges[v2][v2] = 0;
}
private void judge(int v1, int v2) {
if (v1 < 0 || v2 < 0 || v1 >= size || v2 >= size) {
throw new RuntimeException("顶点索引不正确");
}
}
//插入边
public void insertEdge(int v1, int v2) {
judge(v1, v2);
edges[v1][v2] = 1;
edges[v2][v1] = 1;
}
public int getEdge(int v1, int v2) {
judge(v1, v2);
return edges[v1][v2];
}
2.邻接表
（1）图中顶点用一个一维数组存储
（2）图中每个顶点vi的所有邻接点构成一个线性表。
private static class EdgeNode {
/**
* 该节点的下标位置
*/
private int adjvex;
/**
* 权值
*/
private int weight;
/**
* 下一个边节点的指针
*/
private EdgeNode edgeNode;
public EdgeNode(int adjvex, int weight, EdgeNode edgeNode) {
this.adjvex = adjvex;
this.weight = weight;
this.edgeNode = edgeNode;
}
public EdgeNode(int adjvex, int weight) {
this.adjvex = adjvex;
this.weight = weight;
}
public EdgeNode(int adjvex) {
this.adjvex = adjvex;
}
public EdgeNode() {
}
}
private static class VertexNode {
private Object data;
private EdgeNode edgeNode;
public VertexNode() {
}
public VertexNode(Object data) {
this.data = data;
}
public VertexNode(Object data, EdgeNode edgeNode) {
this.data = data;
this.edgeNode = edgeNode;
}
}
private VertexNode[] nodes;
/**
* 实际顶点数量
*/
private int size;
public AdjListGraph(int initSize) {
nodes = new VertexNode[initSize];
size = 0;
visited = new Boolean[initSize];
}
//插入顶点
public void insertV(Object o) {
VertexNode vertexNode = new VertexNode(o);
nodes[size] = vertexNode;
visited[size] = false;
size++;
}
//删除顶点
public void removeV(int v) {
if (v < 0 || v >= size) {
throw new RuntimeException("顶点索引不正确");
}
for (int i = 0; i < size; i++) {
deleteE(i, v);
deleteE(v, i);
}
}
//插入边
public void insertE(int v1, int v2, int weight) {
judge(v1, v2);
handleVertexNode(v1, v2, weight);
handleVertexNode(v2, v1, weight);
}
private void handleVertexNode(int v1, int v2, int weight) {
VertexNode v1VertexNode = nodes[v1];
if (v1VertexNode.edgeNode == null) {
v1VertexNode.edgeNode = new EdgeNode(v2, weight);
} else {
v1VertexNode.edgeNode = new EdgeNode(v2, weight, v1VertexNode.edgeNode);
}
}
//删除边
public void deleteE(int v1, int v2) {
judge(v1, v2);
fastRemoveE(v1, v2);
fastRemoveE(v2, v1);
}
private void fastRemoveE(int v1, int v2) {
//如果是顶点连接的第一个邻接节点，需将顶点的邻接重置
EdgeNode edgeNode = nodes[v1].edgeNode;
if (edgeNode != null && edgeNode.adjvex == v2) {
nodes[v1].edgeNode = edgeNode.edgeNode;
} else {
//判断是不是链表上非第一个
EdgeNode previous = null;
edgeNode = edgeNode.edgeNode;
while (edgeNode != null && edgeNode.adjvex != v2) {
previous = edgeNode;
edgeNode = edgeNode.edgeNode;
}
if (edgeNode != null) {
previous.edgeNode = edgeNode.edgeNode;
}
}
}
private void judge(int v1, int v2) {
if (v1 < 0 || v2 < 0 || v1 >= size || v2 >= size) {
throw new RuntimeException("顶点索引不正确");
}
}
3.十字链表
4.邻接多重表
5.边集数组
由两个一维数组构成。一个存储顶点的信息，另一个存储边的信息，这边数组每个数据元素由一条边的起点下标、终点下标和权值组成。
———————————————————图的遍历———————————————————
1.深度优先遍历
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
邻接矩阵深度优先遍历：递归
/**
* 节点是否被遍历
*/
private Boolean[] visited;
/**
* 邻接矩阵的深度优先算法
* 选定一个顶点进行遍历，判断是否被遍历到
* 如果为遍历到，则遍历这个节点相关联的边节点
*/
public void dfs() {
for (int i = 0; i < size; i++) {
if (!visited[i]) {
dfs(i);
}
}
}
/**
* 从第i个节点进行深度遍历
*
* @param i
*/
private void dfs(int i) {
visited[i] = true;
System.out.println(elementData[i] + " ");
for (int j = 0; j < size; j++) {
if (edges[i][j] == 1 && !visited[j]) {
dfs(j);
}
}
}
邻接矩阵深度优先遍历：非递归（使用栈）
private Boolean[] visited;
private Stack<Object> stack = new Stack<>();
public void stackDfs() {
visited[0] = true;
System.out.println(elementData[0]);
stack.push(elementData[0]);
int index = 0;
while (!stack.isEmpty()) {
int v = getNextIndex(index);
if (v == -1) {
stack.pop();
} else {
visited[v] = true;
System.out.println(elementData[v]);
stack.push(elementData[v]);
index = v;
}
}
}
public int getNextIndex(int index) {
for (int i = 0; i < size; i++) {
if (edges[index][i] == 1 && !visited[i]) {
return i;
}
}
return -1;
}
邻接表深度优先遍历：递归
private Boolean[] visited;
/**
* 邻接链表的深度优先算法
*
* 判断相邻的边的下标是否被遍历到，如果未遍历，则从这个节点开始遍历
*
*
* 递归算法实现
*/
public void dfs() {
for (int i = 0; i < size; i++) {
if (!visited[i]) {
dfs(i);
}
}
}
public void dfs(int i) {
visited[i] = true;
System.out.println(nodes[i].data);
EdgeNode edgeNode = nodes[i].edgeNode;
while (edgeNode != null) {
if (!visited[edgeNode.adjvex]) {
dfs(edgeNode.adjvex);
}
edgeNode = edgeNode.edgeNode;
}
}
邻接表深度优先遍历：栈
private Boolean[] visited;
private Stack<VertexNode> vertexNodeStack = new Stack<>();
/**
* 使用栈对链表进行遍历
*/
public void stackDfs() {
visited[0] = true;
System.out.println(nodes[0].data);
vertexNodeStack.push(nodes[0]);
//栈不空，则判断栈顶元素的向邻接节点
while (!vertexNodeStack.isEmpty()) {
int adjListIndex = getIndex(vertexNodeStack.peek());
if(adjListIndex == -1){
vertexNodeStack.pop();
}else {
visited[adjListIndex] = true;
System.out.println(nodes[adjListIndex].data);
vertexNodeStack.push(nodes[adjListIndex]);
}
}
}
public int getIndex(VertexNode v) {
EdgeNode edgeNode = v.edgeNode;
while (edgeNode != null) {
if (!visited[edgeNode.adjvex]) {
return edgeNode.adjvex;
}
edgeNode = edgeNode.edgeNode;
}
return -1;
}
2.广度优先遍历
一层一层的顶点访问
邻接矩阵广度优先遍历：
private Queue<Object> objectQueue = new ArrayDeque<>();
/**
* 队列实现广度优先遍历算法
*
* 类似层序遍历
*
* 先入队列，则先出队列
*/
public void bfs() {
visited[0] = true;
objectQueue.add(elementData[0]);
System.out.println(elementData[0]);
int index = 0;
while (!objectQueue.isEmpty()) {
objectQueue.remove();
for (int i = 0; i < size; i++) {
if (edges[index][i] == 1 && !visited[i]) {
visited[i] = true;
objectQueue.add(elementData[i]);
System.out.println(elementData[i]);
}
}
}
}
邻接表广度优先遍历：
private Queue<VertexNode> vertexNodeQueue = new ArrayDeque<>();
/**
* 队列实现广度优先遍历算法
*
* 类似层序遍历
*
* 先入队列，则先出队列
*/
public void bfs() {
visited[0] = true;
vertexNodeQueue.add(nodes[0]);
System.out.println(nodes[0].data);
int index = 0;
while (!vertexNodeQueue.isEmpty()) {
vertexNodeQueue.remove();
EdgeNode edgeNode = nodes[index].edgeNode;
while (edgeNode !=null){
if(!visited[edgeNode.adjvex]){
vertexNodeQueue.add(nodes[edgeNode.adjvex]);
visited[edgeNode.adjvex] = true;
System.out.println(nodes[edgeNode.adjvex].data);
}
edgeNode = edgeNode.edgeNode;
}
}
}
网友评论