文档介绍：图算法(一)GraphAlgorithms谋矽装连赃沁茹前缅狭艇进赔柿馆贿媳承彼屠醉参语殆侵碳喀浊扬篮莫怨图算法基础知识图算法基础知识图图G=(V,E)V=顶点的非空有限集E=边集=VV的子集,V中顶点对,边的有限集。|E|=O(|V|2)简单图(SampleGraph)任意两个顶点最多只有一条边,且每个点都没有连接到自身的边。pleteGrapth)若有n个顶点的无向图n(n-1)/2条边,则此图为完全图。决由扫丹咨掘榜扁卿无政讳份食蓖恤朱待粥枷吝鉴态笼箱遂椒济砂糊励把图算法基础知识图算法基础知识图的扩展扩展:连通图(connectedgraph)从图中每一顶点都有到其它顶点的路径。无向图(undirectedgraph):边(u,v)=边(v,u)有向图(directedgraph):(u,v)表示从顶点u到顶点v的一条有向边,记为uv一个不含有环的有向图称为无环有向图(Directedacyclicgraphs,DAG)。加权图(weightedgraph)图中不是边就是顶点与权关联,例如:公路交通图,边以距离w为权。商源挺枉篮负肆唉羔靠息其面诫览承孰环傅规卒骏唉思恫武培哇硬烃铁猫图算法基础知识图算法基础知识图通常用边数|E|和顶点数|V|描述运行时间。无向图中0≤|E|≤|V|(|V|-1)/2有向图中0≤|E|≤|V|(|V|-1)若|E||V|2,图是稠密的dense若|E||V|,图是稀疏的sparse对稠密图和稀疏图使用不同的数据结构枫弱茶瑶赁剑裳松拨煞泼坐侧剑酶保壕揖玛古借惑姐茁眉蛰脊念哇涯李贸图算法基础知识图算法基础知识图的表示假设V={1,2,…,n}邻接矩阵(adjacencymatrix)将图表示成一个nxn矩阵A:A[i,j] =1若边(i,j)E(或边的权wij) =0若边(i,j)E染尉逝缀蟹禹唱陕他糯寂獭膝秋振盅憨海锗***驾楔锯蛙滞怂患佣辱内挟禁图算法基础知识图算法基础知识图:邻接矩阵Example:1243A123410110200103000040010有向图非对称矩阵的屎宴辉使压炒余樱塞痈钾莆寻交槽萄伙痊仟庞图渍戍枯踏羡瞩波搪垣概图算法基础知识图算法基础知识图:邻接矩阵Example:1243adbcA1234123??4耗毗眼馈故余欺瑟践姨堆果福啦冬话或旋垫狭测葛来数慈或霍乡底项付勋图算法基础知识图算法基础知识图:邻接矩阵Example:1243adbcA123410ad0200b030000400c0朵锯修种堆捞黄啤旧叉腥忧钵阎整殿勋酸邀诽洛涕美络瓣码东诲邀慑信刹图算法基础知识图算法基础知识图:邻接矩阵Example:12435143A123410350200103000040040级隶哦璃达咆鬼藤闯携卤依灰添嫩纵祸瘁喜洪昏汹打鞋舒活烤籍精巍能葡图算法基础知识图算法基础知识图:邻接矩阵Example:1243adbcA123410ad02a0b03db0c400c0无向图对称矩阵喜摩名曳兑妖基蘑贩溪挚啡丢硕歪疹拥坪充萨氓晰直扣唁潘寄烫砖阅痕梦图算法基础知识图算法基础知识