• 顶点Vertex（也称节点Node）
• 边Edge（也称弧Arc） 两个顶点之间关系的表示，链接两个顶点，可以无向或有向，相应的图称作’无向图‘和’有向图‘
• 权重Weight 表示从一个顶点到另一个顶点的‘代价’，给边赋权。
• 路径Path 图中的路径是由边依次连接起来的顶点序列，无权路径的长度为边的数量，带权路径的长度为所有边权重的和
• 圈Cycle 首尾顶点相同的路径 (v1,v2,v3,v1)是一个圈 如果有向图中不存在任何圈，则称作‘有向无圈图DAG（directed acyclic graph）‘

对有向图

• 连通 如果从一个节点到另一个节点存在一条（无向）路径，则称这两个节点是连通的
• 连通图 图中任意两个顶点均连通
• 连通分量 无向图的极大连通子图 顶点数达到最大：再加一个顶点就不连通了 边数达到最大：包含子图中所有顶点相连的所有边

对无向图

• 强连通 有向图中两个顶点之间存在双向路径，则称这两个顶点强连通
• 强连通图 有向图中任意两顶点均强连通
• 强连通分量 有向图的极大强连通子图
• 弱连通图 本身不是强连通图，但如果把有向边改为无向时该图是连通图，则称为弱连通图

图的定义

一个图G可以定义为G=(V,E)，其中V是顶点的集合，E是边的集合，E中的每条边e=(v,w)，v和w都是v中的顶点（如果是赋权图，可以在e中添加权重分量子图）

存储类型

邻接矩阵Adjacency Matrix

两个顶点有边相连标注为1，无边相连标注为0，带权边标记为权重值

特点

实现简单，容易得到顶点如何相连的 方便检查任意一对顶点间是否存在边 空间复杂度$O(n^2)$ 如果图中变数很少则效率低下（适合稀疏图，不适用稠密图）

无向图的邻接矩阵 对称，是一个对称矩阵。可以只存储一半的数据来降低其存储空间 顶点i的度=第i行（列）中1的个数 完全图的邻接矩阵对角元素为0，其余为1

有向图的邻接矩阵 第i个元素的出度是矩阵第i行非零元素的个数，入度是第i列非零元素的个数

邻接表Adjacenc List

容易获得顶点所连接的所有顶点和边的信息

适用于稀疏图的更高效实现方案

维护一个包含所有顶点的主列表，主列表中的每个顶点再关联一个与自身有边连接的所有顶点的列表

对于无向图来说方便计算任一顶点的度 对有向图，只能计算出度，需要构造‘逆邻接表（存指向自己的边）’来方便计算入度

带权图的邻接表实现

十字链表

邻接表加逆邻接表 顶点节点包含：数据域、邻接表引用域、逆邻接表引用域 弧节点包含：弧尾节点、弧头节点、上一个引用、下一个引用（加权图还多一个权值域）

实现

关于矩阵推导式的测试用例

#mat推导式测试用例  
mat=[  
    [1,5,8,2,9],  
    [2,7,3,9,4],  
    [0,7,2,9,5],  
    [9,3,8,6,1],  
    [3,0,5,1,9]  
]  
print(len(mat))  
print('-------------------------------')  
print([mat[i][:]for i in range(len(mat))])  
print('-------------------------------')  
print([mat[i]for i in range(len(mat))])  
print('-------------------------------')  
for i in range(len(mat)):  
    print(mat[i][:])  
print('-------------------------------')  
for i in range(len(mat)):  
    print(mat[i])  
print('-------------------------------')

邻接矩阵的实现

#邻接矩阵实现图  
class GraphAX:  
    def __init__(self,vertexs,mat):  
        """  
        vertex:列表，存放顶点集  
        mat:列表中嵌套列表的矩阵，存放边的信息  
        vnum:顶点的个数  
        """        self.vnum=len(vertexs)  
        self.vertexs=vertexs  
        self.mat=[mat[i][:]for i in range(self.vnum)]#推导式，把mat复制到self.mat中  
  
    def findedge(self,v1,v2):  
        """给出两个顶点查找两者是否有边"""  
        if v1 not in self.vertexs or v2 not in self.vertexs:  
            return False  
        else:  
            return self.mat[self.vertexs.index(v1)][self.vertexs.index(v2)]  
  
def DFSmat(graph):  
    """基于邻接矩阵的深搜遍历"""  
    visited=[0]*len(graph.vertexs)  
    stack=[]  
    stack.append(0)  
    visited[0]=1  
    i=0  
    print(graph.vertexs[0],end=' ')  
    while len(stack)!=0:  
        for j in range(len(graph.vertexs)):  
            if graph.mat[i][j]==1 and visited[j]==0:  
                print(graph.vertexs[j],end=' ')  
                visited[j]=1  
                stack.append(j)  
                i=j  
        if len(stack)!=0:  
            i=stack.pop()  
  
