A. 图的邻接表
1.可以。
2.如果a->b和b->a均在邻接表里成对存在，则是无向图的邻接表，否则是有向图的邻接表。a和b是图中顶点。
B. 如何实时更新邻接表边的权值java
本系列文章主要学习如何使用JAVA语言以邻接表的方式实现了数据结构---图（Graph），这是第一篇文章，学习如何用JAVA来表示图的顶点。从数据的表示方法来说，有二种表示图的方式：一种是邻接矩阵，其实是一个二维数组；一种是邻接表，其实是一个顶点表，每个顶点又拥有一个边列表。下图是图的邻接表表示。
从图中可以看出，图的实现需要能够表示顶点表，能够表示边表。邻接表指是的哪部分呢？每个顶点都有一个邻接表，一个指定顶点的邻接表中，起始顶点表示边的起点，其他顶点表示边的终点。这样，就可以用邻接表来实现边的表示了。如顶点V0的邻接表如下：
与V0关联的边有三条，因为V0的邻接表中有三个顶点(不考虑V0)。
C. 如题，以邻接表存储图，并对图进行深度优先遍历
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXVEX 100
typedef char VertexType[3];/*定义VertexType为char数组类型*/
typedef struct vertex
{int adjvex; /*顶点编号*/VertexType data; /*顶点的信息*/ } VType;/*顶点类型*/
typedef struct graph
{int n,e;/*n为实际顶点数,e为实际边数*/
VType vexs[MAXVEX];/*顶点集合*/
int edges[MAXVEX][MAXVEX];/*边的集合*/
} AdjMatix;/*图的邻接矩阵类型*/
typedef struct edgenode
{int adjvex; /*邻接点序号*/ int value;/*边的权值*/struct edgenode *next;/*下一顶点*/
} ArcNode;/*每个顶点建立的单链表中结点的类型*/
typedef struct vexnode
{VertexType data; /*结点信息*/ArcNode *firstarc;/*指向第一条边结点*/
} VHeadNode;/*单链表的头结点类型*/
typedef struct
{int n,e;/*n为实际顶点数,e为实际边数*/
VHeadNode adjlist[MAXVEX];/*单链表头结点数组*/
} AdjList; /*图的邻接表类型*/
void DispAdjList(AdjList *G)
{int i;
ArcNode *p;
printf("图的邻接表表示如下:\n");
for (i=0;i<G->n;i++)
{printf(" [%d,%3s]=>",i,G->adjlist[i].data);
p=G->adjlist[i].firstarc;
while (p!=NULL)
{printf("(%d,%d)->",p->adjvex,p->value);p=p->next;}printf("∧\n");
}
}
void MatToList(AdjMatix g,AdjList *&G) /*将邻接矩阵g转换成邻接表G*/
{int i,j;ArcNode *p;
G=(AdjList *)malloc(sizeof(AdjList));
for (i=0;i<g.n;i++)/*给邻接表中所有头结点的指针域置初值*/
{G->adjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);}
for (i=0;i<g.n;i++)/*检查邻接矩阵中每个元素*/
for (j=g.n-1;j>=0;j--)
if (g.edges[i][j]!=0)/*邻接矩阵的当前元素不为0*/
{p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
p->value=g.edges[i][j];p->adjvex=j;
p->next=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p;}
G->n=g.n;G->e=g.e;
}
int visited[MAXVEX];
void DFS(AdjList *g,int vi)/*对邻接表G从顶点vi开始进行深度优先遍历*/
{ArcNode *p;printf("%d ",vi);/*访问vi顶点*/ visited[vi]=1;/*置已访问标识*/
p=g->adjlist[vi].firstarc;/*找vi的第一个邻接点*/
while (p!=NULL)/*找vi的所有邻接点*/
{if (visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next; }
}
void main()
{int i,j,k,a[9][9];AdjMatix g;AdjList *G;
char *vname[MAXVEX]={"a","b","c","d","e","f","g","h","i"};
printf("输入定点数(<10)，边数");
scanf("%d,%d",&i,&k);
g.n=i;g.e=2*k;
for (i=0;i<g.n;i++)strcpy(g.vexs[i].data,vname[i]);
for (i=0;i<g.n;i++)
for (j=0;j<g.e;j++)g.edges[i][j]=0; /*a[i][j];*/
for(k=0;k<g.e/2;k++)
{printf("请输入第%d条边的起点和终点序号(逗点分隔)",k);scanf("%d,%d",&i,&j);
g.edges[i][j]=g.edges[j][i]=1;}
MatToList(g,G);/*生成邻接表*/ DispAdjList(G);/*输出邻接表*/
for (i=0;i<g.n;i++)visited[i]=0; /*顶点标识置初值*/
printf("从顶点0的深度优先遍历序列:\n");printf(" 递归算法:");DFS(G,0);printf("\n");
}
D. 用JAVA写图的操作与实现
...
这不是数据结构么
书上应该有算法, 好好看看书吧
图应该是邻接表存储方式, 存储方式弄好了, 就是算法的事情了, 书上都有
不过毕业这么多年了, 除了遍历, 其他都记不清了...
E. java中如何把图用邻接表表示出来
package my.graph;
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[start].addAdj(vertexList[end]);
if (!is) {vertexList[end].addAdj(vertexList[start]);}
}
/**
* 返回节点个数
* @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(){
ArrayList<Vertex> next = null;
for (int i = 0; i < vertexList.length; i++) {
printVertx(vertexList[i]);
}
}
public void printVertx(Vertex vertex){
ArrayList<Vertex> 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){
ArrayList<Vertex> 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 ArrayList<Vertex> next = null;
public Vertex(char lab) // constructor
{
label = lab;
isVisted = false;
}
//为节点添加邻接点
public void addAdj(Vertex ver){
if(next == null) next = new ArrayList<Vertex>();
next.add(ver);
}
public ArrayList<Vertex> getAdj(){
return next;
}
public void setIndex(int index){
this.index = index;
}
public String toString(){
return "顶点 "+label+",下标："+index+".";
}
}
代码来自：http://blog.csdn.net/Java2King/article/details/5683429
F. 图的邻接表的时间复杂度问题
其实是O(n + e)，顶点加上边数
那个O(n*e)的意思是每次插入一条边，都需要重新查找边所包含两个顶点信息对应的下标，正常的算法没这么弱智吧，不需要顶点信息即为顶点的下标，用散列等方法可以不用这样的