求解邻接表建图的算法

C语言关于图的邻接表建立~

#include "iostream.h"

const int Max_vertex=5;
const int Max_Edge=8;
int visited[Max_vertex+1]; //访问标志数组

struct ArcNode
{
int adjvex;
ArcNode *nextarc; //指向下一条弧
};

struct Vnode
{
int v; //顶点信息
ArcNode *next;
}a[Max_vertex+1];

/* 无向图的建立 */
void creategraph()
{
int i,j,k;
ArcNode *s;
//初始化
for(i=1;i<=Max_vertex;i++)
{
a[i].v=i;
a[i].next=NULL;
}

/*以头插法建立 */

for(k=1;k<=Max_Edge;k++)
{
cout<<"请输入第"<<k<<"条边:";
cin>>i>>j;
if(i>9||i9)
{
cout<<"输入错误!!
"<<endl;
break;
}
else{
cout<<endl;
s=new ArcNode;
s->adjvex=j;
s->nextarc=a[i].next;
a[i].next=s;
s=new ArcNode;
s->adjvex=i;
s->nextarc=a[j].next;
a[j].next=s;
}
}
}


void display()
{
ArcNode *p;
cout<<"你建立的图为:"<<endl;
for(int i=1;i<=Max_vertex;i++)
{
p=a[i].next;
cout";
while(p->nextarc!=NULL)
{
coutadjvex";
p=p->nextarc;
}
coutadjvex<<endl;
}
}

void main()
{
cout<<"/******本算法以关插法建立无向图的邻接表为例!******/"<<endl;
char yn='y';int k;
creategraph();
display();

}

不懂

邻接表的形式说明及其建表算法
（1）邻接表的形式说明
typedef struct node{//边表结点
　　　　 int adjvex； //邻接点域
　　　　 struct node *next； //链域
　　　　　//若要表示边上的权，则应增加一个数据域
　　　}EdgeNode;
typedef struct vnode{ //顶点表结点
　　　　 VertexType vertex； //顶点域
　　　　 EdgeNode *firstedge；//边表头指针
　　　 }VertexNode；
typedef VertexNode AdjList[MaxVertexNum]；//AdjList是邻接表类型
typedef struct{
　　　 AdjList adjlist；//邻接表
　　　 int n，e； 图中当前顶点数和边数
　　　}ALGraph； //对于简单的应用，无须定义此类型，可直接使用AdjList类型。

(2)建立无向图的邻接表算法
void CreateALGraPh(ALGrahp *G)
{//建立无向图的邻接表表示
int i，j，k；
EdgeNode *s；
scanf( "％d％d "，&G-> n，&G-> e)； //读人顶点数和边数
for(i=0；i <G-> n；i++){//建立顶点表
G-> adjlist[i].vertex=getchar()； //读入顶点信息
G-> adjlist[i].firstedge=NULL；//边表置为空表
}
for(k=0；k <G-> e；k++){//建立边表
scanf( "％d％d "，&i,&j)；读入边(vi，vj)的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode))； //生成边表结点
s-> adjvex=j; //邻接点序号为j
s-> next=G-> adjlist[i].firstedge；
G-> adjlist[i].firstedge=s； //将新结点*s插入顶点vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode))；
s-> adjvex=i; //邻接点序号为i
s-> next=G-> adjlist[j].firstedge；
G-> adjlistk[j].firstedge=s； //将新结点*s插入顶点vj的边表头部
}//end for
}CreateALGraph

　该算法的时间复杂度是O(n+e)。
注意：
　 ① 建立有向图的邻接表更简单，每当读人一个顶点对序号 <i,j> 时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。
　② 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。

邻接矩阵
邻接链表

存储表示

惟一
不惟一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序

空间复杂度S(n，e)
O(n2)稠密图，考虑邻接表中要附加链域，应取邻接矩阵表示法为宜
S(n，e)=O(n+e)。稀疏图用邻接表表示比用邻接矩阵表示节省存储空间

求顶点的度
无向图：第i行(或第i列)上非零元素的个数即为顶点Vi的度有向图：第i行上非零元素的个数是顶点Vi的出度OD(Vi)，第i列上非零元素的个数是顶点Vi的人度ID(Vi)，顶点Vi的度即是二者之和。
无向图：顶点vi的度则是第i个边表中的结点个数有向图：邻接表表示中，第I个边表 (即出边表)上的结点个数是顶点Vi的出度，求Vi的人度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求Vi的人度容易，而求顶点的出度较难。在有向图中求顶点的度。采用邻接矩阵 表示比邻接表表示更方便

判定(Vi，Vj)或 <Vi，vj> 是否是图的一条边
判定矩阵中的第i行第j列上的那个元素是否为零
在邻接表表示中，需扫描第i个边表最坏情况下要耗费O(n)时间

求边的数目
必须检测整个矩阵，所耗费的时间是O(n2)
与e的大小无关 只要对每个边表的结点个数计数即可求得e，所耗费的时间，是O(e+n)。当e≤n2时，采用邻接表表示更节省空间。

首先把图的节点编号，从 0 到 n，设 N 是 最大可能的图顶点数，则：
int map[][] = new int[N+1][N+1]; // 存储图的邻接表数据。

int len[] = new int[N+1]; // ln[i] 表示 跟节点 i 有连接的 节点的数量。
for (int i = 0; i < N+1; ++ i) {
len[i] = 0;

}
定义一个函数，用来判断两个节点之间是否有连接：有连接返回 true，否则返回 false；

