本文共 2344 字，大约阅读时间需要 7 分钟。
1.线性表中的数据元素叫元素；树中数据元素叫结点；图中数据元素叫顶点。（线性表和树可以为空，图不可以为空）
2.树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却是不唯一的。
路径长度是路径上的边或弧的数目。
第一个顶点到最后一个顶点系相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环。
3.无向图中，若顶点v到顶点v’有路径，则称v和v’是连通的。若对于图中任意两个顶点都是连通的，称图是连通图。无向图中的极大连通子图称为连通分量。（无向图由顶点和边构成）
连通分量：（子图、子图是连通的、子图含有极大顶点数、具有极大顶点数的连通子图包含依附于这些顶点的所有边）
4.有向图中，如果对于每一对顶点v、u（v！=u），从v到u和从u到v都存在路径，则称图是强连通图。有向图中的极大强连通子图称为有向图的强连通分量。（有向图由顶点和弧构成）
5.一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。（如果一个图有n个顶点和小于n-1条边，则是非连通图；如果多余n-1条边，必定构成一个环。不管有n-1条边并不一定是生成树）
6.如果一个有向图恰好有一个顶点入度为0，其余顶点的入度均为1，则是一颗有向树。
7.图的存储：邻接矩阵、邻接表、十字链表、邻接多重表、边集数组。
（邻接矩阵时间复杂度O(N+N^2+E)，邻接表时间复杂度O(N+E)）
(把数组与链表相结合的存储方法称为邻接表。)
邻接表的处理方法：
（1）图中顶点用一个一维数组存储，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
（2）图中每个顶点的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储。
（3）顶点表由data和firstedge两个域表示，data数据域存储顶点信息，firstedge指针域指向边表第一个结点。边表结点由adjvex和next域组成，adjvex是邻接点域存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
8.十字链表把邻接表与逆邻接表结合起来。既可以找到v为尾的弧，也可以找到v为头的弧，因而可以容易求得出度和入度。创建图算法的时间复杂度是和邻接表相同的。
9.（1）邻接矩阵DFS
typedef int Boolean;Boolean visited[MAX];//访问标志的数组 //邻接矩阵的深度优先递归算法 void DFS(MGraph G,int i) { int j; visited[i]=TRUE; printf("%c",G.vexs[i]);//打印顶点 for(j=0;j （2）邻接表DFS
//邻接表的深度优先递归算法 void DFS(GraphAdjList GL,int i) { EdgeNode *p; visited[i]=TRUE; printf("%c",GL->adjList[i].data);//打印顶点 p=GL->adjList[i].firstedge; while(p) { if(!visited[p->adjvex]) DFS(Gl,p->adjvex); P=P->next; } }//邻接表的深度遍历操作 void DFSTraverse(GraphAdjList GL) { int i; for(i=0;i numVertexes;i++) visited[i]=FALSE; for(i=0;i numVertexes;i++) if(!visited[i]) DFS(GL,i);} （3） //邻接矩阵的广度遍历操作 void BFSTraverse(MGraph G) { int i,j; Queue Q; for(i=0;i （4）
//邻接表的广度遍历操作 void BFSTraverse(GraphAdjList GL) { int i; EdgeNode *p; Queue Q; for(i=0;i numVertexes;i++) visited[i]=FALSE; InitQueue(&Q); //初始化一辅助用的队列 for(i=0;i numVertexes;i++) { //对每一个顶点做循环 if(!visited[i]) { //若是未访问就做处理 visited[i]=TRUE; //设置当前顶点访问过 printf("%c",GL->adjList[i].data); //打印顶点 EnQueue(&Q,i); //将此队列入队 while(!QueueEmpty(Q)) { //若当前队列不为空 DeQueue(&Q,&i); //将队列元素出队列，赋值给i p=GL->adjList[i].firstedge; while(p) { if(!visited[p->adjvex]) { visited[p->adjvex]=TRUE; //将找到的此点标记已访问 printf("%c",GL->adjList[p->adjvex].data);//打印 EnQueue(&Q,p->adjvex); //将找到的此顶点入队列 } p=p->next; } } } }} 转载地址：http://jicgz.baihongyu.com/