def BFSmat(graph):  
    visited=[0]*len(graph.vertexs)  
    queue=[]  
    print(graph.vertexs[0],end=' ')  
    visited[0]=1  
    queue.append(0)  
    while len(queue)!=0:  
        i=queue.pop(0)  
        for j in range(len(graph.vertexs)):  
            if graph.mat[i][j]==1 and visited[j]==0:  
                print(graph.vertexs[j],end=' ')  
                visited[j]=1  
                queue.append(j)  
  
nodes=['v0','v1','v2','v3','v4']  
mateix=[  
    [0,1,0,1,0],  
    [1,0,1,0,1],  
    [0,1,0,1,0],  
    [1,0,1,0,0],  
    [0,1,1,0,0]  
]  
graph=GraphAX(nodes,mateix)  
print(graph.vertexs)  
print(graph.mat)  
DFSmat(graph)  
print()  
BFSmat(graph)

邻接表的实现

#邻接表实现图  
class Anode:  
    """边表结点"""  
    def __init__(self,edgedata,weight=0):  
        self.edgedata=edgedata  
        self.weight=weight  
        self.next=None  
  
class Vnode:  
    """顶点表结点"""  
    def __init__(self,vertdata):  
        self.vertdata=vertdata  
        self.firsta=None  
  
class Graph:  
    """邻接表实现图"""  
    def __init__(self):  
        self.vertexlist=[]  
        self.vnum=0  
        # self.vnum=len(self.vertexlist) #vnum似乎是固定的，不能根据vertexlist中的元素动态变化  
  
    def add_vertex(self,item):  
        """添加到顶点表中"""  
        vertex=Vnode(item)  
        self.vertexlist.append(vertex)  
        self.vnum+=1  
  
    def locate_vertex(self,vertex):  
        """查找结点在邻接表中的位置，若没有返回-1"""  
        for i in self.vertexlist:  
            if vertex==i.vertdata:  
                return self.vertexlist.index(i)  
        return -1  
  
    def add_edge(self,v1,v2,weight=0):  
        """添加边"""  
        a=self.locate_vertex(v1)  
        b=self.locate_vertex(v2)  
        if a==-1:  
            self.add_vertex(v1)  
            a=self.vertexlist.index(v1)  
        if b==-1:  
            self.add_vertex(v2)  
            b=self.vertexlist.index(v2)  
        p=Anode(b)  
        p.next=self.vertexlist[a].firsta  
        self.vertexlist[a].firsta=p  
  
def DFSadj(graph):  
    """基于邻接表的深搜遍历"""  
    visited=[0]*graph.vnum #标记结点是否被访问过  
    stack=[]  
    print(graph.vertexlist[0].vertdata,end=' ')  
    visited[0]=1  
    stack.append(0)  
    p=graph.vertexlist[0].firsta  
    while len(stack)!=0:  
        while p!=None:  
            if visited[p.edgedata]==0:  
                print(graph.vertexlist[p.edgedata].vertdata,end=' ')  
                visited[p.edgedata]=1  
                stack.append(p.edgedata)  
                p=graph.vertexlist[p.edgedata].firsta  
            else:  
                p=p.next  
        q=stack.pop()  
        p=graph.vertexlist[q].firsta  
  
def BFSadj(graph):  
    visited=[0]*graph.vnum  
    queue=[]  
    print(graph.vertexlist[0].vertdata,end=' ')  
    visited[0]=1  
    queue.append(0)  
    while len(queue)!=0:  
        i=queue.pop(0)  
        p=graph.vertexlist[i].firsta  
        while p!=None:  
            if visited[p.edgedata]==0:  
                print(graph.vertexlist[p.edgedata].vertdata,end=' ')  
                visited[p.edgedata]=1  
                queue.append(p.edgedata)  
            p=p.next  
  
graph=Graph()  
graph.add_vertex('v0')  
graph.add_vertex('v1')  
graph.add_vertex('v2')  
graph.add_vertex('v3')  
graph.add_vertex('v4')  
graph.add_edge('v0','v3')  
graph.add_edge('v0','v1')  
graph.add_edge('v1','v4')  
graph.add_edge('v1','v2')  
graph.add_edge('v1','v0')  
graph.add_edge('v2','v4')  
graph.add_edge('v2','v3')  
graph.add_edge('v3','v2')  
graph.add_edge('v3','v1')  
graph.add_edge('v4','v2')  
graph.add_edge('v4','v1')  
print(graph.vnum)  
print(len(graph.vertexlist))  
print(graph.vertexlist)  
for i in graph.vertexlist:  
    print(i.vertdata,end=' ')  
print()  
DFSadj(graph)  
print()  
BFSadj(graph)

生成树

特点 无回路 n个顶点一定有n-1条边 是图的极小连通子图 生成树中出现的边都在原图中 无向连通图的生成树不唯一，但必然有且仅有n-1条边 向生成树中任加一条边都一定构成回路

贪心算法

永远做出在当前看来最好的选择

Prim算法

算法的时间复杂度与顶点有关

Kruskal算法

从权重最小的边开始选 时间复杂度与边有关

单源最短路径

单源路径就是从一个顶点出发到其他顶点的距离 单源最短路径就是从一个顶点出发到其他各个顶点的最短路径

Dijkstra

从v1出发（dist[v]记录v到原点的最短距离） dist[w]=min(dist[w],dist[v]+<v,w>)

