文档介绍：NOIpNOIp图论算法与模型构建图论算法与模型构建长沙市一中长沙市一中曹利国曹利国图结构?图结构包括:?点?边?图涉及到的概念?边的权?点的度图的储存结构?矩阵?邻接表?邻接多重表?十字链表无向图邻接表********** |5 |4 |3 | /2 |2 |2 |3 |1 |2 |4 | /5 | /4 | /5 | /邻接链表?每一个顶点?有一个所有与之相邻的链表?每一条边?2 个(对无向图)?要在两个顶点的链表中都加入?空间复杂度O(|E|)?对稀疏图这种方式比较好邻接表Pascal语言const maxv=10000;type Tnode=record //定义顶点类型c:integer; //顶点编号next:^Tnode; //此点的邻接链表end;Var//数组g表示每个顶点的邻接链表//的链表头---哨兵 g:array[1..maxv] of Tnode;n,m,i,a,b:integer;t:^Tnode;C++语言#include <iostream>using namespace std;const intmaxv=10000;structTnode{ //定义顶点类型int c; //顶点编号Tnode*next; //此点的邻接链表};//数组g表示每个顶点的邻接链表//的链表头---哨兵Tnodeg[maxv] ;intn,m,i,a,b;Tnode*t;图G有n个顶点,编号从1到n。有m条有向边,输入时每行两个整数a b,表示边为从顶点a连接到顶点b。下面程序用指针实现图的邻接链表。Pascal语言procedure ins(x:integer; varp:Tnode);Begin //插入链表子过程new(t); t^.c:=x;t^.next:=;:=t;end;beginreadln(n,m);//初始化邻接链表“哨兵”for i:=1 to n do g[i].next :=nil;//读入边,插入邻接链表for i:=1 to m do beginreadln(a,b);ins(b,g[a]); { ins(a,g[b]);//无向边时再加入} end; //...C++语言void ins(int x, Tnode &p){ //插入链表子过程 t=new(Tnode); t->c=x; t->next=;=t;}int main() {cin >> n >> m;//初始化邻接链表“哨兵”for(i=1; i<=n; i++)g[i].next=NULL;for(i=0; i<m; i++) { //读入边,插入邻接链表cin>>a>>b;ins(b,g[a]);// ins(a,g[b]);//无向边时}//…邻接表的实现A(指针)Pascal语言const maxV=1000; //最多顶点数maxE=10000; //最多边数type Tnode=record //定义顶点类型c:integer; //节点编号next:integer; //此节点的邻接链表end;var e:array[1..maxE] of Tnode; g:array[1..maxV] of Tnode;n,m,efree,i,a,b,t:integer;procedure ins(x:integer; varp:Tnode);begin //取一个空元素插入链表p后e[efree].c:=x; e[efree].next:=;:=efree;efree:=efree+1; //新空元素下标end;C++语言const intmaxV=1000, //最多顶点数maxE=10000; //最多边数structTnode{ //定义顶点类型int c; //顶点编号int next; //此点的邻接链表};//数组g表示每个顶点的邻接链表//的链表头---哨兵Tnodeg[maxV], e[maxE] ;int n, m, i, a, b, efree, t;void ins(int x, Tnode &p){//取一个空元素插入链表p后e[efree].c=x;e[efree].next=;=efree;efree++; //新空元素下标}邻接表的实现B(数组)Pascal语言beginreadln(n,m);//初始化邻接链表“哨兵”