以邻接链表的方式确定一个无向网
...不新建链表怎么办啊？
每次修改了后继指针后，后继节点就找不到了，除非用一个数组把所有节点的地址记录下来。
树的各种存储结构：
双亲链表则注重的是每个结点最多只有一个双亲，根结点没有双亲，一般用下标就可以表示链接关系了，不一定需要指针
孩子链表则是注重的的每个结点的孩子，一般分为多重链表和单独的链表
多重链表则是按照孩子的个数或者树的度确定结点的指针个数，一个指针指向一个孩子结点，这个空间浪费很多
一般孩子链表类似于图的邻接表，一条边有一个结点，某结点发出的所有边做成一个链表，然后所有的链表的头结点组成数组
#include <stdio.h>
#include <string>
using namespace std;
#define max 10
class node_shuzu;
//邻接链表链结点
class node_lianbiao
{
public:
int position;
int quanzhi;
node_lianbiao * next;
node_lianbiao(int a,int b){position=a;quanzhi=b; next=NULL;}
node_lianbiao(){next=NULL;}
~node_lianbiao(){}
};
//邻接链表数组结点
class node_shuzu
{
public:
node_lianbiao *next;
string data;
node_shuzu(){next=NULL;}
~node_shuzu(){}
};
//图类
class tu_juzhen
{
private:
int juzhen[max][max];
string dingdian[max];
int numding,numhu;
node_shuzu lianbiao[max];
public:
tu_juzhen(){}
void creat();
int locateding( string );//返回这个顶点的第几位
int isempty();//判断是否为空
void guangdubianli();
void printgragh();
void prim();
void ktus();
};
int tu_juzhen::locateding(string b)
{
int i=0;
for(;i<numding;i++)
{
if(dingdian[i]==b) return i;
}
return -1;
}
void tu_juzhen::creat()
{
string data,data1,data2;
int n,m,num;
//输入顶点个数
cout<<"请输入顶点个数：";
cin>>numding;
//输入顶点
cout<<"请依次输入各个顶点：";
for(int i=0;i<numding;i++)
{
cin>>dingdian[i];
}
//以邻接链表确定有向网
node_lianbiao * * po[max];//指向数组链表的最后一位的next成员
for (int i=0;i<numding;i++)
{lianbiao[i].data=dingdian[i];po[i]=&lianbiao[i].next;}
cout<<"输入所有的弧，格式为:“顶点顶点权值”，以格式 0 0 0结束"<<endl;
do
{
cin>>data1>>data2>>num;
n=locateding(data1);
m=locateding(data2);
//node_lianbiao a(m,num);
if((n!=-1)&&(m!=-1))
{
*po[n]=new node_lianbiao(m,num);
po[n]=&((*po[n])->next);
*po[m]=new node_lianbiao(n,num);
po[m]=&((*po[m])->next);
}
}
while((data1!="0")&&(data2!="0")&&(num!=0));
//根据邻接链表建立邻接矩阵
node_lianbiao * po1;
for (int i=0;i<numding;i++)//初始化
for (int j=0;j<numding;j++)
juzhen[i][j]=0;
for(int i=0;i<numding;i++)
{
po1=lianbiao[i].next;
while(po1)
{
n=po1->position;
m=po1->quanzhi;
po1=po1->next;
juzhen[i][n]=m;
};
}
}
void tu_juzhen::printgragh()//打印有向网的邻接矩阵
{
cout<<endl;
cout<<"邻接矩阵为："<<endl;
int i,j;
for(i=0;i<numding;i++)
{
for(j=0;j<numding;j++)
{
cout<<juzhen[i][j]<<" ";
}
cout<<endl;
}
}
void tu_juzhen::guangdubianli()
{
int * flag =new int[numding];//记录顶点访问状态
int * duilie =new int[numding];//记录未广度遍历的顶点数
int front,rear;
front=0;rear=0;
int i;
cout<<endl;
cout<<"该图的广度优先遍历为："<<endl;
for( i=0;i<numding;i++)flag[i]=0;//状态初始化
do
{
for( i=0;i<numding;i++)if(flag[i]==0)break;
if(i!=numding)
{
cout<<"-->"<<dingdian[i]<<endl;
rear++;
duilie[rear]=i;
cout<<"入队列"<<dingdian[i]<<endl;
flag[i]=1;
do
{
cout<<"出队列"<<dingdian[duilie[front+1]]<<endl;
front=(front+1)%20;
for(int j=0;j<numding;j++)
{
if((juzhen[duilie[front]][j]!=0)* (flag[j]!=1))
{
rear++;
duilie[rear]=j;
cout<<"入队列"<<dingdian[j]<<endl;
flag[j]=1;
cout<<"-->"<<dingdian[j]<<endl;
}
}
}
while((((rear+1)%20)!=front) * (rear!=front));//队列结束条件。队列满或空
}
}
while(i!=numding);
cout<<endl;
}
void tu_juzhen::prim()
{
int flag[max],dian[max],n,m,l,p=0;//flag[]标志结点所属树,p表示已写出结点个数
int juzhen1[max][max];//矩阵的映像
for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
juzhen1[i][j]=juzhen[i][j];
for(int i=0;i<numding;i++)flag[i]=0;//初始化
cout<<"普里姆算法"<<endl;
//先找到最小的一个弧
l=n=m=10000;//假设一个很大值
for(int i=0;i<numding;i++)
for (int j=i;j<numding;j++)
{
if((juzhen1[i][j]!=0)&&(juzhen1[i][j]<l))
{
l=juzhen1[i][j];
m=i;n=j;
}
}
p+=2;dian[0]=m;dian[1]=n;flag[n]=flag[m]=1;
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;
while(p<numding)
{
l=n=m=10000;
for(int i=0;i<p;i++)
{
for (int j=0;j<numding;j++)
{
if((juzhen1[j][dian[i]]!=0)&&(juzhen1[j][dian[i]]<l)&&(flag[j]==0))
{
l=juzhen1[j][dian[i]];
n=dian[i];m=j;
}
}
}
if((m!=10000)&&(n!=10000)&&(l!=10000))
{
dian[p]=m;
p++;
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;
flag[m]=1;
}
}
cout<<endl;
}
void tu_juzhen::ktus()
{
int flag[max],n,m,l,p,k;//flag[]标志结点所属树,p表示已写出弧个数
int juzhen1[max][max];//矩阵的映像
for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
juzhen1[i][j]=juzhen[i][j];
cout<<"克鲁斯卡尔算法:"<<endl;
for(int i=0;i<numding;i++)flag[i]=0;//初始化
k=p=0;
while (p<(numding-1))
{
l=n=m=10000;//假设一个很大值
for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
{
if((juzhen1[i][j]!=0)&&(juzhen1[i][j]<l))
{
l=juzhen1[i][j];
m=i;n=j;
}
}
if((m!=10000)&&(n!=10000)&&(l!=10000))
{
if(flag[n]!=0)
if(flag[m]!=0)
if(flag[n]==flag[m]) //成环情况
{continue;}
else
{
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;
p++;
flag[numding]=flag[m];
for(int h=0;h<numding;h++)
if(flag[h]==flag[numding])
flag[h]=flag[n];
}
else
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[m]=flag[n];p++;}//后结点为新
else
if(flag[m]!=0)
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[n]=flag[m];p++;}//前结点为新
else
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[n]=flag[m]=k;p++;}//前后结点均为新
juzhen1[m][n]=juzhen1[n][m]=0;
}
k++;
};
cout<<endl;
}
void main()
{
tu_juzhen li;
li.creat();
li.printgragh();
li.guangdubianli();
li.ktus();
li.prim();
}
以邻接链表的方式确定一个无向网
以邻接链表的方式确定一个无向网请完成:⑴建立并显示出它的邻接矩阵;⑵对该图进行广度优先遍历,显示遍历的结果,(并随时显示队列的入、出情况);⑶用普里姆算法构造其最小生成树... 以邻接链表的方式确定一个无向网 请完成:⑴建立并显示出它的邻接矩阵;⑵对该图进行广度优先遍历,显示遍历的结果,(并随时显示队列...
数据结构之邻接表表示法
邻接表的表示方法 邻接表（Adjacency List） 是图的一种链式存储结构 在邻接表中 对图中每个顶点建立一个单链表 第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧） 邻接表由两部分构成 表头结头 表结点组成的单链表 邻接表的表示意义为 对于图G=(V E) 若(i j)∈E ...
图的基本概念,图的存储--邻接矩阵、邻接表、十字链表、邻接多重表
1)基本思想:类似于树的孩子链表法,就是对于图 G 中的每个顶点 ,将所有邻接于 的顶点 链成一个单链表,这个单链表就称为顶点 的邻接链表,再将所有点的邻接表表头放到数组中,就构成了图的邻接链表。对无向图,其邻接链表是唯一(按顺序链接)的;对有向图,其邻接链表有两种形式。 2)从图的邻接表存储方法容易看...
邻接表怎么画
邻接表是一种图的存储结构，通常用于表示稀疏图。画邻接表时，可以按照以下步骤进行：1.确定节点的个数和边的个数，以及节点和边的对应关系。2.按照边的顺序，画出每个节点及其相邻的节点。这里的节点可以是数字、字母或其它符号，具体表示根据需求而定。3.对于每个节点，只需画出与其相邻的节点，不需...
图- 图的存储结构 - 邻接表表示法(一)
有向图的逆邻接表 在有向图中 为图中每个顶点v i 建立一个入边表的方法称逆邻接表表示法 入边表中的每个表结点均对应一条以v i 为终点(即射入v i )的边 【例】G 的逆邻表如上面(b)图所示 其中v 的人边表上两个表结点 和 分别表示射人v 的两条边(简称为v 的入边) <v p=""> ...
图的邻接表的时间复杂度问题
n表示有n个顶点，e表示有e条边。1.若采用邻接矩阵存储，时间复杂度为O(n^2);2.若采用邻接链表存储，建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);...
数据结构问题 在邻接表中什么是表节点?什么是表头节点?什么是头节点...
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C...
...将如下图所示的无向图给出其存储结构的邻接链表表示,然后写出对其...
【1】接邻链表大概是这么表示 1→2→3→4→NULL 2→5→6→NULL 3→7→8→NULL 4→NULL 5→9→NULL 6→9→NULL 7→9→NULL 8→9→NULL 4→NULL 【2】深度优先遍历：1、2、5、9、6、3、7、8、4 【3】广度优先遍历：1、2、3、4、5、6、7、8、9 ...
邻接表与邻接矩阵的用法?
邻接表有多种实现方式，比如最简单的动态链表，对于一个无向图，为每个节点建一个动态链表，储存的只是这个节点每个相邻的点，而在邻接矩阵中，对于每个节点需要把它与其他所有点的关系都表示出来（相邻为1，不相邻为0），空间复杂度明显是邻接矩阵大，至于查询两者各有千秋，如果只是查询两个点之间是否...
如何用邻接表画无向图?
1、先把要讲解的图在下面展示一下，先看一下；2.然后在图中的邻接点的值的范围画出邻接表的表头。3.根据上一步画出的表头分析与其相连的点，这里链表之中后面有3个框；4.在链表中第一个框写相连点的顶点值，第二个框中写权值；5、根据上述的方式，依次把后面数字的链表写下来，无向带权图的...
枞明小儿： 您好,这是我们数据结构一个作业程序,希望能帮到你.#include <stdio.h>#include<stdlib.h>#define int_max 10000#define inf 9999#define max 20//邻接矩阵定义 typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct ...
松北区13936028438： 采用邻接表表示法,构造无向网G;并从任意一个顶点出发,递归地深度优先遍历该图G - ？
枞明小儿： #include<stdio.h> #include<stdlib.h> #define MaxVerNum 100 /*最大顶点数为100*/ #define TRUE 1 #define FALSE 0 int visited[MaxVerNum]; typedef struct node{ /*边表结点*/ int adjvex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指...
松北区13936028438： 求c语言图的深度优先遍历算法 - ？
枞明小儿： //两个算法使用的全局变量 --- bool visited[MAX_VERTEX_NUM]; // 访问标志数62616964757a686964616fe59b9ee7ad9431333264663039组 Status (* VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作...
松北区13936028438： C++ 用邻接表方式建立一个无向图,以及判断是否连通,求完整代码,有注释最好.？
枞明小儿： #include<iostream>#include<cstdio>#define maxn 1000 //最大顶点数#define maxm 10000//最大边数 using namespace std; struct EDGE{ int u,v,next; //next指向下一条边的编号 }edge[2*maxm+10]; int head[maxn+10],p;//head[i]为从点i出发的边的...
松北区13936028438： C++采用邻接表存储结构,实现无向图的创建和广度优先搜索程序. - ？
枞明小儿： #include＂stdio.h＂#include＂stdlib.h＂#define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode ...
松北区13936028438： 以邻接多重表为存储结构,实现连通无向图的深度优先遍历和广度优先遍历. - ？
枞明小儿： 原创一个C++的#include #include #include #include #define MAXN 30using namespa...
松北区13936028438： 数据结构课程设计:如何以邻接矩阵的方式确定一个图⑴建立并显示出它的邻接链表;⑵给出它的关键路径(要求:显示出VE,VL,E,L,L - E的结果).？
枞明小儿： #include <stdio.h> #define INFI 9999 #define MAXNUM 8 typedef struct{ int arcs[MAXNUM+1][MAXNUM+1]; char vexs[MAXNUM+1]; int vexnum,arcnum; }MGraph; int Locate(MGraph &G1,char &u) { int l; G1.vexs[0]=u; for(l=G1.vexnum;l>=0 && (G1....
松北区13936028438： 关于数据结构建立无向图邻接表的算法 - ？
枞明小儿： 在网上搜的,可以参考一下啊~void CreateGraph(ALGraph &G){ // 生成图G的存储结构-邻接表 cin >> G.vexnum >> G.arcnum >> G.kind;// 输入顶点数、边数和图类型 for (i=0; i<G.vexnum; ++i) { // 构造顶点数组cin>> G.vertices[i].data; ...
松北区13936028438： 用邻接矩阵存储无向图,并用深度优先和广度优先遍历搜索输出序列,要能运行的,并把运行的结果截图下来 - ？
枞明小儿： #include<iostream.h>#include<stdlib.h>#include<malloc.h>#define maxsize 50 struct arcnode //定义边结点 链表结点 { int adjvex; //弧头顶点的位置 struct arcnode *nextarc; //指向相同弧尾的下一条弧的指针 }; struct vnode //定义顶点结点 { int ...
松北区13936028438： 数据结构:图,邻接表中,无向图的每个顶点的单链表平均长度为2e/n,怎么算出来的? - ？
枞明小儿： 这是一个大致粗略的结果.首先要明确无向图邻接表是如何存储的,那就是以每一个顶点为头结点建立n个单链表,每个链表中的节点(称为边节点)是依附于这一顶点的边,这样每一条边被储存了2次!给你举一个最简单的例子:图 2——3,,我们把它们中间的边命名为a,则邻接表如下2——a3——a 所以粗略算共有2*e个边节点,n个链表,所以平均表长为2e/n 若算上头结点也可以为(2e+n)/n