AOV网(Active on vertices)和拓扑排序

AOV网和拓扑排序用于获取做某些事情的先后顺序

AOV网（活动顶点网络）

特点 有向无环

顶点表示活动 弧表示活动之间的优先关系

拓扑排序

包含图中所有顶点的拓扑有序序列 若存在<v1,v2>，则在拓扑有序序列中v1必须在v2前 若不存在<v1,v2>，则在拓扑有序序列中不在意v1和v2的顺序

AOE网（Activity On Edge）与关键路径

AOE网和关键路径获取完成一些事情的时间（最短时间）

AOE网（活动边网络）

特点 有向无环

顶点表示事件 弧（边）表示活动 权值表示活动所需时间

性质 只有顶点事件发生后，边活动才开始 只有进入某一顶点的所有活动都已结束，该顶点代表的开始时间才能发生

存储结构

邻接表

#define MaxVertex 5

// 邻接表实现图
typedef struct Node {
    int nextVertex;  // 下一个顶点的索引
    struct Node* next;
} Node;

Node* createNode(int element) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->nextVertex = element;
    node->next = NULL;
    return node;
}

typedef struct HeadNode {
    int element;
    Node* next;
} HeadNode;

HeadNode* createHeadNode(int element) {
    HeadNode* node = (HeadNode*)malloc(sizeof(HeadNode));
    node->element = element;
    node->next = NULL;
    return node;
}

typedef struct AdjacencyGraph {
    int vertexCount;
    int edgeCount;
    HeadNode* vertex[MaxVertex];
} AdjacencyGraph;

AdjacencyGraph* createAdjacencyGraph() {
    AdjacencyGraph* graph = (AdjacencyGraph*)malloc(sizeof(AdjacencyGraph));
    graph->vertexCount = graph->edgeCount = 0;
    for (int i = 0; i < MaxVertex; i++) {
        graph->vertex[i] = NULL;
    }
    return graph;
}

void addVertex(AdjacencyGraph* graph, int element) {
    if (graph->vertexCount >= MaxVertex)
        return;
    graph->vertex[graph->vertexCount++] = createHeadNode(element);
}

void addEdge(AdjacencyGraph* graph, int a, int b) {
    if (graph == NULL || a >= graph->vertexCount || b >= graph->vertexCount || a < 0 || b < 0 || a == b || graph->vertex[a] == NULL || graph->vertex[b] == NULL)
        return;
    Node* node = graph->vertex[a]->next;
    Node* newNode = createNode(b);
    newNode->next = node;
    if (node == NULL) {
        graph->vertex[a]->next = newNode;
    } else {
        while (newNode->next != NULL) {
            if (newNode->next->nextVertex == b) {
                return;
            }

            node = newNode->next;
            newNode->next = newNode->next->next;
        }
        node->next = newNode;
    }
}

int main() {
    AdjacencyGraph* graph = createAdjacencyGraph();
    for (int i = 'A'; i <= 'D'; ++i) {
        addVertex(graph, i);
    }
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 0);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);


    return 0;
}

邻接矩阵

#define MaxVertex 5

// 邻接矩阵实现无向图
typedef struct MatrixGraph {
    int vertexCount, edgeCount;
    int matrix[MaxVertex][MaxVertex];
    int data[MaxVertex];
} MatrixGraph;

MatrixGraph *createMatrixGraph() {
    MatrixGraph *graph = (MatrixGraph *)malloc(sizeof(MatrixGraph));
    graph->vertexCount = graph->edgeCount = 0;
    // 使用 memset 清零二维数组
    memset(graph->matrix, 0, sizeof(graph->matrix));
    memset(graph->data, 0, sizeof(graph->data));
    return graph;
}

void addVertex(MatrixGraph *graph, int data) {
    if (graph == NULL || graph->vertexCount >= MaxVertex)
        return;
    graph->data[graph->vertexCount++] = data;
}

void addEdge(MatrixGraph *graph, int x, int y) {
    if (graph == NULL || x < 0 || x >= graph->vertexCount || y < 0 || y >= graph->vertexCount)
        return;
    graph->matrix[x][y] = graph->matrix[y][x] = 1;
    graph->edgeCount++;
}

void printGraph(MatrixGraph *graph) {
    printf("  ");
    for (int i = 0; i < MaxVertex; ++i) {
        printf("%c ", graph->data[i]);
    }
    printf("\n");
    if (graph == NULL)
        return;
    for (int i = 0; i < MaxVertex; i++) {
        printf("%c:", graph->data[i]);
        for (int j = 0; j < MaxVertex; j++)
            printf("%d ", graph->matrix[i][j]);
        printf("\n");
    }
}

