图 - suzhouzc/Data-Structure GitHub Wiki

无向完全图的边为：n(n-1)/2
极大连通子图：连通子图；极小连通子图：生成树
邻接矩阵和邻接表的对比

（主要）深度优先遍历

void DFSTraverse(Graph G)
{
 for (v=0 ; v < G.vexnum;++v) visited[v]=o;  //初始化辅助数组
 for (v=0 ; v< G.vexnum;++v)
  if(!visited[v]) 
   DFS(G,V);  //连通分量的个数=循环的次数
}
void DFS(Graph G,int v)
{
 visited[v]=1;
 Visit(v);  //访问顶点v
 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
 if (!visited[w]) DFS(G,w); //访问v的邻接点
}

(递归)若以邻接矩阵法表示图，则DFS算法如下：

void DFS(MGraph G,int v)
{ //从v出发深度优先遍历
 visited[v];
 Visit(v);
 for(w=0;w<G.vexnum:w++)
  if(G.arcs[v][w].adj&&!visited[w])
  DFS(G,w);
}

（递归）若以邻接表发表示图，则DFS算法如下：

void DFS(ALGraph G,int v)
{//从v出发的深度优先遍历
 visited[v]=1; Visit(v);
 for (p=G.vertices[V].firstarc; p ;p=p->nextarc)
  if (!visited[p->adjvex])
  DFS(G,p->adjvex);
}

广度优先遍历非递归遍历图G，类似于数的层次遍历

void BFSTraverse(Graph G)
{
 for (v=0;v<G.vexnum;++v) visited[v]=0;
 InitQueue(Q);
 for(v=0;v<G.vexnum:++v)
  if(！visited[v])
   {
     visited[v]=1;
     Visit(v);
     EnQueue(Q,v);
  while(!QueueEmpty=0)
  {
    DeQueue(Q,u);
    for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
     if(!visited[w])
      {visited[w]=1;Visit(w);EnQueue(Q,w); }
  }    
 }
}//BFSTraverse

最短路径问题

求顶点u到其他顶点的最短路径（广度优先算法BFS）

void BFS_MIN_Distance(Graph G,int u){
 for(i=0;i<G.vexnum;++i){
  int d[i]=⚮；   //初始化路径长度
  int path[i]=-1;  //最短路径从哪个顶点过来
 }
 d[u]=0;
 visited[u]=TRUE;
 EnQueue(Q,u);
 while(!isEmpty(Q)){
 DeQueue(Q,u);
 for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
  if(!visited[w]){  //w为u尚未访问的邻接顶点
  d[w]=d[u]+1;   //路径长度加一
  path[w]=u; //最短路径应从u到w
  visited[w]=TRUE; //设已访问标记
  EnQueue(Q,w);   //顶点w入队
  }
 }
}

迪杰斯特拉算法（最短路径）

Dijkstra算法不适合用于有负权值的带权图（跑毒、中途加电）

弗洛伊德算法（Floyd算法最短路径–动态规划思想）可解决负权值的问题

//--初始化矩阵A和path
for (int k=0;k<n;k++){ //考虑以vk作为中转点
 for (int i=0;i<n;i++){  --遍历整个矩阵，i为行号，j为列号
  for(int j=0;j<n;j++){
    if(A[i][j]>A[i][k]+A[k][j])  //以vk为中转点的路径更短
       A[i][j]=A[i][k]+A[k][j];  //更新最短路径长度
        path[i][j]=k;            //中转点  
   }
 }
}

AOV网（用顶点表示事件）是一个有向无环图
AOE网（用顶点表示事件，用有向边表示活动）
拓扑排序

结构体

#define MaxVertexNum 100
typedef struct ArcNode{ //边表结点
 int adjvex;           //该弧所指向的顶点的位置
 struct ArcNode *nextarc;  //指向下一条弧的指针
  //InfoType info;          //网的边权值
 }ArcNode;
typedef struct VNode{  //顶点表结点
 VertexType data;      //顶点的信息
 ArcNode*firstarc;     //指向第一条依附该顶点的弧的指针
 }VNode,AdjList[MaxVertexNum];
 typedef struct{
  AdjList vertices;    //邻接表
  int vexnum,arcnum;   //图的顶点数和弧数
 }Graph;               //Graph是以邻接表存储的图类型

新定义：

bool TopologicalSort(Graph G){
 InitStack(S);         //初始化栈，存储入度为0的顶点
 for(int i=0;i<G.vexnum;i++)
  if(indegree[i]==0)
   Push(S,i);        //将所有的入度为0的顶点进栈
  int count=0;       //计数，记录当前已经输出的顶点数
  while(!IsEmpty(S)){
   Pop(S,i);         //栈顶元素出栈
   print[count++]=i;  //输出顶点i
   for(p=G.vertices[i].firstarc;p;p=p->nextarc){
    //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
      v=p->adjvex;
      if(!(--indegree[v]))
        Push(S,v);  //入度为0，则入栈
    }
  } //while
   if(count<G.vexnum)
    return false;  //排序失败，有向图中有回路
   else
    return true;  //拓扑排序成功

 }

逆拓扑排序(深度优先遍历)

void DFSTraverse(Graph G){  //对图G进行深度优先遍历
 for( v=0;v<G.vexnum;++v)  
  visited[v]=FALSE;     //初始化已访问标记数据
 for(v=o;v<G.vexnum'++v)  //本代码中是从V=0开始遍历
   if(!visited[v])
      DFS[G,v];
}

void DFS(Graph G,int V){  //从顶点v出发，深度优先遍历图G
// visited(v);   //访问顶点V
 visited[v]=TRUE;  //设已访问标记
 for(w=FirstNeighbor(G,v);W>=0;W=NextNeighbor(G,v,w))
   if(!visited[w]){        //w为u的尚未访问的邻接顶点
     DFS(G,w);
  }
  print(v);           //输出顶点  （通过调用栈来进行的输出）
}

邻接表时间复杂度：O(V+E) 邻接矩阵：O（v^2）

求关键路径的步骤

图 - suzhouzc/Data-Structure GitHub Wiki

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️