邻接表代码JAVA 邻接表c++实现

java中如何把图用邻接表表示出来

package my.graph;

成都创新互联公司是一家专注于成都网站设计、做网站、成都外贸网站建设公司与策划设计,延津网站建设哪家好?成都创新互联公司做网站,专注于网站建设十多年,网设计领域的专业建站公司;建站业务涵盖:延津等地区。延津做网站价格咨询: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);}

}

/**

* 返回节点个数

* @return

*/

public int getVertsCount(){

return vertexList.length;

}

/**

* 深度优先迭代器

* @return

*/

public Iterator dfsIterator(){

dfs();

return new DfsIterator();

}

/**

* 广度优先迭代器

* @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

}

}

//深度优先迭代

private class DfsIterator extends GraphIterator{

public DfsIterator(){

super();

}

public Vertex next() {

return dfs[count++];

}

}

//广度优先迭代

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("深度优先迭代遍历：");

for (Iterator iterator = myGraph.dfsIterator(); iterator.hasNext();) {

vertex = (Vertex) iterator.next();

System.out.println(vertex.toString());

}

System.out.println("/n广度优先迭代遍历：");

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;

}

//为节点添加邻接点

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

{

// 存储节点信息

private char[] vertices;

// 存储边信息（邻接矩阵）

private int[][] arcs;

// 图的节点数

private int vexnum;

// 记录节点是否已被遍历

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)

{

// 边的头尾不能为同一节点

if(i == j)

return;

arcs[i - 1][j - 1] = 1;

arcs[j - 1][i - 1] = 1;

}

// 设置节点集

public void setVertices(char[] vertices)

{

this.vertices = vertices;

}

// 设置节点访问标记

public void setVisited(boolean[] visited)

{

this.visited = visited;

}

// 打印遍历节点

public void visit(int i)

{

System.out.print(vertices[i] + " ");

}

// 从第i个节点开始深度优先遍历

private void traverse(int i)

{

// 标记第i个节点已遍历

visited[i] = true;

// 打印当前遍历的节点

visit(i);

// 遍历邻接矩阵中第i个节点的直接联通关系

for(int j = 0; j  vexnum; j++)

{

// 目标节点与当前节点直接联通，并且该节点还没有被访问，递归

if(arcs[i][j] == 1  visited[j] == false)

{

traverse(j);

}

}

}

// 图的深度优先遍历（递归）

public void DFSTraverse(int start)

{

// 初始化节点遍历标记

for(int i = 0; i  vexnum; i++)

{

visited[i] = false;

}

// 从没有被遍历的节点开始深度遍历

for(int i = start - 1; i  vexnum; i++)

{

if(visited[i] == false)

{

// 若是连通图，只会执行一次

traverse(i);

}

}

}

// 图的深度优先遍历（非递归）

public void DFSTraverse2(int start)

{

// 初始化节点遍历标记

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])

{

// 连通子图起始节点

s.add(i);

do

{

// 出栈

int curr = s.pop();

// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈

if(visited[curr] == false)

{

// 遍历并打印

visit(curr);

visited[curr] = true;

// 没遍历的子节点入栈

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的结点数，边数，搜索的起点：");

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为结点编号（范围是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("深度优先遍历（递归）：");

g.DFSTraverse(S);

System.out.println();

System.out.print("深度优先遍历（非递归）：");

g.DFSTraverse2(S);

}

}

BFS求源代码及思路？

1、算法用途：

是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。

2、主要思想：

主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。

再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，每次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）。 遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。

求助一个graph.java主程序及子程序，并请讲一讲它实现的功能

我有一个主程序NOTEBO0K.java

主程序中设置了一个“字体”选择菜单fontmenuitem

我想在按下fontmenuitem菜单时就可弹出字体对话框font

假如字体对话框在子程序FontDialog.java中实现。

在主程序NOTEBO0K.java：

public class NOTEBO0K（）{

.....

//设置“字体”选择菜单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来表示取得的字体大小

......

}