int main() {
    MatrixGraph *graph = createMatrixGraph();
    for (int c = 'A'; c < 'D'; c++) {
        addVertex(graph, c);
    }
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);

    printGraph(graph);
    return 0;
}

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int vexnum = 0, arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs), vexnum(vexs.size()) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j))
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i) {
            if (!visited.at(i) && arcs.at(index).at(i))
                DFS(visited, i);
        }
    }

    void BFS(vector<int>& visited, int index) {
        queue<int> q;
        q.emplace(index);
        visited.at(index) = 1;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int cur = q.front();
                q.pop();
                cout << vexs.at(cur) << " ";
                for (int j = 0; j < arcs.at(cur).size(); ++j) {
                    if (arcs.at(cur).at(j) && !visited.at(j)) {
                        q.emplace(j);
                        visited.at(j) = 1;
                    }
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 1, 1, 1, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 0, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 1, 0}};

    Graph g("ABCDE", arcs);
    vector<int> visited(g.vexs.length(), 0);

    g.BFS(visited, 0);
    return 0;
}

图的遍历

#define MaxVertex 10

// 邻接表实现图
typedef struct Node {
    int nextVertex;  // 下一个顶点的索引
    struct Node* next;
} Node;

Node* createNode(int element) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->nextVertex = element;
    node->next = NULL;
    return node;
}

typedef struct HeadNode {
    int element;
    Node* next;
} HeadNode;

// 队列节点
typedef struct QueueNode {
    int element;
    struct QueueNode* next;
} QueueNode;

// 队列
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

bool initQueue(Queue* queue) {
    queue->front = queue->rear = NULL;
    return true;
}

bool enqueue(Queue* queue, int tnode) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    node->element = tnode;
    node->next = NULL;

    if (queue->front == NULL)
        queue->front = queue->rear = node;
    else {
        queue->rear->next = node;
        queue->rear = node;
    }
    return true;
}

bool isEmpty(Queue* queue) {
    return queue->front == NULL;
}

int dequeue(Queue* queue) {
    // 检查队列是否为空，为空则返回NULL
    if (queue->front == NULL)
        return NULL;
    int element = queue->front->element;
    queue->front = queue->front->next;
    return element;
}

HeadNode* createHeadNode(int element) {
    HeadNode* node = (HeadNode*)malloc(sizeof(HeadNode));
    node->element = element;
    node->next = NULL;
    return node;
}

typedef struct AdjacencyGraph {
    int vertexCount;
    int edgeCount;
    HeadNode* vertex[MaxVertex];
} AdjacencyGraph;

AdjacencyGraph* createAdjacencyGraph() {
    AdjacencyGraph* graph = (AdjacencyGraph*)malloc(sizeof(AdjacencyGraph));
    graph->vertexCount = graph->edgeCount = 0;
    for (int i = 0; i < MaxVertex; i++) {
        graph->vertex[i] = NULL;
    }
    return graph;
}

void addVertex(AdjacencyGraph* graph, int element) {
    if (graph->vertexCount >= MaxVertex)
        return;
    graph->vertex[graph->vertexCount++] = createHeadNode(element);
}

void addEdge(AdjacencyGraph* graph, int a, int b) {
    if (graph == NULL || a >= graph->vertexCount || b >= graph->vertexCount || a < 0 || b < 0 || a == b || graph->vertex[a] == NULL || graph->vertex[b] == NULL)
        return;
    Node* node = graph->vertex[a]->next;
    Node* newNode = createNode(b);
    newNode->next = node;
    if (node == NULL) {
        graph->vertex[a]->next = newNode;
    } else {
        while (newNode->next != NULL) {
            if (newNode->next->nextVertex == b) {
                return;
            }

            node = newNode->next;
            newNode->next = newNode->next->next;
        }
        node->next = newNode;
    }
}

/**
 * 深度优先搜索
 * @param graph 图
 * @param startVertex 起始顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 记录已达节点数组
 */
bool dfs(AdjacencyGraph* graph, int startVertex, int targetVertex, int* visited) {
    printf("%c ", graph->vertex[startVertex]->element);
    visited[startVertex] = 1;
    Node* node = graph->vertex[startVertex]->next;
    if (startVertex == targetVertex)
        return true;
    while (node) {
        if (!visited[node->nextVertex])
            if (dfs(graph, node->nextVertex, targetVertex, visited))
                return true;
        node = node->next;
    }
    return false;
}

/**
 * 广度优先搜索
 * @param graph 图
 * @param startVertex 起始顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 记录已达节点数组
 */
bool bfs(AdjacencyGraph* graph, int startVertex, int targetVertex, int* visited, Queue* queue) {
    enqueue(queue, startVertex);
    visited[startVertex] = 1;
    while (!isEmpty(queue)) {
        int next = dequeue(queue);
        printf("%c ", graph->vertex[next]->element);
        Node* node = graph->vertex[next]->next;
        while (node) {
            if (node->nextVertex == targetVertex)
                return true;
            if (!visited[node->nextVertex]) {
                enqueue(queue, node->nextVertex);
                visited[node->nextVertex] = 1;
            }
            node = node->next;
        }
    }
    return false;
}

int main() {
    AdjacencyGraph* graph = createAdjacencyGraph();
    for (int i = 'A'; i <= 'G'; ++i) {
        addVertex(graph, i);
        //printf("%c ", i);
    }
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 3, 6);

    int visited[graph->vertexCount];
    int visited2[graph->vertexCount];
    memset(visited, 0, sizeof(visited));
    memset(visited2, 0, sizeof(visited2));
    Queue queue;
    initQueue(&queue);
    
    printf("\ndfs:%d\n",dfs(graph, 0, 6, visited));

    printf("\nbfs:%d\n",bfs(graph, 0, 6, visited2, &queue));


    return 0;
}

