当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 图论一 深度遍历和广度遍历

发表于: 2012-11-15   作者:blackproof   来源:转载   浏览次数:
摘要: 图对建模很有帮助。   图的基本知识:   Java实现图的两种方法 1 邻接矩阵 邻接矩阵是用二维数据,使用1代表节点间有边,如下表格:   A B C D A 0 1 1 1 B 1 0 0 1 C 1 0 0

图对建模很有帮助。

 

图的基本知识:

 

Java实现图的两种方法

邻接矩阵

邻接矩阵是用二维数据,使用1代表节点间有边,如下表格:

 

A

B

C

D

A

0

1

1

1

B

1

0

0

1

C

1

0

0

0

D

1

1

0

0

 

邻接表

临界表是使用类似链表,连接节点,表示有边

定点

包含邻接顶点的链表

A

B->C->D

B

A->D

C

A

D

A->B

 

深度遍历思路:

 

使用栈,查找栈顶顶点连通到的,没有访问的顶点,使其入栈,并访问。当找不到,则当前栈顶元素出栈。否则继续查找。

 

 

广度遍历思路:

 

使用队列,查找队列头连通的,没有访问的顶点,使其入队列,并访问。当找不到,则当前顶点出队列。否则继续遍历当前队列顶点

 

他们的不同之处就在,栈访问的顶点变化,会越来越深;队列访问的顶点不变化,只有出队列后才换节点访问。

 

 

 

图在java中的邻接矩阵实现:

 

package com.Construction;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphSimpleExample {
	private final int MAX_VERTS = 20;
	private GraphNodeBean nodeList[];
	private int adjMat[][];
	private int nVerts;
	
	public GraphSimpleExample(){
		nodeList = new GraphNodeBean[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				adjMat[i][j] = 0;
			}
		}
	}
	
	public void addNode(char label){
		nodeList[nVerts++] = new GraphNodeBean(label);
	}
	
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}

	public void displayGraphNode(int v){
		System.out.println(nodeList[v].label);
	}
	
	/**
	 * 获得未访问节点
	 * @param v
	 * @return
	 */
	public int getAdjUnvisitedVertex(int v){
		for (int i = 0; i < nVerts; i++) {
			if(adjMat[v][i]==1 && nodeList[i].isVisited == false)
				return i;
		}
		return -1;
	}
	
	/**
	 * deft first 
	 */
	public void dfs(){
		@SuppressWarnings("rawtypes")
		Stack<Integer> theStack = new Stack<Integer>();
		nodeList[0].isVisited = true;
		displayGraphNode(0);
		theStack.push(0);
		
		while(!theStack.isEmpty()){
			int v = getAdjUnvisitedVertex(theStack.peek());
			if(v == -1)
				theStack.pop();
			else{
				nodeList[v].isVisited = true;
				displayGraphNode(v);
				theStack.push(v);
			}
		}
//		for (int i = 0; i < nVerts; i++) {
//			nodeList[i].isVisited = false;
//		}
	}
	
	public void bds(){
		Queue<Integer> theQueue = new LinkedList<Integer>();
		
		nodeList[0].isVisited = true;
		displayGraphNode(0);
		theQueue.offer(0);
		int v2;
		
		while(!theQueue.isEmpty()){
			int v1 = theQueue.poll();
			while((v2 = getAdjUnvisitedVertex(v1)) != -1){
				nodeList[v2].isVisited = true;
				displayGraphNode(v2);
				theQueue.add(v2);
			}
		}
//		for (int i = 0; i < nVerts; i++) {
//		nodeList[i].isVisited = false;
//	}
		
	}
	
}

 其中dfs是深度优先算法

bfs是广度优先算法

java 图论一 深度遍历和广度遍历

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
在编程生活中,我们总会遇见属性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及
在编程生活中,我们总会遇见属性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及
1.调用代码入口: using System; namespace 图_图的遍历 { internal class Program { private stati
图的常用表示方法就是矩阵和邻接表。 矩阵通常使用与规整的,且数据量较小的图,这种图直观上方便的
邻接图的优点就是,现用现申请,空间存储很灵活,并且需要的空间也很小。我们在做复杂网络时,通常
申明 本文的目地是对算法导论中广度优先的内容做一笔记,整体更像该章节的剪辑。 简介 图的广度优先
写在最前面的 两种图的遍历算法在其他图的算法当中都有应用,并且是基本的图论算法。 广度优先搜索
广度优先遍历是连通图的一种遍历策略。其基本思想如下: 1、从图中某个顶点V0出发,并访问此顶点;
申明 本文的目地是对算法导论中深度优先的内容做一笔记,整体更像该章节的剪辑以及总结。 简介 与图
图的广度优先算法是图的基本算法,也是最小生成树以及单源最短路径算法的基础。最近把广度优先遍历
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号