求PASCAL邻接表和邻接矩阵的具体用法
发布网友
发布时间：2022-04-22 00:52
共3个回答
热心网友
时间：2023-08-01 01:59
邻接矩阵a[i,j] 表示点i,j之间的路程，如果任意i,j都有a[i,j]=a[j,i]那么这个图就是一个无向图。
邻接表a[i],a[i]表示一个链表，里面依次存储每个和i相连的点k，i，k的距离，和next；如用.data .n .next 分别表示这个点的编号，这个点到i的距离和连接下一个地址。一般还要用一个head数组来表示每个点的首地址，我简要写一下： if head[i]=nil then begin new(a[i]);读入相关数据；head[i]=a[i];new(a[i]^.next);end else begin 读入数据；new(a[i]^.next);end；
要用的时候只要对首地址head[i]进行处理就行了。
一般来说，邻接矩阵的复杂度较低，邻接表的空间利用率比较高。所以一般的题目数据不大可以用邻接矩阵来编写，易调试编写也方便，只有在数据比较大邻接矩阵会爆内存的时候才不得不用邻接表。
热心网友
时间：2023-08-01 01:59
邻接表一般用于线多点少的图，链表一般用于点多线少的图。不过都相对复杂。如果数据不大，一般在5000个点以内就可以用邻接矩阵。
邻接矩阵就是二维数组map[i,j]表示i节点与j节点是否相连，如果直接相连那么map[i,j]就等于它们的距离，否则就等于一个很大的值，但是不能用maxlongint，因为这样很容易栈溢出。
邻接表用于边很多的情况，操作方法类似于链表。一般来说掌握邻接矩阵的链表储存的方法对于NOIP就足够了。
热心网友
时间：2023-08-01 02:00
递归算法:
program graph02;
const maxn=10;
type
datatype=integer;
nodep=^node;
node=record
vertex:1..maxn;
next:nodep;
end;
gnode=record
data:datatype;
head:nodep;
end;
graph=record
a:array[1..maxn]of gnode;
vexn:integer;
end;
var g:graph;
f:array[1..maxn]of boolean;
qu:array[1..maxn]of integer;
front,rear:integer;
fin,fout:text;
{*** 输入文件要求：第一行数据为图顶点个数，从第二行开始，第i行第一个数据为第i个结点的数据，
后面的为第i个结点的邻接顶点的编号 ***}
procere buildadjlist(var g:graph);
var i,t:integer; p,q:nodep; k:1..maxn;
begin
readln(fin,g.vexn);
for i:=1 to g.vexn do
begin
read(fin,g.a[i].data);
g.a[i].head:=nil;
t:=0;
while not eoln(fin) do
begin
read(fin,k);
t:=t+1;
new(p);
p^.vertex:=k;
p^.next:=nil;
if (t=1) then begin g.a[i].head:=p; q:=p; end
else begin q^.next:=p; q:=p; end;
end;
readln(fin);
end;
end;
procere bfs(g:graph; i:integer);
var p:nodep;
begin
p:=g.a[i].head;
while (p<>nil) do
begin
if (not f[p^.vertex]) then
begin
write(fout,'V',p^.vertex:1,' ');
f[p^.vertex]:=true;
inc(rear);
if (rear>maxn)then rear:=1;
qu[rear]:=p^.vertex;
end;
p:=p^.next;
end;
while (front<>rear) do
begin
inc(front);
if (front>maxn) then front:=1;
bfs(g,qu[front]);
end;
end;
procere trav_bfs(g:graph);
var i:integer;
begin
fillchar(f,sizeof(f),false);
for i:=1 to g.vexn do
if (not f[i]) then
begin
write(fout,'V',i:1,' ');
f[i]:=true; front:=1; rear:=1;
bfs(g,i);
end;
end;
begin
assign(fin,'a.in');
assign(fout,'a.out');
reset(fin);
rewrite(fout);
buildadjlist(g);
close(fin);
trav_bfs(g);
close(fout);
end.
非递归算法:
program graph02;
const maxn=20;
type
datatype=integer;
nodep=^node;
node=record
vertex:1..maxn;
next:nodep;
end;
gnode=record
data:datatype;
head:nodep;
end;
graph=record
a:array[1..maxn]of gnode;
vexn:integer;
end;
var g:graph;
f:array[1..maxn]of boolean;
qu:array[1..maxn]of integer;
front,rear:integer;
fin,fout:text;
{*** 输入文件要求：第一行数据为图顶点个数，从第二行开始，第i行第一个数据为第i个结点的数据，
后面的为第i个结点的邻接顶点的编号 ***}
procere buildadjlist(var g:graph);
var i,t:integer; p,q:nodep; k:1..maxn;
begin
readln(fin,g.vexn);
for i:=1 to g.vexn do
begin
read(fin,g.a[i].data);
g.a[i].head:=nil;
t:=0;
while not eoln(fin) do
begin
read(fin,k);
t:=t+1;
new(p);
p^.vertex:=k;
p^.next:=nil;
if (t=1) then begin g.a[i].head:=p; q:=p; end
else begin q^.next:=p; q:=p; end;
end;
readln(fin);
end;
end;
procere bfs(g:graph; i:integer);
var p:nodep; t:integer;
begin
write(fout,'V',i:1,' ');
f[i]:=true;
front:=0; rear:=1; qu[rear]:=i;
while (front<>rear) do
begin
inc(front);
if front>maxn then front:=1;
t:=qu[front];
p:=g.a[t].head;
while (p<>nil) do
begin
if not f[p^.vertex] then
begin
write(fout,'V',p^.vertex:1,' ');
f[p^.vertex]:=true;
inc(rear);
if (rear>maxn) then rear:=1;
qu[rear]:=p^.vertex;
end;
p:=p^.next;
end;
end;
end;
procere trav_bfs(g:graph);
var i:integer;
begin
fillchar(f,sizeof(f),false);
for i:=1 to g.vexn do
if (not f[i]) then bfs(g,i);
end;
begin
assign(fin,'a.in');
assign(fout,'a.out');
reset(fin);
rewrite(fout);
buildadjlist(g);
close(fin);
trav_bfs(g);
close(fout);
end.
请参考
