Ⅰ 如何用邻接表存储图结构
我看不太懂这个程序，不过我有些过图的邻接表表示，看对你有没有帮助吧。
#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表示为未找到，否则为最短路径值。