广度优先搜索

#define MaxVertex 10

// 邻接表实现图
typedef struct Node {
    int nextVertex;  // 下一个顶点的索引
    struct Node* next;
} Node;

Node* createNode(int element) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->nextVertex = element;
    node->next = NULL;
    return node;
}

typedef struct HeadNode {
    int element;
    Node* next;
} HeadNode;

// 队列节点
typedef struct QueueNode {
    int element;
    struct QueueNode* next;
} QueueNode;

// 队列
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

bool initQueue(Queue* queue) {
    queue->front = queue->rear = NULL;
    return true;
}

bool enqueue(Queue* queue, int tnode) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    node->element = tnode;
    node->next = NULL;

    if (queue->front == NULL)
        queue->front = queue->rear = node;
    else {
        queue->rear->next = node;
        queue->rear = node;
    }
    return true;
}

bool isEmpty(Queue* queue) {
    return queue->front == NULL;
}

int dequeue(Queue* queue) {
    // 检查队列是否为空，为空则返回NULL
    if (queue->front == NULL)
        return NULL;
    int element = queue->front->element;
    queue->front = queue->front->next;
    return element;
}

HeadNode* createHeadNode(int element) {
    HeadNode* node = (HeadNode*)malloc(sizeof(HeadNode));
    node->element = element;
    node->next = NULL;
    return node;
}

typedef struct AdjacencyGraph {
    int vertexCount;
    int edgeCount;
    HeadNode* vertex[MaxVertex];
} AdjacencyGraph;

AdjacencyGraph* createAdjacencyGraph() {
    AdjacencyGraph* graph = (AdjacencyGraph*)malloc(sizeof(AdjacencyGraph));
    graph->vertexCount = graph->edgeCount = 0;
    for (int i = 0; i < MaxVertex; i++) {
        graph->vertex[i] = NULL;
    }
    return graph;
}

void addVertex(AdjacencyGraph* graph, int element) {
    if (graph->vertexCount >= MaxVertex)
        return;
    graph->vertex[graph->vertexCount++] = createHeadNode(element);
}

void addEdge(AdjacencyGraph* graph, int a, int b) {
    if (graph == NULL || a >= graph->vertexCount || b >= graph->vertexCount || a < 0 || b < 0 || a == b || graph->vertex[a] == NULL || graph->vertex[b] == NULL)
        return;
    Node* node = graph->vertex[a]->next;
    Node* newNode = createNode(b);
    newNode->next = node;
    if (node == NULL) {
        graph->vertex[a]->next = newNode;
    } else {
        while (newNode->next != NULL) {
            if (newNode->next->nextVertex == b) {
                return;
            }

            node = newNode->next;
            newNode->next = newNode->next->next;
        }
        node->next = newNode;
    }
}

/**
 * 深度优先搜索
 * @param graph 图
 * @param startVertex 起始顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 记录已达节点数组
 */
bool dfs(AdjacencyGraph* graph, int startVertex, int targetVertex, int* visited) {
    printf("%c ", graph->vertex[startVertex]->element);
    visited[startVertex] = 1;
    Node* node = graph->vertex[startVertex]->next;
    if (startVertex == targetVertex)
        return true;
    while (node) {
        if (!visited[node->nextVertex])
            if (dfs(graph, node->nextVertex, targetVertex, visited))
                return true;
        node = node->next;
    }
    return false;
}

/**
 * 广度优先搜索
 * @param graph 图
 * @param startVertex 起始顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 记录已达节点数组
 */
bool bfs(AdjacencyGraph* graph, int startVertex, int targetVertex, int* visited, Queue* queue) {
    enqueue(queue, startVertex);
    visited[startVertex] = 1;
    while (!isEmpty(queue)) {
        int next = dequeue(queue);
        printf("%c ", graph->vertex[next]->element);
        Node* node = graph->vertex[next]->next;
        while (node) {
            if (node->nextVertex == targetVertex)
                return true;
            if (!visited[node->nextVertex]) {
                enqueue(queue, node->nextVertex);
                visited[node->nextVertex] = 1;
            }
            node = node->next;
        }
    }
    return false;
}

int main() {
    AdjacencyGraph* graph = createAdjacencyGraph();
    for (int i = 'A'; i <= 'G'; ++i) {
        addVertex(graph, i);
        //printf("%c ", i);
    }
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 3, 6);

    int visited[graph->vertexCount];
    int visited2[graph->vertexCount];
    memset(visited, 0, sizeof(visited));
    memset(visited2, 0, sizeof(visited2));
    Queue queue;
    initQueue(&queue);
    
    printf("\ndfs:%d\n",dfs(graph, 0, 6, visited));

    printf("\nbfs:%d\n",bfs(graph, 0, 6, visited2, &queue));


    return 0;
}

图的应用

生成树和最小生成树

