实验3 图的基本操作ppt课件

1、0 01 13 32 2(a) (a) 无向图无向图G1G1(d) (d) 图图G1G1的邻接矩的邻接矩阵阵 0 1 2 3 0 1 2 30 0 1 0 10 0 1 0 11 1 0 1 11 1 0 1 12 0 1 0 12 0 1 0 13 1 1 1 03 1 1 1 00 01 13 32 20 01 12 23 3 1 1 3 3 0 0 0 0 2 2 建立邻接表建立邻接表 函数函数CreateGraphCreateGraph构造一个有构造一个有n n个顶点，但不包含边的有向图。由于图个顶点，但不包含边的有向图。由于图的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数

2、组。的顶点数事先并不知道，所以我们使用动态存储分配的一维指针数组。void CreateGraph(Graphvoid CreateGraph(Graph* * g, int n) g, int n) int i; int i; g-Vertices=n; g-Vertices=n; g-A=(ENode g-A=(ENode* * *)malloc(n)malloc(n* *sizeof(ENodesizeof(ENode* *); ); for(i=0; iAi=NULL; for(i=0; iAi=NULL; 0 01 1.n-1n-1. 边的搜索边的搜索0 01 12 23 32 2

3、1 1 0 0 3 3 1 1 3 3 1 1 3 3 2 2 0 0 1,21,2是否有边？是否有边？/搜索边的函数搜索边的函数BOOL Exist(Graph g, int u, int v) int n; ENode* p; n=g.Vertices; if(un-1) return FALSE; for(p=g.Au; p&p-AdjVex!=v; p=p-NextArc; if (!p) return FALSE; return TRUE; 插入边的函数插入边的函数BOOL Add(Graph *g, int u, int v, T w) int n; ENode *p; n

4、=g-Vertices; if (u0 | vn-1 | vn-1 | u=v | Exist(*g, u, v) printf(BadInputn); return FALSE; p=NewENode(v, w, g-Au); g-Au=p; return TRUE; 0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 p p3 30 01 13 32 2插入邻接表中由指针插入邻接表中由指针AuAu所指示的单链表的最前面所指示的单链表的最前面ENodeENode* * NewENode( int vex, T weight, ENode NewENode( int vex, T

5、 weight, ENode* * nextarc) nextarc) ENodeENode* * p; p; p=(ENodep=(ENode* *)malloc(sizeof(ENode); )malloc(sizeof(ENode); p-AdjVex=vex; p-AdjVex=vex; p-W=weight; p-W=weight; p-NextArc=nextarc; p-NextArc=nextarc; return p; return p; /删除边的函数删除边的函数BOOL Delete(Graph *g, int u, int v) int n=g-Vertices; EN

6、ode* p, *q; if(u-1 & uAu; q=NULL; while (p& p-AdjVex!=v) q=p; p=p-NextArc; if (p) if (q) q-NextArc=p-NextArc; else g-Au=p-NextArc; free(p); return TRUE; printf(BadInputn); return FALSE; 0 01 12 23 3 1 1 3 3 0 0 0 0 2 2 0 01 13 32 23 3P Pq=NULLq=NULL在由指针在由指针AuAu所指示的单所指示的单链表中，搜索链表中，搜索AdjVexAdj

7、Vex域的域的值为值为v v的边结点的边结点DFSDFS递归算法（递归算法（ 【程序【程序10105 5】 ）。）。void DFS(Graph g, int v, BOOL void DFS(Graph g, int v, BOOL * *visited)visited) ENode ENode * *w; w; visitedv=TRUE; printf(%d , v); visitedv=TRUE; printf(%d , v); for ( w=g.Av; w; w=w-NextArc) for ( w=g.Av; w; w=w-NextArc) if (!visitedw-AdjVe

8、x ) if (!visitedw-AdjVex ) DFS(g, w-AdjVex, visited); DFS(g, w-AdjVex, visited); void Traversal_DFS(Graph g)void Traversal_DFS(Graph g) BOOL visitedMaxSize; int i, n=g.Vertices; BOOL visitedMaxSize; int i, n=g.Vertices; for(i=0; in; i+) visitedi=FALSE; for(i=0; in; i+) visitedi=FALSE; for (i=0; in; i+) for (i=0; iNextArc) for (w=g.Au; w; w=w-NextArc) if (!visitedw-AdjVex) if (!visitedw-AdjVex) printf(%d , w-AdjVex); printf(%d , w-AdjVex); visitedw-AdjVex=