boolean checkLink(int i, int j) {
// 如果 图中 i 到j 有连接，则 返回 true，否则返回 false
// 具体的代码实现根据 实际问题和需求而定

}

构造图的邻接表 表示：
// 如果是单向图（节点之间可能只有单向连接）

for (int i = 0; i <= n; ++ i) {
for (int j = 0; j <= n; ++ j) {
if (checkLink(i, j)) {
map[i][len[i]] = j;
++ len[i];

}

}

}
// 如果是双向图(节点之间如果有连接就一定是双向连接)
for (int i = 0; i <= n; ++ i) {
for (int j = i+1; j <=n; ++ j) {
if (checkLink(i, j)) {
map[i][len[i]] = j;
++ len[i];
map[j][len[j]] = i;
++ len[j];

}
}
}
**构造　图的表示时　对 节点 i 到 i 的连接情况可以特殊处理。
有时候情况特殊，需要把 i 到 i 设置为 无连接的情况。这时候可以 让checkLink 在
i == j 是返回 false 或这 在循环时候 添加判断if (i != j && checkLink(i, j)) { ... }
如果需要 把 需要把 i 到 i 设置为 有连接的情况 就可以做另外的处理了，看情况而定。

这个都好说，不过你要用邻借表保存图，还是已知邻接表打印图？这两个是不同的算法。

找本数据结构的书，里面有的。记得北邮的那本直接有代码

---

府谷县17580752998： 基于邻接表建图的几种方法 - ？
双巩气片： 数据结构书上表示邻接表比较复杂,一般形式如下: typedef struct Node{int dest; //邻接边的弧头结点序号 int weight; //权值信息 struct Node *next; //指向下一条邻接边}Edge; //单链表结点的结构体typedef struct{ DataType data; //结点的一...

府谷县17580752998： 图的邻接表的构建算法、图的深度优先遍历搜索递归算法、图的广度优先遍历搜索非递归算法. - ？
双巩气片： //第一次深度优先遍历建立finished数组 if(!visited[v]) DFS1(G,v); 分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块

府谷县17580752998： 请设计算法,由依次输入的顶点数目、弧数目、各顶点的信息和各条弧的信息建立有向图的邻接表 - ？
双巩气片： 解:Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { scanf(&G.vexnum,&G.arcnum); //输入顶点数、边数 for(i=0;iadjvex=j; s-> info=w; //插入(逆差)链表G.vertices[i] s->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=s; } return OK; }//Build_AdjList

府谷县17580752998： 采用邻接表存储结构,编写一个求无向图的连通分量个数的算法. - ？
双巩气片： 思路是这样的:1、从图中任选一个节点,以此节点进行深度优先搜索并将访问的节点做好标记,连通分量数加一.2、在从图中没有访问的节点集中选一个节点重复1的过程直到所有节点都被标记

府谷县17580752998： 关于数据结构建立无向图邻接表的算法 - ？
双巩气片： 在网上搜的,可以参考一下啊~void CreateGraph(ALGraph &G){ // 生成图G的存储结构-邻接表 cin >> G.vexnum >> G.arcnum >> G.kind;// 输入顶点数、边数和图类型 for (i=0; i<G.vexnum; ++i) { // 构造顶点数组cin>> G.vertices[i].data; ...

府谷县17580752998： 在C语言中编程实现建立无向图的邻接表,输出某个点的邻接点~! - ？
双巩气片： 用矩阵表示无向图的,设有M个节点,则建立一个MXM矩阵,对每个顶点添加它的邻接点,即每行中对于有标记的列为该行顶点的邻接点.

府谷县17580752998： 假设图G采用邻接表存储,试设计一个算法,求不带权无向连通图G中距离顶点V的最远的一个顶点. - ？
双巩气片：[答案] (1)每个点关联一个量d,让所有定点的d值都为0 (2)对v进行广度优先搜索 (3)bfs后d值最大的点就是离v最远的点.

府谷县17580752998： 编写算法,求有向图中各定点的入度 - ？
双巩气片： 先是根据邻接表的顶点个数n,创建一个int型的数组a[n](用来存储各顶点的入度),把a[n]中的每一项置为0.然后再邻接表遍历一下就行了,先是顶点遍历,然后弧遍历. 我大致写一下算法. #define n 30; struct diagraph { struct vertex * head; ...

府谷县17580752998： c语言图的邻接表建立,建立应该怎么写,说一下具体的思路就行,不要给代码 - ？
双巩气片： 1. 在读入顶点信息的时候,将每个点的第一条置为空.如node[x].first_edge = NULL2. 读入每条边的时候,边的信息应该包括这条边所连接的两个点,即为ilink和jlink.然后执行 edge = malloc...edge->next_edge = node[ilink].first_edge; node[ilink].first_edge = edge; 即,将ilink的第一条边指向刚刚输入的这条边,而该边的下一条边置为原本ilink的第一条边.重复这一过程,直至读完所有边的信息.

府谷县17580752998： 求算法,用邻接矩阵和邻接表创建一个图,实现深度和广度搜索,菜单形式,c语言的代码.无向无权的图. - ？
双巩气片： #include#include#define NULL 0#define maxvernum 100 typedef struct node { int adjvex; struct node *next; }nodetype; typedef struct frontnode { int data; struct node *next; }frontnodetype; frontnodetype adjlist[maxvernum];/*******************************...