prim算法

#define MAX numeric_limits<int>::max()

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i) && arcs.at(index).at(i) != MAX)
                DFS(visited, i);
    }

    void prim(int index) {
        // 用于记录树的节点信息
        // 当前flag小于size，则表示当前图还未完全遍历
        // edge中的值为到达的权重 MAX表示不可达,为0表示已经遍历
        vector<int> edge(vexs.length(), MAX);
        int flag = 0, min = index;

        while (flag < edge.size()) {
            // 无最小生成树
            if (min == -1) {
                cout << "There is no minimum spanning tree" << endl;
                return;
            }

            cout << " --> " << vexs[min] << " , widget= " << edge[min] << endl;

            edge.at(min) = 0;
            ++flag;
            for (int i = 0; i < arcs[min].size(); ++i) {
                if (arcs[min][i] && arcs[min][i] != MAX) {
                    edge[i] = edge[i] > arcs[min][i] ? arcs[min][i] : edge[i];
                }
            }

            // 寻找权重最小值
            min = -1;
            for (int i = 0; i < edge.size(); ++i)
                if (edge[i] && edge[i] != MAX) {
                    if (min == -1)
                        min = i;
                    else
                        min = edge[min] > edge[i] ? i : min;
                }
        }
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 6, 1, 5, MAX, MAX},
        {6, 0, 5, MAX, 3, MAX},
        {1, 5, 0, 5, 6, 4},
        {5, MAX, 5, 0, MAX, 2},
        {MAX, 3, 6, MAX, 0, 6},
        {MAX, MAX, 4, 2, 6, 0}};

    // vector<vector<int>> arcs1 = {
    //     {0, 10, 20, MAX, MAX},
    //     {10, 0, 25, 30, MAX},
    //     {20, 25, 0, 35, 40},
    //     {MAX, 30, 35, 0, 45},
    //     {MAX, MAX, 40, 45, 0}};

    Graph g("ABCDE", arcs);
    g.prim(0);

    return 0;
}

kruskal算法

#define MAX numeric_limits<int>::max()

typedef struct Edge {
    int start;
    int end;
    int weight;

    Edge(int s, int e, int w) : start(s), end(e), weight(w) {}

    bool operator<(const Edge& e) const {
        return weight < e.weight;
    }

} Edge;

class UnionFind {
public:
    vector<int> arr;

    UnionFind(int n) : arr(n) {
        for (int i = 0; i < n; ++i) {
            arr[i] = -1;
        }
    }

    int find(int x) {
        if (x < 0)
            return x;

        if (arr[x] < 0)
            return x;

        int tmp = x;
        while (arr[tmp] >= 0) {
            tmp = arr[tmp];
        }
        arr[x] = tmp;
        return tmp;
    }

    void unionSet(int x, int y) {
        if (x < 0 || y < 0)
            return;

        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY)
            return;

        if (arr[rootX] > arr[rootY]) {
            arr[rootY] += arr[rootX];
            arr[rootX] = rootY;

        } else {
            arr[rootX] += arr[rootY];
            arr[rootY] = rootX;
        }
    }

    void foreach () {
        for (int i = 0; i < arr.size(); ++i) {
            cout << i << " " << arr.at(i) << endl;
        }
    }
};

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i) && arcs.at(index).at(i) != MAX)
                DFS(visited, i);
    }

    void kruskal() {
        vector<Edge> edges;
        for (int i = 0; i < arcs.size(); ++i) {
            for (int j = i; j < arcs[i].size(); ++j) {
                if (arcs[i][j] && arcs[i][j] != MAX) {
                    edges.emplace_back(Edge(i, j, arcs[i][j]));
                }
            }
        }
        sort(edges.begin(), edges.end(), [](const Edge& e1, const Edge& e2) {
            return e1.weight < e2.weight;
        });

        UnionFind connected(vexs.size());
        int flag = 0;
        for (int i = 0; i < edges.size(); ++i) {
            int start = edges[i].start;
            int end = edges[i].end;

            if (connected.find(start) != connected.find(end)) {
                connected.unionSet(start, end);
                ++flag;
                cout << vexs[start] << " --> " << vexs[end] << " , weight= " << edges[i].weight << endl;
            }

            if (flag == vexs.size() - 1) {
                cout << "yes min tree" << endl;
                return;
            }
        }
        if (flag < vexs.size() - 1)
            cout << "no min tree" << endl;
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 6, 1, 5, MAX, MAX},
        {6, 0, 5, MAX, 3, MAX},
        {1, 5, 0, 5, 6, 4},
        {5, MAX, 5, 0, MAX, 2},
        {MAX, 3, 6, MAX, 0, 6},
        {MAX, MAX, 4, 2, 6, 0}};

    // vector<vector<int>> arcs1 = {
    //     {0, 10, 20, MAX, MAX},
    //     {10, 0, 25, 30, MAX},
    //     {20, 25, 0, 35, 40},
    //     {MAX, 30, 35, 0, 45},
    //     {MAX, MAX, 40, 45, 0}};

    Graph g("12345", arcs);
    g.kruskal();
    return 0;
}

最短路径问题

