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)的意思是每次插入一條邊，都需要重新查找邊所包含兩個頂點信息對應的下標，正常的演算法沒這么弱智吧，不需要頂點信息即為頂點的下標，用散列等方法可以不用這樣的