Ⅰ 如何用鄰接表存儲圖結構
我看不太懂這個程序，不過我有些過圖的鄰接表表示，看對你有沒有幫助吧。
#include <iostream>
#include <fstream>
#include <vector>
typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //圖的最大頂點數
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局變數--訪問標志數組
typedef struct ArcNode{
//弧結點
int adjvex; //該弧所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條弧的指針
InfoType *info; //保存邊的信息，可以簡單的改為 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
class Graph{
public: AdjList vertices; //記錄頂點信息，指向第一條依附該頂點的弧的指針
int vexnum,arcnum; //圖的當前頂點和弧數
int GraphKind; //圖的種類，0---無向圖，1---有向圖
Graph(int vexnum,int arcnum,int kind)
{
this->vexnum=vexnum;
this->arcnum=arcnum;
this->GraphKind=kind;
}
};
void CreateGraph(Graph &G,VertexType *V,ArcType *VR){
//構造鄰接表結構的圖G
int i;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) //初始化指針數組
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
s->nextarc=G.vertices[VR[i].start].firstarc; //插入到鄰接表中
s->adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;
if(G.GraphKind==0) {
//若是無向圖，再插入到終點的弧鏈中
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.vertices[VR[i].end].firstarc;
s->adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}
Ⅱ 用鄰接表作為存儲結構,實現對上圖的拓撲排序
程序運行結果:
1-3->2->4->5
對應樓主的圖數據為：
5 7
1 2
1 4
1 3
2 4
3 4
4 5
2 5
代碼：
#include<cstdio>
intnext[100],first[100],en[100],ru[100],n,m,dl[100],head=0,tail=0;
intmain()
{
freopen("t2.in","r",stdin);
scanf("%d%d",&n,&m);//讀入頂點數和邊數
for(inti=1;i<m;i++)//讀入有向邊
{
intx,y;
scanf("%d%d",&x,&y);
next[i]=first[x];
first[x]=i;
en[i]=y;
ru[y]++;
}
//用隊列來進行拓撲排序
for(inti=1;i<=n;i++)//找到入度為0的點入隊
if(ru[i]==0)
{
ru[i]==-1;//將這個點去掉。
dl[++tail]=i;//入隊
}
while(head<tail)
{
intx=dl[++head];
intp=first[x];
while(p!=0)//和這個點相連的邊刪去
{
inty=en[p];
ru[y]--;//則對應的點的入度會減少
if(ru[y]==0)//如果再次找到了入度為0的點則入隊
{
ru[y]=-1;
dl[++tail]=y;
}
p=next[p];
}
}
//最後直接輸出整個隊列元素，從1到尾
intflag=0;
for(inti=1;i<=tail;i++)
if(!flag)
{
flag=1;
printf("%d",dl[i]);
}elseprintf("->%d",dl[i]);
printf(" ");
return0;
}
Ⅲ 圖中的這道題 求代碼 (有向無環圖 拓撲排序 基於鄰接表存儲結構)
鄰接表還是逆鄰接表？如果是逆鄰接表，每個頂點出發鄰接表的鏈表中的結點個數就是入度如果是鄰接表過程如下：有一個輔助數組，大小就是頂點數量，所有元素初值都為0從頭到尾遍歷每個頂點出發的鄰接表的結點，只要當前結點的數據是幾（也就是第幾個結點被有向弧進入了），這個下標的輔助數組元素加1，等所有的鄰接表的小鏈表遍歷完了，這個輔助數組中各個下標的數字就是該頂點的入度
Ⅳ 以鄰接多重表為存儲結構，實現連通無向圖的深度優先遍歷和廣度優先遍歷。
沒有現成的，自己看看套用一下吧。
鄰接多重表
/*********************************************************
Title : graph-multiadjacentlist.c
Author :
Time :
Purpose : 圖的多重鄰接鏈表表示法
Thread :
Comment :
Usage :
**********************************************************/
#include "stdio.h"
#include "stdlib.h"
/*=====================變數聲明--variable declaration=================*/
struct edge /* 圖形邊線結構聲明 */
{
int vertex1; /* 頂點1資料 */
int vertex2; /* 頂點2資料 */
struct edge *edge1; /* 頂點1下一邊線 */
struct edge *edge2; /* 頂點2下一邊線 */
};
typedef struct edge *nextedge; /* 圖形的邊線新型態 */
struct node /* 圖形頂點結構宣告 */
{
int vertex; /* 頂點資料 */
struct edge *edge; /* 頂點下一邊線 */
};
typedef struct node *graph; /* 圖形的結構新型態 */
struct node head[6]; /* 圖形頂點結構數組 */
/*=====================函數聲明--function declaration=================*/
void creategraph(int *node,int num);
/*====================函數實現--function implementation================*/
/* --------------------------------------------------
Function : void creategraph()
Purpose :
Arguments :
Returns :
------------------------------------------------- */
void creategraph(int *node,int num)
{
nextedge newnode; /* 新邊線指標 */
nextedge previous; /* 前一邊線指標 */
nextedge ptr; /* 目前邊線指標 */
int from; /* 邊線的起點 */
int to; /* 邊線的終點 */
int i;
for ( i = 0; i < num; i++ ) { /* 讀取邊線的迴路 */
from = node[i*2]; /* 邊線的起點 */
to = node[i*2+1]; /* 邊線的終點 */
/* 建立新邊線記憶體 */
newnode = ( nextedge ) malloc(sizeof(struct edge));
newnode->vertex1 = from; /* 建立頂點內容 */
newnode->vertex2 = to; /* 建立頂點內容 */
newnode->edge1 = NULL; /* 設定指標初值 */
newnode->edge2 = NULL; /* 設定指標初值 */
previous = NULL; /* 前一邊線指標 */
ptr = head[from].edge; /* 目前邊線指標 */
while ( ptr != NULL ) { /* 遍歷到最後邊線 */
previous = ptr; /* 保留前一邊線 */
if ( ptr->vertex1 == from ) /* 決定走的邊線 */
ptr = ptr->edge1; /* 下一邊線 */
else
ptr = ptr->edge2; /* 下一邊線 */
}
if ( previous == NULL )
head[from].edge = newnode; /* 設定頂點邊線指標 */
else
if ( previous->vertex1 == from ) /* 決定走的邊線 */
previous->edge1 = newnode; /* 連接下一邊線 */
else
previous->edge2 = newnode; /* 連接下一邊線 */
previous = NULL; /* 前一邊線指標 */
ptr = head[to].edge; /* 目前邊線指標 */
while ( ptr != NULL ) { /* 遍歷到最後邊線 */
previous = ptr; /* 保留前一邊線 */
if ( ptr->vertex1 == to ) /* 決定走的邊線 */
ptr = ptr->edge1; /* 下一邊線 */
else
ptr = ptr->edge2; /* 下一邊線 */
}
if ( previous == NULL )
head[to].edge = newnode; /* 設定頂點邊線指標 */
else
if ( previous->vertex1 == to ) /* 決定走的邊線 */
previous->edge1 = newnode; /* 連接下一邊線 */
else
previous->edge2 = newnode; /* 連接下一邊線 */
}
}
/*======================主函數--main function--建立圖形後,將邊線列印出========================*/
int main(int argc, char* argv[])
{
nextedge ptr;
int node[6][2] = { {1, 2}, /* 邊線數組 */
{1, 3},
{2, 3},
{2, 4},
{3, 5},
{4, 5}, };
int i;
for ( i = 1; i <= 5; i++ ) {
head.vertex = i; /* 設定頂點值 */
head.edge = NULL; /* 清除圖形指標 */
}
creategraph(node,6); /* 建立圖形 */
printf("圖形的多重鄰接鏈表內容:\n");
for ( i = 1; i <= 5; i++ ) {
printf("頂點%d =>",head.vertex); /* 頂點值 */
ptr = head.edge;
/* 邊線位置 */
while ( ptr != NULL ) { /* 遍歷至鏈表尾 */
/* 印出邊線 */
printf("(%d,%d)",ptr->vertex1,ptr->vertex2);
/* 決定下一邊線指標 */
if ( head.vertex == ptr->vertex1 )
ptr = ptr->edge1; /* 下一個邊線 */
else
ptr = ptr->edge2; /* 下一個邊線 */
}
printf("\n"); /* 換行 */
}
return 1;
}
// 圖的遍歷 *
// 生成，深度、廣度優先遍歷 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
#define MAXQSIZE 30 //隊列的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex; //該弧所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條弧的指針
}ArcNode; //弧結點
typedef struct
{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針
int vexnum,arcnum; //圖的當前頂點和弧數
int GraphKind; //圖的種類，0---無向圖，1---有向圖
}Graph;
typedef struct //隊列結構
{int elem[MAXQSIZE]; //數據域
int front; //隊頭指針
int rear; //隊尾指針
}SqQueue;
BOOL visited[MAX_VERTEX_NUM]; //全局變數——訪問標志數組
void CreateGraph(Graph &); //生成圖的鄰接表
void DFSTraverse(Graph); //深度優先搜索遍歷圖
void DFS(Graph,int);
void BFSTraverse(Graph); //廣度優先搜索遍歷圖
void Initial(SqQueue &); //初始化一個隊列
BOOL QueueEmpty(SqQueue); //判斷隊列是否空
BOOL EnQueue(SqQueue &,int); //將一個元素入隊列
BOOL DeQueue(SqQueue &,int &); //將一個元素出隊列
int FirstAdjVex(Graph,int); //求圖中某一頂點的第一個鄰接頂點
int NextAdjVex(Graph,int,int); //求某一頂點的下一個鄰接頂點
void main()
{Graph G; //採用鄰接表結構的圖
char j='y';
//------------------程序解說----------------------------
printf("本程序將演示生成一個圖，並對它進行遍歷.
");
printf("首先輸入要生成的圖的種類.
");
printf("0---無向圖, 1--有向圖
");
printf("之後輸入圖的頂點數和弧數。
格式：頂點數，弧數；例如:4,3
");
printf("接著輸入各邊(弧尾，弧頭).
例如:
1,2
1,3
2,4
");
printf("程序會生成一個圖，並對它進行深度和廣度遍歷.
");
printf("深度遍歷:1->2->4->3
廣度遍歷:1->2->3->4
");
//------------------------------------------------------
while(j!='N'&&j!='n')
{printf("請輸入要生成的圖的種類(0/1):");
scanf("%d",&G.GraphKind); //輸入圖的種類
printf("請輸入頂點數和弧數：");
scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和弧數
CreateGraph(G); //生成鄰接表結構的圖
DFSTraverse(G); //深度優先搜索遍歷圖
BFSTraverse(G); //廣度優先搜索遍歷圖
printf("圖遍歷完畢，繼續進行嗎?(Y/N)");
scanf(" %c",&j);
}
}
void CreateGraph(Graph &G)
{//構造鄰接表結構的圖G
int i;
int start,end;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) G.AdjList=NULL; //初始化指針數組
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d",&start,&end); //輸入弧的起點和終點
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
s->nextarc=G.AdjList[start]; //插入到鄰接表中
s->adjvex=end;
G.AdjList[start]=s;
if(G.GraphKind==0) //若是無向圖，再插入到終點的弧鏈中
{s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
}
void DFSTraverse(Graph G)
{//深度優先遍歷圖G
int i;
printf("DFSTraverse:");
for(i=1;i<=G.vexnum;i++) visited=False; //訪問標志數組初始化
for(i=1;i<=G.vexnum;i++)
if(!visited) DFS(G,i); //對尚未訪問的頂點調用DFS
printf("\b\b
");
}
void DFS(Graph G,int i)
{//從第i個頂點出發遞歸地深度遍歷圖G
int w;
visited=True; //訪問第i個頂點
printf("%d->",i);
for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
if(!visited[w]) DFS(G,w); //對尚未訪問的鄰接頂點w調用DFS
}
void BFSTraverse(Graph G)
{//按廣度優先非遞歸的遍歷圖G，使用輔助隊列Q和訪問標志數組visited
int i,u,w;
SqQueue Q;
printf("BFSTreverse:");
for(i=1;i<= G.vexnum;i++) visited=False; //訪問標志數組初始化
Initial(Q); //初始化隊列
for(i=1;i<=G.vexnum;i++)
if(!visited)
{visited=True; //訪問頂點i
printf("%d->",i);
EnQueue(Q,i); //將序號i入隊列
while(!QueueEmpty(Q)) //若隊列不空，繼續
{DeQueue(Q,u); //將隊頭元素出隊列並置為u
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!visited[w]) //對u的尚未訪問的鄰接頂點w進行訪問並入隊列
{visited[w]=True;
printf("%d->",w);
EnQueue(Q,w);
}
}
}
printf("\b\b
");
}
int FirstAdjVex(Graph G,int v)
{//在圖G中尋找第v個頂點的第一個鄰接頂點
if(!G.AdjList[v]) return 0;
else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{//在圖G中尋找第v個頂點的相對於u的下一個鄰接頂點
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=u) p=p->nextarc; //在頂點v的弧鏈中找到頂點u
if(p->nextarc==NULL) return 0; //若已是最後一個頂點，返回0
else return(p->nextarc->adjvex); //返回下一個鄰接頂點的序號
}
void Initial(SqQueue &Q)
{//隊列初始化
Q.front=Q.rear=0;
}
BOOL QueueEmpty(SqQueue Q)
{//判斷隊列是否已空，若空返回True,否則返回False
if(Q.front==Q.rear) return True;
else return False;
}
BOOL EnQueue(SqQueue &Q,int ch)
{//入隊列，成功返回True，失敗返回False
if((Q.rear+1)%MAXQSIZE==Q.front) return False;
Q.elem[Q.rear]=ch;
Q.rear=(Q.rear+1)%MAXQSIZE;
return True;
}
BOOL DeQueue(SqQueue &Q,int &ch)
{//出隊列,成功返回True，並用ch返回該元素值，失敗返回False
if(Q.front==Q.rear) return False;
ch=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return True; //成功出隊列，返回True
}
轉載
Ⅳ 鄰接表存儲結構適合存儲什麼樣的圖
圖的鄰接表數據類型描述如下：
const int N=maxn； // maxn表示圖中最大頂點數
const int E=maxe ； // maxe圖中最大邊數
struct Edge{
int u,v; //邊所鄰接的兩個頂點
int w; //邊的權值
int next; //邊指針，指向下一條邊的內存池地址
}edge[E]; // 靜態內存池，用於分配邊
int head[N]; // 表頭
int num; // 內存池的指針
Ⅵ 用鄰接表表示圖的廣度優先搜索時的存儲結構,通常採用什麼結構來實現演算法
B
鄰接表表示的圖的廣度優先搜索一般採用隊列結構來實現演算法：
首先選擇一個起始節點，把它的臨界表中節點加入到隊列中，每次取出隊首元素，然後把該元素的鄰接表中的節點加入到隊列末尾，標記已遍歷過的節點，直到隊列中沒有節點為止
一般棧用於深度優先搜索，隊列用於廣度優先搜索
Ⅶ 無向圖採用鄰接表存儲結構,編寫演算法輸出圖中各連通分量的節點序列
//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.僅適用於鄰接表結構
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表結點
LinkQueue Q;//鏈隊列類型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值為未被訪問
}
InitQueue(&Q);//初始化輔助隊列Q
for (v=0; v<G.vexnum; ++v)//如果是連通圖，只v=0就遍歷全圖
{
if (! visited[v])//v尚未被訪問
{
visited[v] = TRUE;//設v為已被訪問
Visit(G.vertices[v].data);//訪問v
EnQueue(&Q,v);//v入隊
while (! QueueEmpty(Q))//隊列不空
{
DeQueue(&Q,&u);//隊頭元素出隊並置為u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的鄰接頂點
{
if (! visited[p->data.adjvex])//u的鄰接頂點尚未被訪問
{
visited[p->data.adjvex] = TRUE;//該鄰接頂點設為已被訪問
Visit(G.vertices[p->data.adjvex].data);//訪問該鄰接頂點
EnQueue(&Q,p->data.adjvex);//入隊該鄰接頂點序號
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
Ⅷ 編程實現以鄰接表或鄰接矩陣為存儲結構，圖的廣度和深度優先搜索
/*******************************************
圖的遍歷演示
以鄰接多重表為存儲結構,實現連通無向圖的深度優先和廣度優先遍歷.
以用戶指定的結點為起點,分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集.
*******************************************/
#include<iostream>
# include <string.h>
# include <malloc.h>
# include <conio.h>
using namespace std;
int visited[30];
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode //弧
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//表頭
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct//圖
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph &G)
{
int k,i,v1;
cout<<endl<<"請輸入結點個數: ";
cin>>G.vexnum;
cout<<"請輸入弧的個數: ";
cin>>G.arcnum;
for(i=1;i<=G.vexnum;i++)//初使化表頭
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=1;k<=G.vexnum;k++) //輸入邊
{
int v2;
cout<<"請輸入與結點"<<k<<"相鄰的邊數:";
cin>>v2;
cout<<"請輸入與第"<<k<<"個結點相連的結點編號: ";
cin>>v1;
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p->adjvex=v1;
p->nextarc=NULL;
G.vertices[k].firstarc=p;
for(int i=1;i<v2;i++)
{
int m;
cout<<"請輸入與第"<<k<<"個結點相連的結點編號: ";
cin>>m;
ArcNode *q;
q=(ArcNode *)malloc(sizeof(ArcNode));//動態指針
if(!q) exit(-1);
q->adjvex=m; //頂點給P
q->nextarc=NULL;
p->nextarc=q;
p=q;
//free(q);
}
//free(p);
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
ArcNode *x;
x=(ArcNode*)malloc(sizeof(ArcNode));
if(!x) exit(-1);
x=G.vertices[v].firstarc;
int w;
for (;x;x=x->nextarc)
{ w=x->adjvex;
if(visited[w]==0)
DFS(G,w);
}
}
void DFSB (ALGraph G,int v)//深度搜索的邊集
{
visited[v]=1;
ArcNode *y;
y=(ArcNode*)malloc(sizeof(ArcNode));
if(!y) exit(-1);
y=G.vertices[v].firstarc;
int u=G.vertices[v].data;
int w;
for(;y;y=y->nextarc)
{ w=y->adjvex;
if(visited[w]==0)
{
cout<<u<<"--->"<<w<<endl;
DFSB(G,w);
}
}
}
typedef struct QNode
{
int data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue (LinkQueue &Q)//建立一個空隊列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(-1);
Q.front->next=NULL;
}
void EnQueue (LinkQueue &Q,int e)//進隊
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
//free(p);
}
int DeQueue (LinkQueue &Q,int &e)//出隊
{
if(Q.front==Q.rear)
return -1;
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
int QueueEmpty (LinkQueue Q)//判斷隊列是否為空
{
if(Q.front==Q.rear)
return 1;
return 0;
}
void BFS(ALGraph G,int v)//廣度搜索
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *z;
z=(ArcNode*)malloc(sizeof(ArcNode));
if(!z) exit(-1);
z=G.vertices[u].firstarc;
/*
for(int w=z->adjvex;w>=0;w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}*/
int w;
for(;z;z=z->nextarc)
{ w=z->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}
}
}
}
void BFSB (ALGraph G,int v)//廣度搜索的邊集
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *r;
r=(ArcNode*)malloc(sizeof(ArcNode));
if(!r) exit(-1);
r=G.vertices[u].firstarc;
int w;
for(;r!=NULL;r=r->nextarc)
{ w=r->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<u<<"--->"<<w<<endl;
EnQueue(Q,w);
}
}
}
}
}
int main()
{
int i;
ALGraph G;
CreateDG(G);
int x;
cout<<"請輸入結點數:";
cin>>x;
cout<<"鄰接表為："<<endl;
for(int j=1;j<=x;j++)
{
cout<<G.vertices[j].data<<" ";
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p=G.vertices[j].firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
cout<<"請輸入第一個要訪問的結點序號："<<endl;
int n;
cin>>n;
for( i=0;i<30;i++)
visited[i]=0;
cout<<"廣度搜索："<<endl;
BFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"邊集："<<endl;
BFSB(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<"深度搜索："<<endl;
DFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"邊集："<<endl;
DFSB(G,n);
//system("pause");
return 0;
}
前幾天上機剛好做了這個,個人感覺很完美,盡管老師說用的是鄰接表而不是多重表,太簡單,但還不錯,界面輸入過程比較繁瑣,要嚴格按照提示來輸入,是無向圖,等級太低,沒辦法把執行結果粘出來,應該能看懂吧
Ⅸ 鄰接表的簡介
圖的鄰接矩陣存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。如詞條概念圖所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
鄰接表是圖的一種最主要存儲結構,用來描述圖上的每一個點。對圖的每個頂點建立一個容器（n個頂點建立n個容器），第i個容器中的結點包含頂點Vi的所有鄰接頂點。實際上我們常用的鄰接矩陣就是一種未離散化每個點的邊集的鄰接表。
在有向圖中，描述每個點向別的節點連的邊（點a->點b這種情況）。
在無向圖中，描述每個點所有的邊(點a-點b這種情況)
與鄰接表相對應的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。
工業上有很多非常好的圖庫的實現,例如C++的boost graph庫.如果可以，盡量用這些庫，這樣可以大大提高你的效率。
Ⅹ 以鄰接表作存儲結構實現求源點到其餘各頂點的最短路徑的Dijkstra演算法
具體演算法為：
//Dijkstra求單源最短路徑
#include<stdio.h>
#define N 20 //圖的頂點最多數
#define MAX 1000
#define MIN -1
typedef int ElemType;//圖的頂點標識，這里為自然數
//圖的結點結構
typedef struct ArcNode{
ElemType adjvex;//圖的頂點 （該弧指向頂點的位置）
struct ArcNode *nextarc;//指向下一條弧的指針
int info//該弧權值
}ArcNode;
//表頭結點表
typedef struct VertexNode{
ElemType data;
ArcNode *firstarc;
}VertexNode;
//圖
typedef struct AdjList{
VertexNode vertex[N];
int vexnum;//圖的頂點數
int arcnum;//弧數;
int kind;//圖的種類（kind=1為有向圖）
int dist[N];//圖的路徑長度
int path[N];//輔助數組
}AdjList;
//邊
typedef struct{
int i;
int j;
int f;
}Side;
//鄰接表法創建圖
int CreateDAG(AdjList *L){
int i,j;
ArcNode *p=NULL;
//測試用例
Side S[N];
S[0].i=1;S[0].j=3;S[0].f=10;
S[1].i=1;S[1].j=5;S[1].f=30;
S[2].i=1;S[2].j=6;S[2].f=100;
S[3].i=2;S[3].j=3;S[3].f=5;
S[4].i=3;S[4].j=4;S[4].f=50;
S[5].i=4;S[5].j=6;S[5].f=10;
S[6].i=5;S[6].j=6;S[6].f=60;
S[7].i=5;S[7].j=4;S[7].f=20;
for(i=1;i<7;i++){
L->vertex[i].data=i;
L->dist[i]=MAX;//設為最大值，表示不可達
L->path[i]=MIN;//設為最小值，表示尚未初始化
//L->vertex[i].indegree=0;
L->vertex[i].firstarc=NULL;
}
L->kind=1;
L->vexnum=6;
L->arcnum=8;
for(i=0;i<8;i++){
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=S[i].j;
p->info=S[i].f;
p->nextarc=L->vertex[(S[i].i)].firstarc;
L->vertex[(S[i].i)].firstarc=p;
if(S[i].i==1){//初始頂點為1
L->dist[(S[i].j)]=S[i].f;
//L->path[(S[i].j)]=S[i].f;
}
// L->vertex[(S[i].j)].indegree++;
}
return 1;
}
//輸出鄰接表存儲
void PrintALGraph(AdjList *L){
ArcNode *p=NULL;
int i,k=0;
for(i=1;i<=L->vexnum;i++){
k=L->vertex[i].data;
printf("V%d",k);
// printf(" 入度為%d 鄰接點有 ",(L->vertex[i].indegree));
p=L->vertex[k].firstarc;
while(p!=NULL){
printf(" ->%d",p->adjvex);
p=p->nextarc;
}
printf(" ");
}
}
//Dijkstra求單源最短路徑
void Dijkstra(AdjList *L){
int i=1,j,k=0;
Side s;
L->path[1]=0;
ArcNode *p=NULL;
while(k<10){
s.f=MAX;
for(i=1;i<=L->vexnum;i++){
if(L->path[i]!=MIN){
p=L->vertex[i].firstarc;
if(p!=NULL){
while(p!=NULL){
if(s.f>p->info&&L->path[(p->adjvex)]==MIN){
s.f=p->info;
s.i=i;
s.j=p->adjvex;
}
p=p->nextarc;
}
}
}
}
if(s.f==MAX){
}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){
L->dist[(s.j)]=L->dist[(s.i)]+s.f;
L->path[(s.j)]=L->dist[(s.j)];
}else{
L->path[(s.j)]=L->dist[(s.j)];
}
k++;
}
//輸出
printf("輸出最短路徑: ");
for(i=1;i<=L->vexnum;i++){
if(L->dist[i]==1000||i==1){
printf("v1到v%d不存在最短路徑 ",i);
}else{
printf("v1到v%d的最短路徑是%d ",i,L->dist[i]);
}
printf("path is %d ",L->path[i]);
}
}
int main(){
AdjList *L=(AdjList *)malloc(sizeof(AdjList));
if(CreateDAG(L)==1){
PrintALGraph(L);
Dijkstra(L);
}else{
printf("創建失敗 ");
}
}
(10)基於鄰接表存儲結構擴展閱讀：
要求帶權有向圖中某一頂點到其他各頂點的最短路徑，常用Dijkstra演算法，該演算法基本思想是，先將圖的頂點分為兩個集合，一個為已求出最短路徑的終點集合（開始為原點v1），另一個為還未求出最短路徑的頂點集合（開始為除v1外的全部結點），然後按最短路徑長度的遞增順序逐個將第二個集合的頂點加到第一組中。
演算法中使用dist數組，dist[i]表示目前已經找到、v1到vi的當前最短路徑，否則為MAX；path數組，作為是否找到該點最短路徑的標志，path[i]==MIN表示為未找到，否則為最短路徑值。