建站
咨詢
售后
建站咨詢
新聞中心
java中如何把圖用鄰接表表示出來
package my.graph;
成都創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站設(shè)計、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司與策劃設(shè)計,延津網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:延津等地區(qū)。延津做網(wǎng)站價格咨詢:18982081108
import java.util.ArrayList;
import java.util.Iterator;
import my.queue.*;
import my.stack.StackX;
/**
* 鄰接表表示
* @author xiayi
*
*/
public class Graph {
private int MAX_VERTS = 20;
private Vertex vertexList[];
private boolean is = false;//是否為有向圖
private int nVerts = 0;
private StackX stackX;
private Vertex dfs[];
private Vertex bfs[];
private Queue queue;
public Graph(){
vertexList = new Vertex[MAX_VERTS];
dfs = new Vertex[MAX_VERTS];
bfs = new Vertex[MAX_VERTS];
}
public Graph(int n){
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
public Graph(int n, boolean is){
this.is = is;
vertexList = new Vertex[n];
dfs = new Vertex[n];
bfs = new Vertex[n];
}
//////////////////////////////////////////////
public boolean isIs() {
return is;
}
public void setIs(boolean is) {
this.is = is;
}
public Vertex[] getVertexList() {
return vertexList;
}
public Vertex[] getDfs() {
return dfs;
}
public Vertex[] getBfs() {
return bfs;
}
////////////////////////////////////////////////////
/**
* 添加頂點
*/
public void addVertex(Vertex vertex){
vertex.setIndex(nVerts);
vertexList[nVerts] = vertex;
nVerts++;
}
/**
* 添加邊
*/
public void addEdge(int start, int end){
vertexList.addAdj(vertexList);
if (!is) {vertexList.addAdj(vertexList);}
}
/**
* 返回節(jié)點個數(shù)
* @return
*/
public int getVertsCount(){
return vertexList.length;
}
/**
* 深度優(yōu)先迭代器
* @return
*/
public Iterator dfsIterator(){
dfs();
return new DfsIterator();
}
/**
* 廣度優(yōu)先迭代器
* @return
*/
public Iterator bfsIterator(){
bfs();
return new BfsIterator();
}
////////////////////////////////////////////////////////
public void displayGraph(){
ArrayListVertex next = null;
for (int i = 0; i vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayListVertex next = vertex.getAdj();
if(next == null){ System.out.println(vertex.toString()+" 無連接點");}
else{
System.out.print(vertex.toString()+"有鄰接點:");
for (int i = 0; i next.size(); i++) {
System.out.print("頂點"+next.get(i).label+", ");
}
System.out.println();
}
}
///////////////////////////////////////////////////////////
public void dfs(){
stackX = new StackX(MAX_VERTS);
vertexList[0].isVisted = true;
dfs[0] = vertexList[0];
stackX.push(vertexList[0]);
int dfsIndex = 0;
Vertex vertex;
while(!stackX.isEmpty()){
vertex = getAdjVertex((Vertex)stackX.peek());
if(vertex == null){
stackX.pop();
}else{
vertex.isVisted = true;
dfs[++dfsIndex]=vertex;
stackX.push(vertex);
}
}
for (int i = 0; i getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
public void bfs() {
queue = new Queue(MAX_VERTS);
vertexList[0].isVisted = true;
bfs[0] = vertexList[0];
queue.insert(vertexList[0]);
int bfsIndex = 0;
Vertex vertex;
while(!queue.isEmpty()){
Vertex vertex2 = (Vertex)queue.remove();
while((vertex = getAdjVertex(vertex2))!=null){
vertex.isVisted = true;
bfs[++bfsIndex] = vertex;
queue.insert(vertex);
}
}
for (int i = 0; i getVertsCount(); i++) {
vertexList[i].isVisted = false;
}
}
/**
* 得到一個鄰接點
* @param vertex
* @return
*/
public Vertex getAdjVertex(Vertex vertex){
ArrayListVertex adjVertexs = vertex.getAdj();
for (int i = 0; i adjVertexs.size(); i++) {
if(!adjVertexs.get(i).isVisted){
return adjVertexs.get(i);
}
}
return null;
}
/////////////////////////////////////////////////////////////
private abstract class GraphIterator implements Iterator{
int count = 0;
public GraphIterator(){
}
public boolean hasNext() {
return count != getVertsCount()-1;
}
public Object next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub
}
}
//深度優(yōu)先迭代
private class DfsIterator extends GraphIterator{
public DfsIterator(){
super();
}
public Vertex next() {
return dfs[count++];
}
}
//廣度優(yōu)先迭代
private class BfsIterator extends GraphIterator{
public BfsIterator(){
super();
}
public Object next() {
return bfs[count++];
}
}
/////////////////////////////////////////////////////////
public static void main(String[] args) {
int nVerts = 10;
int c = 'A'-1;
Vertex vertex;
Graph myGraph = new Graph(nVerts, false);
for (int i = 0; i nVerts; i++) {
c++;
vertex = new Vertex((char)(c));
myGraph.addVertex(vertex);
}
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 4);
myGraph.addEdge(1, 2);
myGraph.addEdge(2, 3);
myGraph.addEdge(4, 5);
myGraph.addEdge(4, 6);
myGraph.addEdge(5, 8);
myGraph.addEdge(6, 7);
myGraph.addEdge(7, 8);
myGraph.addEdge(8, 9);
System.out.println("深度優(yōu)先迭代遍歷：");
for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
System.out.println("/n廣度優(yōu)先迭代遍歷：");
for (Iterator iterator = myGraph.bfsIterator(); iterator.hasNext();) {
vertex = (Vertex) iterator.next();
System.out.println(vertex.toString());
}
}
}
class Vertex{
public char label;
public boolean isVisted;
public int index;
private ArrayListVertex next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//為節(jié)點添加鄰接點
public void addAdj(Vertex ver){
if(next == null) next = new ArrayListVertex();
next.add(ver);
}
public ArrayListVertex getAdj(){
return next;
}
public void setIndex(int index){
this.index = index;
}
public String toString(){
return "頂點 "+label+",下標："+index+".";
}
}
代碼來自：
求代碼，java實驗，題目如圖
import?java.util.Scanner;
import?java.util.Stack;
public?class?DFS
{
//?存儲節(jié)點信息
private?char[]?vertices;
//?存儲邊信息（鄰接矩陣）
private?int[][]?arcs;
//?圖的節(jié)點數(shù)
private?int?vexnum;
//?記錄節(jié)點是否已被遍歷
private?boolean[]?visited;
//?初始化
public?DFS(int?n)
{
vexnum?=?n;
vertices?=?new?char[n];
arcs?=?new?int[n][n];
visited?=?new?boolean[n];
for(int?i?=?0;?i??vexnum;?i++)
{
for(int?j?=?0;?j??vexnum;?j++)
{
arcs[i][j]?=?0;
}
}
}
//?添加邊(無向圖)
public?void?addEdge(int?i,?int?j)
{
//?邊的頭尾不能為同一節(jié)點
if(i?==?j)
return;
arcs[i?-?1][j?-?1]?=?1;
arcs[j?-?1][i?-?1]?=?1;
}
//?設(shè)置節(jié)點集
public?void?setVertices(char[]?vertices)
{
this.vertices?=?vertices;
}
//?設(shè)置節(jié)點訪問標記
public?void?setVisited(boolean[]?visited)
{
this.visited?=?visited;
}
//?打印遍歷節(jié)點
public?void?visit(int?i)
{
System.out.print(vertices[i]?+?"?");
}
//?從第i個節(jié)點開始深度優(yōu)先遍歷
private?void?traverse(int?i)
{
//?標記第i個節(jié)點已遍歷
visited[i]?=?true;
//?打印當前遍歷的節(jié)點
visit(i);
//?遍歷鄰接矩陣中第i個節(jié)點的直接聯(lián)通關(guān)系
for(int?j?=?0;?j??vexnum;?j++)
{
//?目標節(jié)點與當前節(jié)點直接聯(lián)通，并且該節(jié)點還沒有被訪問，遞歸
if(arcs[i][j]?==?1??visited[j]?==?false)
{
traverse(j);
}
}
}
//?圖的深度優(yōu)先遍歷（遞歸）
public?void?DFSTraverse(int?start)
{
//?初始化節(jié)點遍歷標記
for(int?i?=?0;?i??vexnum;?i++)
{
visited[i]?=?false;
}
//?從沒有被遍歷的節(jié)點開始深度遍歷
for(int?i?=?start?-?1;?i??vexnum;?i++)
{
if(visited[i]?==?false)
{
//?若是連通圖，只會執(zhí)行一次
traverse(i);
}
}
}
//?圖的深度優(yōu)先遍歷（非遞歸）
public?void?DFSTraverse2(int?start)
{
//?初始化節(jié)點遍歷標記
for(int?i?=?0;?i??vexnum;?i++)
{
visited[i]?=?false;
}
StackInteger?s?=?new?StackInteger();
for(int?i?=?start?-?1;?i??vexnum;?i++)
{
if(!visited[i])
{
//?連通子圖起始節(jié)點
s.add(i);
do
{
//?出棧
int?curr?=?s.pop();
//?如果該節(jié)點還沒有被遍歷，則遍歷該節(jié)點并將子節(jié)點入棧
if(visited[curr]?==?false)
{
//?遍歷并打印
visit(curr);
visited[curr]?=?true;
//?沒遍歷的子節(jié)點入棧
for(int?j?=?vexnum?-?1;?j?=?0;?j--)
{
if(arcs[curr][j]?==?1??visited[j]?==?false)
{
s.add(j);
}
}
}
}?while(!s.isEmpty());
}
}
}
public?static?void?main(String[]?args)
{
Scanner?sc?=?new?Scanner(System.in);
int?N,?M,?S;
while(true)
{
System.out.println("輸入N?M?S，分別表示圖G的結(jié)點數(shù)，邊數(shù)，搜索的起點：");
String?line?=?sc.nextLine();
if(!line.matches("^\\s*([1-9]\\d?|100)(\\s+([1-9]\\d?|100)){2}\\s*$"))
{
System.out.print("輸入錯誤，");
continue;
}
String[]?arr?=?line.trim().split("\\s+");
N?=?Integer.parseInt(arr[0]);
M?=?Integer.parseInt(arr[1]);
S?=?Integer.parseInt(arr[2]);
break;
}
DFS?g?=?new?DFS(N);
char[]?vertices?=?new?char[N];
for(int?i?=?0;?i??N;?i++)
{
vertices[i]?=?(i?+?1?+?"").charAt(0);
}
g.setVertices(vertices);
for(int?m?=?0;?m??M;?m++)
{
System.out.println("輸入圖G的第"?+?(m?+?1)?+?"條邊，格式為“i?j”，其中i，j為結(jié)點編號（范圍是1~N）");
String?line?=?sc.nextLine();
if(!line.matches("^\\s*([1-9]\\d?|100)\\s+([1-9]\\d?|100)\\s*$"))
{
System.out.print("輸入錯誤，");
m--;
continue;
}
String[]?arr?=?line.trim().split("\\s+");
int?i?=?Integer.parseInt(arr[0]);
int?j?=?Integer.parseInt(arr[1]);
g.addEdge(i,?j);
}
sc.close();
System.out.print("深度優(yōu)先遍歷（遞歸）：");
g.DFSTraverse(S);
System.out.println();
System.out.print("深度優(yōu)先遍歷（非遞歸）：");
g.DFSTraverse2(S);
}
}
BFS求源代碼及思路？
1、算法用途：
是一種圖像搜索演算法。用于遍歷圖中的節(jié)點，有些類似于樹的深度優(yōu)先遍歷。這里唯一的問題是，與樹不同，圖形可能包含循環(huán)，因此我們可能會再次來到同一節(jié)點。
2、主要思想：
主要借助一個隊列、一個布爾類型數(shù)組、鄰接矩陣完成（判斷一個點是否查看過，用于避免重復到達同一個點，造成死循環(huán)等），先將各點以及各點的關(guān)系存入鄰接矩陣。
再從第一個點開始，將一個點存入隊列，然后在鄰接表中找到他的相鄰點，存入隊列，每次pop出隊列頭部并將其打印出來（文字有些抽象，實際過程很簡單），整個過程有點像往水中投入石子水花散開。
（鄰接表是表示了圖中與每一個頂點相鄰的邊集的集合，這里的集合指的是無序集）
3、代碼（java）：
(以上圖為例的代碼）
1 import java.util.*; 2 ?3 //This class represents a directed graph using adjacency list
4 //representation ?5 class Graph1 { 6 ? ? private static int V; // No. of vertices 7 ? ? private LinkedListInteger a Lists 8 ?9 ? ? // Constructor10 ? ? Graph1(int v) {11 ? ? ? ? V = v;12 ? ? ? ? adj = new LinkedList[v];13 ? ? ? ? for (int i = 0; i v; ++i)14 ? ? ? ? ? ? adj[i] = new LinkedList();15 ?? ?}16 17 ? ? // Function to add an edge into the graph18 ? ? void addEdge(int v, int w) {19 ?? ? ? ?adj[v].add(w);20 ?? ?}21 22 ? ? // prints BFS traversal from a given source s23 ? ? public void BFS() {24 ? ? ? ? // Mark all the vertices as not visited(By default25 ? ? ? ? // set as false)26 ? ? ? ? boolean visited[] = new boolean[V];27 ? ? ? ? // Create a queue for BFS28 ? ? ? ? LinkedListInteger queue = new LinkedListInteger();29 30 ? ? ? ? for (int i = 0; i V; i++) {31 ? ? ? ? ? ? if (!visited[i]) {32 ?? ? ? ? ? ? ? ?BFSUtil(i, visited, queue);33 ?? ? ? ? ? ?}34 ?? ? ? ?}35 ?? ?}36 37 ? ? public void BFSUtil(int s, boolean visited[], LinkedListInteger queue) {38 ? ? ? ? // Mark the current node as visited and enqueue it39 ? ? ? ? visited[s] = true;40 ?? ? ? ?queue.add(s);41 42 ? ? ? ? while (queue.size() != 0) {43 ? ? ? ? ? ? // Dequeue a vertex from queue and print it44 ? ? ? ? ? ? s = queue.poll();45 ? ? ? ? ? ? System.out.print(s + " ");46 47 ? ? ? ? ? ? // Get all adjacent vertices of the dequeued vertex s48 ? ? ? ? ? ? // If a adjacent has not been visited, then mark it49 ? ? ? ? ? ? // visited and enqueue it50 ? ? ? ? ? ? IteratorInteger i = adj[s].listIterator();51 ? ? ? ? ? ? while (i.hasNext()) {52 ? ? ? ? ? ? ? ? int n = i.next();53 ? ? ? ? ? ? ? ? if (!visited[n]) {54 ? ? ? ? ? ? ? ? ? ? visited[n] = true;55 ?? ? ? ? ? ? ? ? ? ?queue.add(n);56 ?? ? ? ? ? ? ? ?}57 ?? ? ? ? ? ?}58 ?? ? ? ?}59 ?? ?}60 61 ? ? // Driver method to62 ? ? public static void main(String args[]) {63 ? ? ? ? Graph1 g = new Graph1(4);64 65 ? ? ? ? g.addEdge(0, 1);66 ? ? ? ? g.addEdge(0, 2);67 ? ? ? ? g.addEdge(1, 2);68 ? ? ? ? g.addEdge(2, 0);69 ? ? ? ? g.addEdge(2, 3);70 ? ? ? ? g.addEdge(3, 3);71 72 ? ? ? ? System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");73 ?? ? ? ?g.BFS();74 ?? ?}75 }
4、復雜度分析：
算法借助了一個鄰接表和隊列，故它的空問復雜度為O(V）。 遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程，其耗費的時間取決于所采用結(jié)構(gòu)。 鄰接表表示時，查找所有頂點的鄰接點所需時間為O(E)，訪問頂點的鄰接點所花時間為O（V）,此時，總的時間復雜度為O(V+E)。
求助一個graph.java主程序及子程序，并請講一講它實現(xiàn)的功能
我有一個主程序NOTEBO0K.java
主程序中設(shè)置了一個“字體”選擇菜單fontmenuitem
我想在按下fontmenuitem菜單時就可彈出字體對話框font
假如字體對話框在子程序FontDialog.java中實現(xiàn)。
在主程序NOTEBO0K.java：
public?class?NOTEBO0K（）{
.....
//設(shè)置“字體”選擇菜單fontmenuitem的事件
ActionListener?fontsetting=new?ActionListener(){
public?void?actionPerformed(ActionEvent?e)?
{
FontDialog??font=new??FontDialog(this);//想在這里引入字體對話框
font.setLocation(80,50);
font.setModal(true);?
font.show();?
}
};
fontmenuitem.addActionListener(fontsetting);
}
在//FontDialog.java
public?class?FontDialog?extends?JDialog
{
......
JTextField?nameTxt=new?JTextField("Default");//nameTxt來表示取得的字體名
JTextField?styleTxt=new?JTextField("Plain");
JTextField?sizeTxt=new?JTextField("15");
......... //選擇字體的過程
String?name=nameTxt.getText();//name來表示取得的字體名
int?style=((Integer)styleTbl.get(styleTxt.getText())).intValue();
//style來表示取得的字體類型
String?sizeStr=sizeTxt.getText().trim();//sizeStr來表示取得的字體大小
......
}
當前名稱：鄰接表代碼JAVA 鄰接表c++實現(xiàn)
標題來源：http://fisionsoft.com.cn/article/ddceeih.html