dijkstra算法

#define MAX numeric_limits<int>::max()

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i) && arcs.at(index).at(i) != MAX)
                DFS(visited, i);
    }

    void dijkstra(int start) {
        vector<int> dist(vexs.size(), MAX);        // 源点到其他点的最短距离
        vector<int> path(vexs.size(), -1);         // 可达点到源点的前驱
        vector<bool> visited(vexs.size(), false);  // 是否已经访问

        path.at(start) = start;  // 源点到源点的距离为0
        visited[start] = true;
        dist.at(start) = 0;

        for (int i = 1; i < dist.size(); ++i) {
            // 设置可达点的前驱和到达原点的距离
            for (int j = 0; j < arcs[start].size(); ++j) {
                if (!visited[j] && arcs[start].at(j) && arcs[start].at(j) != MAX) {
                    if (dist[j] > (dist[start] + arcs[start].at(j))) {
                        dist[j] = dist[start] + arcs[start].at(j);
                        path[j] = start;
                    }
                }
            }
            // 寻找最小的未访问点
            int min = -1;
            for (int j = 0; j < dist.size(); ++j)
                if (!visited[j] && (dist[j] < dist[min] || min == -1))
                    min = j;

            if (min == -1) {
                cout << "No path!" << endl;
                return;
            } else {
                start = min;
                visited[start] = true;
            }
        }
        for (int i = 0; i < path.size(); ++i)
            cout << vexs.at(i) << " " << vexs.at(path.at(i)) << " " << dist.at(i) << endl;
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 12, MAX, MAX, MAX, 16, 14},
        {12, 0, 10, MAX, MAX, 7, MAX},
        {MAX, 10, 0, 3, 5, 6, MAX},
        {MAX, MAX, 3, 0, 4, MAX, MAX},
        {MAX, MAX, 5, 4, 0, 2, 8},
        {16, 7, 6, MAX, 2, 0, 9},
        {14, MAX, MAX, MAX, 8, 9, 0}};

    vector<vector<int>> arcs2={
        {0, 10, MAX, 1, MAX},  // A
        {10, 0, 1, MAX, 2},    // B
        {MAX, 1, 0, 1, MAX},   // C
        {1, MAX, 1, 0, 1},     // D
        {MAX, 2, MAX, 1, 0}    // E
    };


    Graph g("ABCDE", arcs2);
    vector<int> visited(g.vexs.size(), 0);
    g.DFS(visited, 0);
    cout << endl;

    g.dijkstra(0);
    return 0;
}

floyd算法

#define MAX numeric_limits<int>::max()

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i) && arcs.at(index).at(i) != MAX)
                DFS(visited, i);
    }

    void floyd() {
        vector<vector<int>> dist(arcs);                                       // 存储最短路径的权重
        vector<vector<int>> path(arcs.size(), vector<int>(arcs.size(), -1));  // 存储该点到点i的前驱

        // path数组初始化全为-1,若边权大于0小于max,则设置前驱
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs[i].size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    path.at(i).at(j) = i;

        // Floyd算法
        for (int i = 0; i < dist.size(); ++i)
            for (int j = 0; j < dist.size(); ++j)
                for (int k = 0; k < dist.at(j).size(); ++k)
                    if (dist.at(j).at(i) != MAX && dist.at(i).at(k) != MAX && dist.at(j).at(k) > (dist.at(j).at(i) + dist.at(i).at(k))) {
                        dist.at(j).at(k) = dist.at(j).at(i) + dist.at(i).at(k);
                        path.at(j).at(k) = i;
                    }

        cout << "Floyd: " << endl;
        for_each(dist.begin(), dist.end(), [](vector<int> v) {
            for_each(v.begin(), v.end(), [](int i) {
                cout << i << " ";
            });
            cout << endl;
        });

        cout << "min path: " << endl;
        for_each(path.begin(), path.end(), [](vector<int> v) {
            for_each(v.begin(), v.end(), [](int i) {
                cout << i << " ";
            });
            cout << endl;
        });
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 1, MAX, 3},
        {1, 0, 2, 2},
        {MAX, 2, 0, 8},
        {3, 2, 8, 0}};

    Graph g("ABCDE", arcs);
    vector<int> visited(g.vexs.size(), 0);
    g.floyd();
    return 0;
}

拓扑排序

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j))
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i))
                DFS(visited, i);
    }

    void topologicalSort() {
        // 建立一个入度表
        vector<int> inDegrees(vexs.size(), 0);
        for (int i = 0; i < vexs.size(); ++i)
            for (int j = 0; j < vexs.size(); ++j)
                if (arcs.at(j).at(i))
                    ++(inDegrees.at(i));

        queue<int> q;
        for (int i = 0; i < inDegrees.size(); ++i) {
            if (inDegrees.at(i) == 0) {
                q.emplace(i);
                inDegrees.at(i) = -1;
            }
        }

        while (!q.empty()) {
            int index = q.front();
            q.pop();
            cout << vexs.at(index) << " ";
            for (int i = 0; i < arcs.at(index).size(); ++i) {
                if(arcs.at(index).at(i)){
                    if (--inDegrees.at(i) == 0) {
                        q.emplace(i);
                        inDegrees.at(i) = -1;
                    }
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 1, 1, 1, 0, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 1, 0}};

    Graph g("123456", arcs);
    vector<int> visited(g.vexs.size(), 0);
    g.DFS(visited, 0);
    cout << endl;
    g.topologicalSort();
    return 0;
}

关键路径计算

#define MAX numeric_limits<int>::max()

class Graph {
public:
    string vexs;
    vector<vector<int>> arcs;
    int arcnum = 0;
    vector<int> topTable;

    Graph(string vexs, vector<vector<int>> arcs) : vexs(vexs), arcs(arcs) {
        for (int i = 0; i < arcs.size(); ++i)
            for (int j = 0; j < arcs.at(i).size(); ++j)
                if (arcs.at(i).at(j) && arcs.at(i).at(j) != MAX)
                    ++arcnum;
        arcnum /= 2;
    }

    ~Graph() {
        vexs.clear();
        for (int i = 0; i < vexs.size(); ++i) {
            arcs.at(i).clear();
        }
        arcs.clear();
    }

    void DFS(vector<int>& visited, int index) {
        visited.at(index) = 1;
        cout << vexs.at(index) << " ";
        for (int i = 0; i < arcs.at(index).size(); ++i)
            if (!visited.at(i) && arcs.at(index).at(i) && arcs.at(index).at(i) != MAX)
                DFS(visited, i);
    }

    void topologicalSort() {
        // 建立一个入度表
        vector<int> inDegrees(vexs.size(), 0);
        for (int i = 0; i < vexs.size(); ++i)
            for (int j = 0; j < vexs.size(); ++j)
                if (arcs.at(j).at(i) && arcs.at(j).at(i) != MAX)
                    ++(inDegrees.at(i));

        queue<int> q;
        for (int i = 0; i < inDegrees.size(); ++i) {
            if (inDegrees.at(i) == 0) {
                q.emplace(i);
                inDegrees.at(i) = -1;
            }
        }

        while (!q.empty()) {
            int index = q.front();
            topTable.emplace_back(index);
            q.pop();

            for (int i = 0; i < arcs.at(index).size(); ++i) {
                if (arcs.at(index).at(i) && arcs.at(index).at(i) != MAX) {
                    if (--inDegrees.at(i) == 0) {
                        q.emplace(i);
                        inDegrees.at(i) = -1;
                    }
                }
            }
        }
        for_each(topTable.begin(), topTable.end(), [](int& x) { cout << x << " "; });
    }

    // 关键路径
    void criticalPath() {
        vector<int> ve(topTable.size(), 0);  // 最早发生时间

        for (int i = 1; i < topTable.size(); ++i) {
            int cur = topTable.at(i);
            for (int j = 0; j < arcs.size(); ++j) {
                if (arcs.at(j).at(cur) && arcs.at(j).at(cur) != MAX) {
                    ve.at(cur) = max(ve.at(cur), ve.at(j) + arcs.at(j).at(cur));
                }
            }
        }

        for_each(ve.begin(), ve.end(), [](int& x) { cout << x << " "; });

        vector<int> vl(topTable.size(), ve.at(ve.size() - 1));  // 最晚发生时间

        for (int i = topTable.size() - 2; i >= 0; --i) {
            int cur = topTable.at(i);
            for (int j = 0; j < arcs.size(); ++j) {
                if (arcs.at(cur).at(j) && arcs.at(cur).at(j) != MAX) {
                    vl.at(cur) = min(vl.at(cur), vl.at(j) - arcs.at(cur).at(j));
                }
            }
        }
        cout << endl;
        for_each(vl.begin(), vl.end(), [](int& x) { cout << x << " "; });

        vector<int> d(topTable.size(), 0);  // 时间余量
        for (int i = 0; i < topTable.size(); ++i) {
            d.at(i) = vl.at(i) - ve.at(i);
        }
        cout << endl;
        for_each(d.begin(), d.end(), [](int& x) { cout << x << " "; });
    }
};

int main() {
    vector<vector<int>> arcs = {
        {0, 6, 4, 5, MAX, MAX, MAX, MAX, MAX},
        {MAX, 0, MAX, MAX, 1, MAX, MAX, MAX, MAX},
        {MAX, MAX, 0, MAX, 1, MAX, MAX, MAX, MAX},
        {MAX, MAX, MAX, 0, MAX, 2, MAX, MAX, MAX},
        {MAX, MAX, MAX, MAX, 0, MAX, 9, 7, MAX},
        {MAX, MAX, MAX, MAX, MAX, 0, MAX, 4, MAX},
        {MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, 2},
        {MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0, 4},
        {MAX, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0}};

    Graph g("012345678", arcs);
    vector<int> visited(g.vexs.size(), 0);
    g.DFS(visited, 0);
    cout << endl;
    g.topologicalSort();
    cout << endl;
    g.criticalPath();
    return 0;
}

贡献者

pinkdopeybug

版权所有

版权归属：PinkDopeyBug

许可证：署名 4.0 国际 (CC-BY-4.0)